NOTE: Follow THIS link for more solutions.
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
n = 37, the output should be
secondRightmostZeroBit(n) = 8.
3710 = 1001012. The second rightmost zero bit is at position
3 (0-based) from the right in the binary representation of
Thus, the answer is
23 = 8.
- [time limit] 4000ms (py)
- [input] integer nConstraints:
4 ≤ n ≤ 230.
- [output] integer
To find second rightmost zero bit, we first need to find the first one. (in other words, Least significant zero bit).
Let’s look at the alternatives that we can use.
3710 = 1001012.
3810 = 1001102
^(3710) = 0110102.
If we use XOR between our number N and (N+1), we get
3710 XOR 3810= 0000112.
This looks good. If we get the complement of this.
-0001002. This is almost what we need. But it gives the next bit rather than what we want.
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)
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.
this is equal to
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.
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.