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

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