how to get the thighest bit position in big integers?

[Gary Herron]

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
>   


How about a binary search? 

>>> from bisect import bisect
>>> BITS = [1<<n for n in range(1,1000)]  # Use max number of bits here.
>>> bisect(BITS, 1<<159)
159
>>> bisect(BITS, 1<<160-1)
159
>>> bisect(BITS, 1<<160)
160
>>>

I have no clue if this is faster or not.  The comparison function used
in the search is (potentially) slow, but the search is O(log n) on the
number of bits rather than O(n), so its worth a test.


If you run timing test, let us know the results.

Gary Herron



> 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?
>
> cheers,
> mmg
> --
> http://mail.python.org/mailman/listinfo/python-list
>