how to get the thighest bit position in big integers?

[Terry Reedy]

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.

One alternative is to compare r against successive larger powers of 2, 
starting with 2**0 == 1.  Given that you have p=2**(n-1), you could test 
whether generating 2**n for large n is faster as 1<<n or p<<1.  A 
refinement would be to raise the test power k at a time instead of 1 at 
a time, tuning k for the implementation.  Then do binary search in the 
interval n, n+k.  I once read that longs store 15 bits in pairs of 
bytes.  If true today, k = 15 might be a good choice since <<15 would 
mean tacking on a pair of 0 bytes.

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

I tested and floor(log(2**n,2) == n for n in range(400), so your only 
worry is that the answer is 1 too high.  Easy to check and fix

res = int(math.floor(math.log(r, 2)))
if (1<<res) > r: res -=1

This works for 2**n-1 over the same range (all tests with 3.0rc1).

> My question to the group: Does anyone know of a non-hackish way to
> determine the required bit position in python?

If you call the standard methods hackish, I have no idea what would 
satisfy you ;-)

Terry Jan Reedy