Implement the missing code, denoted by ellipses. You may not modify the pre-existing code.
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 2^position_of_the_found_pair (0-based).
Example
For n = 10 and m = 11, the output should be
equalPairOfBits(n, m) = 2.
10 = 0b1010, 0b1110 = 0b1011, 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 2^1 = 2.
Approach
Similar to problem 23 - Different Rightmost Bit
Use the XOR bitwise operation to produce a 1 in every bit that differs.
10 = 0b1010
11 = 0b1011
0b1010 ^ 0b1011 = 0b0001
The rightmost 0 bit is in a position where the bits are the same in both n and m.
If the complement is taken: ~0001 = 1110
The rightmost 1 bit is the indicator that they are the same in both n and m.
In order to get the position_of_the_found_pair, we can take the complement of n XOR m then perform bitwise AND with (n^m) + 1:
0b1110 & (0b0001 + 0b0001) = 0b1110 & 0b0010 = 0b0010 = 2
def equalPairOfBits(n, m):
o = (n^m)
return ~o & (o + 1)
To follow the requirement: Implement the missing code, denoted by ellipses. You may not modify the pre-existing code.
def equalPairOfBits(n, m):
return ~(n^m) & ((n^m) + 1)
Alternatively, we can take the complement of n XOR m then perform bitwise AND with negative complement of n XOR m:
0b1110 & (0b0001 + 0b0001) = 0b1110 & 0b0010 = 0b0010 = 2
def equalPairOfBits(n, m):
o = (n^m)
return ~o & -(~o)
or
def equalPairOfBits(n, m):
return ~(n^m) & -(~(n^m))
It's equivalent because two's complement of a number can represent the negative number. To get the two's complement you perform two operations:
- Invert all the bits (can be done with bitwise NOT operator
~). - Add one to the result.
Summary
Problems like these are worth doing even when your day-to-day job doesn't require you to be messing around with bits. It tends to lead me down a rabbit-hole of other interesting related subject matter. You never know when it will be relevant to your work. It's good to refresh on the basics as well.