find position of most significant bit ?

delta trinity
Wed, 27 Nov 2002 11:22:00 -0500

> > I assume one knows from the data structure of an arbitrary integer
> > where the limb containing the most significant bit is.
>Yes. If A is an mpz_t, then A->_mp_d[ABS(A->_mp_size) - 1] is the most
>significant limb, since ABS(A->_mp_size) is the number of limbs and
>the most significant limb is always nonzero. I'm not exactly sure what
>happens when A is zero, but I think that ABS(A->_mp_size) is zero
>then, so there are no limbs. (Someone correct me if I'm wrong!)

I think this is right.  First check if A->_mp_size==0.  If so, then the 
value of A is zero.

If not, then, take the absolute value of _mp_size because negatives numbers 
are stored as positive integers inside the structure.  The sign of the 
number is stored in _mp_size (two-complement).

Then, I guess the fastest way to check, if you have a x86 class processor, 
is to use the 'bsr' assembly instruction (bit scan reverse):

(Assuming you've put the A->_mp_d[ABS(A->_mp_size)] value into edx.  You 
could also use a memory refference)

bsr   eax,edx

Then, eax contain index of most significant bit.

> > Then the problem reduces to the problem of finding the most
> > significant within a limb (a machine word).
>In longlong.h there is a macro called count_leading_zeros that does

The new MSN 8: advanced junk mail protection and 2 months FREE*