[Codefights] Equal Pair of Bits

Problem

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

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

Example

For n = 10 and m = 11, the output should be
equalPairOfBits(n, m) = 2.

1010 = 10102, 1110 = 10112, the position of the rightmost pair of equal bits is the bit at position 1 (0-based) from the right in the binary representations.
So the answer is 21 = 2.


 

Solution

  • ~(n ^ m) & ((n ^ m) + 1)
  • ~(n ^ m) & -(~(n ^ m))

Explanation

Similar to previous post of “Different Rightmost Bit”, if we do XOR operation between the two numbers, we have 1 in every position that differs.

n = 1010 = 10102
m = 1110 = 10112

n XOR m = 1010^ 1011= 00012

Since 1 bit means the two number differed in that position, the rightmost 0 bit is the rightmost position of equal bits.

Let’s take a complement of this.
~00012 = 11102

Now, the rightmost 1 bit is the rightmost position of equal bits.

There are two options to take now.
With our x = n ^ m,

  • ~x & (x+1): AND operation with its complement and x+1
  • ~x & -(~x): AND operation with its complement and negative complement
    • Example is shown in the previous “Different Rightmost Bit” post

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