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

Ernst Berg ernst_berg at sbcglobal.net
Sat Dec 6 16:23:52 CET 2003

```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 ?

---------------------------------------------
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-----
> 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
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.