how to get the thighest bit position in big integers?

[M.-A. Lemburg]

On 2008-10-05 17:26, mmgarvey at gmx.de wrote:
> Hi,
> 
> I'm using python to develop some proof-of-concept code for a
> cryptographic application. My code makes extended use of python's
> native bignum capabilities.
> 
> In many cryptographic applications there is the need for a function
> 'get_highest_bit_num' that returns the position number of the highest
> set bit of a given integer. For example:
> 
>    get_highest_bit_num( (1 << 159))     == 159
>    get_highest_bit_num( (1 << 160) - 1) == 159
>    get_highest_bit_num( (1 << 160))     == 160
> 
> I implemented this the following way:
> 
> def get_highest_bit_num(r):
>     i = -1
>     while r > 0:
>         r >>= 1
>         i = i + 1
>     return i
> 
> This works, but it is a very unsatisfying solution, because it is so
> slow.
> 
> My second try was using the math.log function:
> 
> import math
> r = (1 << 160) - 1
> print highest_bit_num(r)              # prints out 159
> print math.floor(math.log(r, 2))      # prints out 160.0
> 
> We see that math.log can only serve as a heuristic for the highest bit
> position. For small r, for example r = (1 << 16) - 1, the result from
> math.log(, 2) is correct, for big r it isn't any more.
> 
> My question to the group: Does anyone know of a non-hackish way to
> determine the required bit position in python? I know that my two
> ideas
> can be combined to get something working. But is there a *better* way,
> that isn't that hackish?

In Python 2.6, you can use the bin() builtin:

>>> len(bin(1<<159)) - 3
159

-- 
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Source  (#1, Oct 06 2008)
>>> Python/Zope Consulting and Support ...        http://www.egenix.com/
>>> mxODBC.Zope.Database.Adapter ...             http://zope.egenix.com/
>>> mxODBC, mxDateTime, mxTextTools ...        http://python.egenix.com/
________________________________________________________________________

:::: Try mxODBC.Zope.DA for Windows,Linux,Solaris,MacOSX for free ! ::::


   eGenix.com Software, Skills and Services GmbH  Pastor-Loeh-Str.48
    D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
           Registered at Amtsgericht Duesseldorf: HRB 46611