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

2.6k Views Asked by At

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.

2

There are 2 best solutions below

0
On

"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.
INT discards the fraction.
Adding 1 gives the index position
of the bit, as you requested.

If you MUST have a value
for D in the case where
A=B, my suggestion would be
to force the value to 0, which
would be on a continuum
with the range of other
possible values.

2
On

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.