How to Solve “secondRightmostZeroBit” in CodeFights

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 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 (py)
  • [input] integer nConstraints:
    4 ≤ n ≤ 230.
  • [output] integer

The Solution:
def secondRightmostZeroBit(n):
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.

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)

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 to1001112

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.

Advertisements

10 thoughts on “How to Solve “secondRightmostZeroBit” in CodeFights

  1. 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. 🙂

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

  3. 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)

    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.

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