# find position of most significant bit ?

**delta trinity
**
deltatrinity@hotmail.com

*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
*>*this.
*
_________________________________________________________________
The new MSN 8: advanced junk mail protection and 2 months FREE*
http://join.msn.com/?page=features/junkmail