How bit manipulation works?

Question

There was a question asked:

"Presented with the integer n, find the 0-based position of the second rightmost zero bit in its binary representation (it is guaranteed that such a bit exists), counting from right to left.

Return the value of 2position_of_the_found_bit."

I had written below solution which works fine.

int secondRightmostZeroBit(int n) {
  return (int)Math.pow(2,Integer.toBinaryString(n).length()-1-Integer.toBinaryString(n).lastIndexOf('0',Integer.toBinaryString(n).lastIndexOf('0')-1))  ;
}

But below was the best voted solution which I also liked as it has just few characters of codding and serving the purpose, but I could not understand it. Can someone explain how bit manipulation is helping to achieve it .

int secondRightmostZeroBit(int n) {
  return ~(n|(n+1)) & ((n|(n+1))+1) ;
}

Answer 1

Consider some number having at least two 0 bits. Here is an example of such a number with the 2 rightmost 0 bits marked (x...x are bits we don't care about which can be either 0 or 1, and 1...1 are the sequences of zero or more 1 bits to the right and to the left of the rightmost 0 bit) :

x...x01...101...1 - that's n

If you add 1 to that number you get :

x...x01...110...0 - that's (n+1)

which means the right most 0 bit flipped to 1

therefore n|(n+1) would give you:

x...x01...111...1 - that's n|(n+1)

If you add 1 to n|(n+1) you get:

x...x100........0 - that's (n|(n+1))+1

which means the second right most 0 bit also flips to 1

Now, ~(n|(n+1)) is

y...y10.........0 - that's ~(n|(n+1))

where each y bit is the inverse of the corresponding x bit

therefore ~(n|(n+1)) & ((n|(n+1))+1) gives

0...010.........0

where the only 1 bit is at the location of the second rightmost 0 bit of the input number.