## The 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 `2`

(0-based).^{position_of_the_found_bit}

**Example**

For `n = 11`

and `m = 13`

, the output should be

`differentRightmostBit(n, m) = 2`

.

`11`

, _{10} = 10**1**1_{2}`13`

, the rightmost bit in which they differ is the bit at position _{10} = 11**0**1_{2}`1`

(0-based) from the right in the binary representations.

So the answer is `2`

.^{1} = 2

**Input/Output**

**[time limit] 4000ms (py)**

**[input] integer n***Constraints:*

`0 ≤ n ≤ 2`

.^{30}

**[input] integer m***Constraints:*

`0 ≤ m ≤ 2`

,^{30}

`n ≠ m.`

**[output] integer**

## The Solution

`def differentRightmostBit(n, m):`

return -~((~(n^m))^((~(n^m))+1))/2

## The Explanation

*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.

`11`

, _{10} = 10**1**1_{2}`13`

,_{10} = 11**0**1_{2}

`11`

_{10} XOR 13_{10} = 0110_{2}

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)

`11`

_{10} XNOR 13_{10} = 1001_{2}

The code to do this:

`(~(n^m))`

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))`

`return -~(q^(q+1))/2`

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,

` return -~((~(n^m))^((~(n^m))+1))/2`

Hope it does not sound so complicated now.

There’s another solution.

XOR the two bits to find the bits that differ, then take this and AND it with it’s complement.

ANDing a bit with it’s complement will return only right most set bit.

eg.

11 = 00001011

13 = 00001101

XOR

00001011

00001101

————–

00000110

————–

Take the twos complement (eg -x)

11111010

AND these values

00000110

11111010

————-

00000010

————-