1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by "reading left to right"? If you are looking for a constant time solution, then we can't iterate. $\endgroup$ – John Griffin Aug 7 '17 at 19:48
  • $\begingroup$ 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. $\endgroup$ – user3243499 Aug 7 '17 at 19:51
  • $\begingroup$ If $$ a = (01110100)_2$$ and $$ b = (11101011)_2,$$ then would the answer still be $5$? $\endgroup$ – John Griffin Aug 7 '17 at 19:52
  • $\begingroup$ Are you counting operation time by word length or bit length? $\endgroup$ – platty Aug 7 '17 at 19:57
  • $\begingroup$ 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. $\endgroup$ – user3243499 Aug 7 '17 at 19:57
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This fails when $a=(00001011)_2$,and, $b=(00001111)_2$ $\endgroup$ – user3243499 Aug 8 '17 at 7:00
  • $\begingroup$ $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 $\endgroup$ – Ross Millikan Aug 8 '17 at 14:42
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.