**NOTE: Follow THIS link for more solutions.**

## The Problem:

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 `2`

.^{position_of_the_found_bit}

**Example**

For `n = 37`

, the output should be

`secondRightmostZeroBit(n) = 8`

.

`37`

. The second rightmost zero bit is at position _{10} = 10**0**101_{2}`3`

(0-based) from the right in the binary representation of `n`

.

Thus, the answer is `2`

.^{3} = 8

**Input/Output**

**[time limit] 4000ms (py)**

**[input] integer n***Constraints:*

`4 ≤ n ≤ 2`

.^{30}**[output] integer**

## The Solution:

`def secondRightmostZeroBit(n):`

return -~((n-~(n^(n+1))/2)^(n-~(n^(n+1))/2+1))/2

return -~((n-~(n^(n+1))/2)^(n-~(n^(n+1))/2+1))/2

## The Explanation:

To find second rightmost zero bit, we first need to find the first one. (in other words, Least significant zero bit).

How to…

Let’s look at the alternatives that we can use.

`37`

._{10} = 100101_{2}

`38`

_{10} = 100110_{2}

`^(37`

._{10)} = 011010_{2}

If we use XOR between our number N and (N+1), we get

`37`

._{10} XOR 38_{10}= 000011_{2}

This looks good. If we get the complement of this.

`-000100`

. This is almost what we need. But it gives the next bit rather than what we want._{2}

We can divide it by two to shift it (or use >> operator to shift it one bit.)

what we have is XOR and then a complement operation, namely, XNOR. (We don’t have XNOR, so we need to produce it ourselves.

**a XNOR b = ~(a ^ b)**

Now,

We found our first zero. What do we do to find second?

If we sum up our original number with this result, we get rid of first zero. (note the complement operation makes the number negative, so we need to subtract it instead of summation.

`n-~(n^(n+1))/2`

this is equal to`100111`

_{2}

Now, if we do the same thing operation with this new number, we get our result.

CodeFights limits us to write it as one return statement. So, it looks more complicated.

But if we assign this to a new variable **x.**

We have

`-~(x^(x+1))/2`

As our answer.

Otherwise, just type it twice and get the result.

Note that this time we don’t subtract it from X. Because we only need the number, we don’t need to get rid of the zero.

Yes, the problem is good. It can be solved in a couple more ways. However, the essence of the problem is the bitwise operations, so, solving it with only bitwise operations give people (at least, me) the full satisfaction of the solution.

As you can see, it is not easy to explain a solution. When you see the solution, it becomes much harder to explain it well. 🙂

I agree! That’s why I had to wrestle through it myself, even after I got the cheesy String-based solution.

A much simpler bitwise/arithmetic solution.

(((((n + 1) | n) + 1) | n) – n)

ORing n with (n + 1) fills the first zero bit.

ORing n with (step1 + 1) fills ONLY the second zero bit.

Negating n from step 2 leaves us with the answer.

Very neat, good solution, thanx

Although the solution is correct your explanation is incorrect. Check your math 37 xor 38 is 000011

I didn’t realize it. Updated. Thanks!

Great topic. Thanks to you I have also come up with another idea.

Solution:

var xnor = ~(n ^ (n + 1));

var sum = n | (n ^ (n + 1));

int pos = ~sum & (sum + 1);

thus: ~(n | (n ^ (n + 1))) & ((n | (n ^ (n + 1))) + 1)

Congrats!

Yes, when you get the gist of it, It’s pretty easy to come up with a solution. All the operations are built upon basic bitwise operations. So, using other bitwise or arithmetic operations leads to alternative one line solutions.