[Codefights] Different Rightmost Bit

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.
  • For n = 7 and m = 23, the output should be
    differentRightmostBit(n, m) = 16.710 = 1112, 2310 = 101112, i.e.

    00111
    10111
    

    So the answer is 24 = 16.


 

Solution

(n ^ m) & -(n ^ m)

Explanation

Let’s take n = 11 and m = 13 for example.
1110 = 10112
1310 = 11012

If we do XOR operation with n and m, we have 1 in every position that differs between the two.
1110 XOR 1310 = 10112 ^ 11012 = 01102

Since we have a bit representation of the positions that differ, we need to find the rightmost 1.

There is a trick to this. Given a number, x,
x & -x gives the rightmost 1
x = 6 = 01102
-x = -6 = 10102

x & -x = 0110& 10102 = 00102

So, (n^m) & -(n^m) is our answer.

 

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