You’re given two integers,
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
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.
- ~(n ^ m) & ((n ^ m) + 1)
- ~(n ^ m) & -(~(n ^ m))
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 = 10102 ^ 10112 = 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