Java 1 line bit manipulation solution


  • 52

    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;
            return num & mask;
        }
    }
    

    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);
        }
    }
    

  • 1
    L

    @shawngao said in Java 1 line bit manipulation solution:

    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.


  • 2
    A

    we have the similar idea and
    just like your

    num = ~num;
    return num & mask;
    

    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;
    

  • 5
    A

    @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;
    

    will be the answer


  • 7

    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) 
        {
            int mask = 1;
            while (mask < num) mask = (mask << 1) | 1;
            return ~num & mask;
        }
    

  • 0

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


  • 0

    @shawngao

    Question about performance optimization -

    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.


  • 0

    @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.


  • 0

    @jdrogin

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


  • 1
    L

    remove "<<1"

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

    works the same.


  • 0

    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.

    @leetesua said in Java 1 line bit manipulation solution:

    remove "<<1"

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

    works the same.


  • 2
    Z

    any good reason to use ~num & mask instead of num ^ mask???

    thanks


  • 0
    A

    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?


  • 0
    G

    Another solution in a line

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

  • 4
    T

    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;
        return num ^ mask;
    }

  • 0
    Y

    Same idea, slightly different code :)

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

  • 0
    M

    said in Java 1 line bit manipulation solution:

    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


  • 0

    @madhurauti Agreed


  • 0
    T

    @shawngao Why are you subtracting 1?


  • 1

    @thepha3drus

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


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.