closed form solution?

Erik Demaine edemaine at
Mon Nov 26 20:49:18 PST 2001

Dear Gabriel,

As I understand it, you're asking for the number of most significant bits
that match between a and b.  To do this in constant time, lookup tables
of size O(U^epsilon) for any epsilon > 0 (e.g., O(sqrt U)) are the best
I know how to do.  If you'll settle for a lg lg U solution, you could
binary search on i.  It's also conceivable that you could do it in time
proportional to the number of 1 bits that match between a and b, which would
be fast if you expect to have more 0's than 1's.

Hope this helps,
Erik Demaine  |  edemaine at  |

On Thu, 22 Nov 2001, Gabriel Zachmann wrote:

> Dear all,
> does anybody know a closed form solution for the following equation?
>     floor( a * 2^i/U ) = floor( b * 2^i/U )
> where
>     U = 2^d
>     a,b in [0,U-1]
> I am looking for a closed form solution which would return the largest i
> solving the above equation.
> I know of 2 ways which both use some kind of lookup table of hash table,
> but I would prefer the closed form.
> (Remark: you probably have already seen that i is a common ancestor
> of a and b in a binary tree.)
> Thanks a lot in advance for any thoughts, hints, and pointers.
> Gabriel Zachmann.

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list