how to get the thighest bit position in big integers?

[mmgarvey at gmx.de]

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?

cheers,
mmg