How to Solve ‘DifferentRightmostBit’ in CodeFights

The Problem

You’re given two integers, n and m. Find position of the rightmost bit in which they differ in their binary representations (it is guaranteed that such a bit exists), counting from right to left.

Return the value of 2position_of_the_found_bit (0-based).

Example

For n = 11 and m = 13, the output should be
differentRightmostBit(n, m) = 2.

1110 = 10112, 1310 = 11012, the rightmost bit in which they differ is the bit at position 1 (0-based) from the right in the binary representations.
So the answer is 21 = 2.

Input/Output

  • [time limit] 4000ms (py)
  • [input] integer nConstraints:
    0 ≤ n ≤ 230.
  • [input] integer mConstraints:
    0 ≤ m ≤ 230,
    n ≠ m.
  • [output] integer

The Solution

def differentRightmostBit(n, m):
return -~((~(n^m))^((~(n^m))+1))/2

The Explanation

The question essentially requires us to find it using bitwise opetations. Although there are numerous other ways to find it, I will explain the bitwise solution I had.

To solve this problem, first, we need to find the different bits. It is not as hard as it sounds. A simple XOR operation gives us what we need.

1110 = 10112, 1310 = 11012,

1110 XOR 1310 = 01102

Now, we need to find first occurence of 1 here. However, it is easier to find first occurrence of zero. The operation we use becomes XNOR (if you have, otherwise, just get NOT)

1110 XNOR 1310 = 10012

The code to do this:

(~(n^m))

Now, how do we find the first occurrence of zero in a number?

I’d like to get your attention to another operation.

What happens when we add 1 to a number (in binary representation)?

The number gets 1 added to the rightmost bit. If it was already 1, converts it to zero and it creates a carry to the next bit until it reaches to a zero. This means that, each bit until a zero bit (including that zero bit) gets converted to its complement and the remaining bits are unchanged.

So, if we can find the first unchanged bit, we find our last changed bit, which is our first zero bit. (To go from first unchanged bit to last changed bit, we can divide the number by two.)

You can test it with a couple sample numbers. Or, you can see it in my previous post HERE.

To do this, we can XNOR the number with +added number. (q XNOR (q+1)).

Our solution becomes,

q = (~(n^m))

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

You probably noticed the sign in the answer, that is because the integers are signed according to their most significant bit in computing world and NOT operation reverses that bit too. So, we need to put – sign to get it back to positive numbers’ territory.

Because the problem wants us to give a one-liner, we replace q‘s with it’s value.

And, we get,

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

Hope it does not sound so complicated now.

Advertisements

One thought on “How to Solve ‘DifferentRightmostBit’ in CodeFights

  1. There’s another solution.

    XOR the two bits to find the bits that differ, then take this and AND it with it’s complement.

    ANDing a bit with it’s complement will return only right most set bit.

    eg.

    11 = 00001011
    13 = 00001101
    XOR
    00001011
    00001101
    ————–
    00000110
    ————–
    Take the twos complement (eg -x)
    11111010

    AND these values
    00000110
    11111010
    ————-
    00000010
    ————-

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