You’re given two integers,
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
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.
- [time limit] 4000ms (py)
- [input] integer nConstraints:
0 ≤ n ≤ 230.
- [input] integer mConstraints:
0 ≤ m ≤ 230,
n ≠ m.
- [output] integer
def differentRightmostBit(n, m):
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:
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))
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,
Hope it does not sound so complicated now.