Comparing Integers with a shift

[Paul Zimmermann]

       Dear Barukh,

> Date: Sun, 10 Jan 2010 09:56:21 +0200
> From: Barukh Ziv <barukh.ziv at gmail.com>
> 
> Dear all,
> 
> Consider the following scenario: given a constant integer a, and a variable
> integer b, that may be represented as b = d*2^n, where d is odd.
> 
> My question is: what is the most efficient way to compare a and d, if you
> are given a and b?
> 
> Working at C++ level, one possible way would be:
> 
> (b >> mpz_scan1(b. get_mpz_t(), 0)) == a
> 
> but this requires copying and allocation, which may be expensive in case a,
> b occupy many limbs.
> 
> Another approach is to compare mpz_sizeinbase(a, 2) (which is constant!) to
> mpz_sizeinbase(b, 2) - mpz_scan1(b, 0). If these are not equal, the outcome
> is clear; only in case they are equal, the aforementioned full comparison is
> performed.
> 
> Is this more efficient? Any other ideas are welcomed.
> 
> Regards,
> Barukh.

the most efficient method seems to be the following:

* if a is even, always return "inequal" :-)
* if a is odd, first compare the most significant bits of a and b
  (this might require shifting bits of a or b if they are not bit-aligned,
  alternatively you might precompute 64 copies of a which are shifted by 0
  to 63 bits)
* if the most significant bits (i.e., d) agree, then check the low bits of
  b are zero (here no shift is required)

Paul Zimmermann