how to get the thighest bit position in big integers?

[Scott David Daniels]

mmgarvey at gmx.de wrote:
> 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
>...
> def get_highest_bit_num(r):
>     i = -1
>     while r:
>         r >>= 1
>         i += 1
>     return i
> My second try was using the math.log function:
> print math.floor(math.log(r, 2))      # prints out 160.0

Since floating point has to identify the position of the highest bit,
you can use that hardware to "quickly" get to the highest bit.  IEEE
has the mantissa .5 <= mantissa < 1., but some other floating point
formats treated the mantissa in different ranges.  This should work
for anything where the exponent is truly a "binary point." In an older
IBM floating point format, for example, the exponent was a "hexadecimal
point," so the exponent only went up 1 when you multiplied by 16.


EXP_OF_ONE = math.frexp(1.0)[1]

def high_bit(value):
     '''Find the highest order bit of a positive integer <= maxfloat'''
     assert value > 0
     return math.frexp(value)[1] - EXP_OF_ONE

--Scott David Daniels
Scott.Daniels at Acm.Org