[Codefights] Second-Rightmost Zero Bit

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 2position_of_the_found_bit.

Example

For 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 n.
Thus, the answer is 23 = 8.

Input/Output

  • [time limit] 4000ms (rb)
  • [input] integer n
    Guaranteed constraints:
    4 ≤ n ≤ 230.
  • [output] integer

 

Solution

~(k = n|n+1) & k+1

Explanation

Before we find the second rightmost, we need to be able to find the first.
To do so…

Suppose we have n = 37.
3710 = 1001012
3810 = 1001102

If we use an OR operator between the two numbers, 37 (n) and 38 (n+1), our first rightmost zero is “gone”. Let’s call this k (i.e. k = n|n+1)

3710 OR 3810 = 1001112

Now, the complement of this is ~k = ~1001112 = 0110002
And k+1 = 1010002

In k’s complement, other than our original first rightmost zero bit, all other “zero bits” will be all 1’s.
In k+1, our wanted “second rightmost zero” will have 1.

So if we use an AND operator between ~k and k+1, only the second zero will be 1 and all others will be 0’s.

~k & (k+1) = 0110002 AND 1010002 = 0010002

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s