# How to find the least significant bit position using bit position common to two numbers?

Let's say, I have two numbers $$a = (01110100)_2$$ and $$b = (01101011)_2$$

How to find the position of the least significant bit common to a and b while reading left to right in constant time $O(1)$ using bitwise operations?

I was reading articles on the web to find the LSB, and all I get is $(x\&-x)$. However, I am not able to convert this concept in finding the common LSB of two numbers a and b instead of just one number x.

For example, for the above numbers, matching is $(011)_2$ so the LSB common to both is at position 5 or 6 (if we consider 0th bit in position 1).

EDIT: Or atleast a faster method than to literally checking bit by bit.

• What do you mean by "reading left to right"? If you are looking for a constant time solution, then we can't iterate. – John Griffin Aug 7 '17 at 19:48
• I understand why it sounds confusing. My sole intention of putting "reading left to right" is just to describe what I mean by "common to a and b". Obviously, if I iterate through bits then it is no longer a constant time. – user3243499 Aug 7 '17 at 19:51
• If $$a = (01110100)_2$$ and $$b = (11101011)_2,$$ then would the answer still be $5$? – John Griffin Aug 7 '17 at 19:52
• Are you counting operation time by word length or bit length? – platty Aug 7 '17 at 19:57
• Your value of a is same as the one I have mentioned. But I think you are asking what if a==b. Well in that case the bitwise expression should result to something which respresents equality. Basically, what I mean is, how can we find the EXTENT to which any two numbers have common binary string. if $$b=(01110001)_2$$, then the common string is $(011110)_2$ so the position should be 4. – user3243499 Aug 7 '17 at 19:57

Let $y$ be bitwise invert ($a$ XOR $b$), then do $y \& (-y)$ This gives you a $1$ in the lowest bit where $a$ and $b$ agree.

• This fails when $a=(00001011)_2$,and, $b=(00001111)_2$ – user3243499 Aug 8 '17 at 7:00
• $a$ and $b$ agree in bit $0$. $a$ XOR $b=00000100, y=11111011, -y=00000101, y\&-y=00000001$, just as you want. Note that $-y$ is twos complement, as in your $a \& -a$ example – Ross Millikan Aug 8 '17 at 14:42

"How to find the position of
the least significant bit common
to a and b while reading left
to right in constant time O(1)O(1)
using bitwise operations?"

# -- quotation from original statement.

Call what you are seeking D.
After ascertaining that A <> B,
D = INT((LOG(A XOR B)/LOG(2))+1

Convention:
high-order digit is digit 7,
low-order digit is digit 0.

Explanation: All occurrences
of corresponding-but-differing
bits in the two numbers are
given by A XOR B.
The near-index of the first
differing bit is given by
LOG(A XOR B)/LOG(2) --
i.e., the base-2 logarithm of
A XOR B.