comparing bit lengths of binary numbers

Question

Suppose I have two binary numbers x and y that have bit lengths of nx and ny which are unknown. I'm looking for a fast method of comparing their bit lengths without computing their bit lengths; I think I found one using bitwise OR, and a pair of left shifts, but I'm not sure:

def comparelen(x, y):
   '''return -1 if bitlength(x)<bitlength(y),
      return  1 if bitlength(x)>bitlength(y),
      return  0 if bitlength(x)==bitlength(y)
   '''
   xy = x | y             # bitwise OR
   if (x << 1) <= xy:
      return -1
   if (y << 1) <= xy:
      return 1
   return 0

If x and y are the same length, it's easy to see that this will return the correct result.

If nx < ny - 1, or ny < nx - 1, this will return the correct result.

What I can't seem to figure out is if my function is correct for bit lengths that differ by one. Can anyone help me?

Answer 1

It does work. Suppose $x$ has length $n$ and $y$ has length $n+1$. Then $x|y$ begins with two leading ones, so if $2x \geq x|y$, then $x$ must begin with two ones. But then $x|y$ begins with three ones so $x$ must begin with three ones, and so forth. You finally conclude that $x$ is all ones, but in that case you still have $2x < x|y$ because $x|y$ is a string of $n+1$ ones whereas $2x$ is of length $n+1$ and ends in a zero. Thus $2x < x|y$ is guaranteed if the length of $x$ is less than the length of $y$. Nice algorithm you found :)