find position of most significant bit ?
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)
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*