finding MSB ?? Best way or is there a function?

[delta trinity]

If mpz_t value is zero, there's no MSB.
Else, you can take the highest limb, and the fastest way would probably be 
to use assembly instruction BSR (bit scan reverse).

>From: Ernst Berg <ernst_berg at sbcglobal.net>
>To: gmp-discuss at swox.com
>Subject: finding MSB ?? Best way or is there a function?
>Date: Sat, 6 Dec 2003 16:23:52 -0800 (PST)
>
>I have been looking for a way to find the MSB of mpz_t
>in GMP.
>I am new to GMP.
>Below are the only texts I can find on the subject.
>   Do you know of any new or better ways to Find MSB in
>mpz_t.
>  Do you know of a standard function in/for GMP that
>finds MSB of mpz_t ?
>
>---------------------------------------------
>Previous posts on the subject  :  Your comments are
>welcome as to the validity of these suggestions.
>  My post continues after these quotes.
>--------------------------------------------
>Start--- "
>
>Hello,
>
>Is there an efficient way to compute the position of
>the most
>significant bit in a multiprecision integer?
>Basically, like
>mpz_scan1(), but instead of scanning from LSB to MSB,
>the other way around.
>
>mpz_sizeinbase(op, 2) would do it, but I don't know if
>there is a more
>efficent way to accomplish this.
>
>Regards,
>George Coulouris
>
>----------------------------------------------------------------------------
>George Coulouris <coulouri at ncbi.nlm.nih.gov> writes:
>
>   mpz_sizeinbase(op, 2) would do it, but I don't know
>if there is a more
>   efficent way to accomplish this.
>
>mpz_sizeinbase(op,2) should need just a few cycles.
>Is that not efficient enough?  ;-)
>
>--
>Torbjörn
>
>----------------------------------------------------------------------------
>
>----------------------------------------------------------------------------
>
>I assume one knows from the data structure of an
>arbitrary integer where the
>limb containing the most significant bit is.
>
>Then the problem reduces to the problem of finding the
>most significant
>within a limb (a machine word).
>
>I would tend to hardcode and bsearch it, i.e.
>
>if (word & 0x0000FFFF)
>    {
>    if (word & 0x000000FF)
>       {
>       }
>    else
>       {
>       }
>    }
>else
>    {
>    if (word & 0x00FF0000)
>       {
>       }
>    else
>       {
>       }
>    }
>
>You could just roll and test, but I'm not sure how
>that would compare
>against a hardcoded BSEARCH.
>
>Dave.
>-----------------------------------------------------------------------------
>-----------------------------------------------------------------------------
>
> > -----Original Message-----
> > From: gmp-discuss-admin at swox.com
>[mailto:gmp-discuss-admin at swox.com]On
> > Behalf Of Torbjorn Granlund
> > Sent: Tuesday, November 26, 2002 1:04 PM
> > To: George Coulouris
> > Cc: gmp-discuss at swox.com
> > Subject: Re: find position of most significant bit ?
> >
> >
> > George Coulouris <coulouri at ncbi.nlm.nih.gov> writes:
> >
> >   mpz_sizeinbase(op, 2) would do it, but I don't
>know if there is a more
> >   efficent way to accomplish this.
> >
> > mpz_sizeinbase(op,2) should need just a few cycles.
> > Is that not efficient enough?  ;-)
> >
> > --
> > Torbjörn
> > _______________________________________________
>
>-----------------------------------------------------------------------------
>
> > gmp-discuss mailing list
> > gmp-discuss at swox.com
> > https://gmplib.org/mailman/listinfo/gmp-discuss
>On 2002-11-26 16:25:18 -0500, David T. Ashley wrote:
> >
> > 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!)
>
> > 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.
>
>--
>Kalle Hasselström, kha at treskal.com
>       www.treskal.com/kalle
>
>
>-----------------------------------------------------------------------------
>  "---End
>
>
>
>This is great news for me that these fine folks offer
>aid in their posts; however, if there is already a
>function for this so much the better.
>  I didn't see any that I could tell was a MSB function
>so I guess I would need to write one.
>
>  Please if you know of a MSB function ready made let
>me know.
>
>Ernst_Berg at sbcglobal.net
>
>
>
>
>_______________________________________________
>gmp-discuss mailing list
>gmp-discuss at swox.com
>https://gmplib.org/mailman/listinfo/gmp-discuss

_________________________________________________________________
Get holiday tips for festive fun. 
http://special.msn.com/network/happyholidays.armx