Clean and simple explanation why this bit manipulation works (with solution)


  • 0
    S
    • Let's assume the input a is 10101
    • Our answer should be simply ~a = 01010. If we discard the left most zero then 1010. The problem is that Java doesn't store it like that.
    • Java would still store it as 11111111111111111111111111101010 because it stored the a with leading zeros since every integer is stored using 32 bits.
    • This is not what we want.
    • How to get rid of the redundant one's in the result then? Mask those bits.
      • Come up with a number that makes the unwanted 1s as 0s and leave the wanted bits as it is. Something like 00000000000000000000000000001111.
      • How to come up with this mask? If we subtract 1 from something like 10000, it'll give us 1111.
      • How did I come up with 10000? It's the highest bit of integer present in the input (10101)
      • So, Integer.highestOneBit(input) will give me 10000.
      • Integer.highestOneBit(input) - 1 will give me 1111. Its nothing but 00000000000000000000000000001111.
      • Now we've successfully generated our mask.
    • Now ~a ANDed with this mask will give you your result- ~num & mask;
    public int findComplement(int num) {
            int mask = Integer.highestOneBit(num) - 1;
            return ~num & mask;
    }
    

Log in to reply
 

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