# 3 line C++

• ``````class Solution {
public:
int findComplement(int num) {
unsigned mask = ~0;
while (num & mask) mask <<= 1;
return ~mask & ~num;
}
};
``````

For example,

``````num          = 00000101
~mask & ~num = 00000010
``````

• or

``````class Solution {
public:
int findComplement(int num) {
unsigned mask = ~0;
while (num & mask) mask <<= 1;
return num ^ ~mask;
}
};
``````

• Hi lzl,

Thank you for sharing your code. Could you please help me with the following quick question regarding your code?

Seems it is important to define variable "mask" using "unsigned" type, I tried to define it as "int" type but there was Run Time Error. Could you please explain a little why "int" type will case failure here?

Thank you in advance

• @BSKLK I got AC if use `int`... No idea why you get RTE.

I think you could use `int` in this case to save some typing. I used `unsigned` for masks whenever I'm doing bit manipulation so that I don't need to care the shift direction:

``````((unsigned)~0) >> 1 == 01111111111111111111111111111111
~0 >> 1             == 11111111111111111111111111111111
``````

• ``````while (num & mask) mask <<= 1;
``````

I am confused about this line. Could you explain it in detail? What is the purpose of the while loop and what does <<= 1 accomplish?

• In Python

``````class Solution(object):
def findComplement(self, num):

x = len(bin(num)[2:])
m = int('1'*x,2)
return m^num
``````

• @mawills In English, it's "as long as `num` and `mask` has bit `1` at the same place (i.e. overlap), shift `mask` left by one bit"

For example

``````num          = 00000101
^ ^ overlap!
num          = 00000101
^   overlap!
num          = 00000101
^   overlap!
num          = 00000101
clear!
``````

• @lzl124631x I think I understand it now, thank you!

• very cool, I didn't think of inverting the mask, rather I built up my mask to be set bits up to the point where the most signification bit is covered.

``````    public int FindComplement(int num)
{
int mask = 1;
while (mask < num) mask = (mask << 1) | 1;
return ~num & mask;
}
``````

• @jdrogin The last line can be " return num ^ mask; " -- one less operation.

• Hi. I have a question about this solution. For the while loop, if I use

``````while (num & mask != 0) mask <<= 1;
``````

``````while (num & mask) mask <<= 1;
``````

then I got incorrect answer. So the difference is in that `!= 0`

I do not understand why. Could you tell me why that would be wrong? Thank you.

• @dragonhyq-gmail.com `mask << 1` doesn't change `mask`. `mask <<= 1;` does.

• @lzl124631x Hi. I am very sorry I had a typo in my post, I have edited it. Could you take a look again? I think I understand the entire process of creating the mask, shifting the mask, and flipping the lower bits. But that `!=0` thing eludes me...

Thank you in advance!

• Have u considered the input parameters of the function? It needs to be 32-bit signed integer. Please check ur code.

• @dragonhyq-gmail.com Be cautious when using bitwise operators. Checkout the C++ operator priorities. `&` is even of lower priority than `!=`.

IMHO, if you are not sure the priority, always enclose bistwise binary operators `&` `|` `^` in parentheses, e.g. `while((num & mask) != 0)`.

• @veeperbupt does it matter? please check again.

• @lzl124631x You are right! It is the priority! Thank you!

• I think my solution is easier than you ,but it can't pass the tests , some cases make it Time Limit Exceeded ,I can't find out it, I test some cases in my own IDE,it pass all.,canld you help me?
class Solution { Time Limit Exceeded
public:
int findComplement(int num) {
int tmp = 1;
while (tmp <= num) tmp <<= 1;
return (tmp - num - 1);
}
};

• @sgsg it should be ~mask ^ num :-)

• My code is very similar to yours, but still i get "error: expected unqualified-id before string constant" It seems to run properly in my IDE. any ideas where I am making a mistake ?

``````        int n = ceil(log2(num));
int mask = (pow(2,n)-1);