# Java 1 line bit manipulation solution

• I post solution first and then give out explanation. Please think why does it work before read my explanation.

``````public class Solution {
public int findComplement(int num) {
return ~num & ((Integer.highestOneBit(num) << 1) - 1);
}
}
``````

According to the problem, the result is

1. The `flipped` version of the original `input` but
2. Only flip `N` bits within the range from `LEFTMOST` bit of `1` to `RIGHTMOST`.
For example input = `5` (the binary representation is `101`), the `LEFTMOST` bit of `1` is the third one from `RIGHTMOST` (`100`, `N` = 3). Then we need to flip 3 bits from `RIGHTMOST` and the answer is `010`

To achieve above algorithm, we need to do 3 steps:

1. Create a bit mask which has `N` bits of `1` from `RIGHTMOST`. In above example, the mask is `111`. And we can use the decent Java built-in function `Integer.highestOneBit` to get the `LEFTMOST` bit of `1`, left shift one, and then minus one. Please remember this wonderful trick to create bit masks with `N` ones at `RIGHTMOST`, you will be able to use it later.
2. Negate the whole input number.
3. `Bit AND` numbers in step `1` and `2`.

Three line solution if you think one line solution is too confusing:

``````public class Solution {
public int findComplement(int num) {
int mask = (Integer.highestOneBit(num) << 1) - 1;
num = ~num;
}
}
``````

`UPDATE`
As several people pointed out, we don't need to left shift 1. That's true because the highest `1` bit will always become `0` in the `Complement` result. So we don't need to take care of that bit.

``````public class Solution {
public int findComplement(int num) {
return ~num & (Integer.highestOneBit(num) - 1);
}
}
``````

• Integer.highestOneBit

I didn't know about the method, Integer.highestOneBit, so needed to implement it by myself. It's a good tip!

return num ^ ((Integer.highestOneBit(num) << 1) - 1)> might be faster.

• we have the similar idea and
just like your

``````num = ~num;
``````

my

``````return mask-num；
``````

will work as well but yours is faster :)
and my one line solution is ：

``````return (Integer.highestOneBit(num) << 1) - 1-num;
``````

• @Archonzzb My idea is that the sum of one number and it's complement number will be 2^n-1(11.....111) so

`````` (Integer.highestOneBit(num)<<1)-1-num;
``````

• nice solution, I came up with similar just not using any built in functions. The mask is all set bits to cover the range of the number. From there just do the complement and apply the mask

C#

``````    public int FindComplement(int num)
{
}
``````

• ~num&((Integer.highestOneBit(num) << 1) - 1) = num^((Integer.highestOneBit(num) << 1) - 1)

• @shawngao

The algorithm in the original post is almost in its simplest form.
Here are the stats when I ran it -

`149 / 149` test cases passed.
Status: Accepted
Runtime: `12 ms`
Beat: `32.28%`

Some algorithms got higher performance because they are more efficient or simply there used to be less test cases?
If it's the latter, then no concerns.

• @zzhai hey, you can't read too much into the time rating. if you are way off you should look for a better approach. But, in general the times are pretty inconsistent. You can try running your solution a few times to see how it varies. Better to read the discussion posts and really understand how your approach compares, don't look at the ranking too much.

• @jdrogin

Agreed. You can see I just began the journey in this site.

• remove "<<1"

public class Solution {
public int findComplement(int num) {
return ~num & (Integer.highestOneBit(num)-1);
}
}

works the same.

• I guess it's not the same.
Edit: Understood. the leading `1` will be `0` in the complement, so it's unnecessary for the mask to have this bit.

remove "<<1"

public class Solution {
public int findComplement(int num) {
return ~num & (Integer.highestOneBit(num)-1);
}
}

works the same.

thanks

• Cool solution!

But just curious, what are the chances of these bit manipulation questions being asked on a mid-senior level dev or sdet interviews?

• Another solution in a line

`````` public int findComplement(int num) {
return (0xffffffff >>> Integer.numberOfLeadingZeros(num)) & ~num;
}
``````

• Once we get the bit mask (N bits of 1 from rightmost), can we simply do num ^ mask? An XOR operation will flip 1 to 0 and 0 to 1. I tried it and it passed all tests.

``````public int findComplement(int num) {
int mask = (Integer.highestOneBit(num) << 1) - 1;
}``````

• Same idea, slightly different code :)

``````public class Solution {
public int findComplement(int num) {
int n = Integer.highestOneBit(num) << 1;
return n - num - 1;
}
}
``````

• highestOneBit : Do we need to left shift by 1 bit? so for any number we are sure that the highestOneBit will become '0' so a mask of Integer.highestOneBit(num) - 1 should work i.e. for 5 (101 --> 100 (-1) --> 11 & (~) 11111...010 = 2

To create a mask `111...111` that has the same length as the original number.