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