how to get the thighest bit position in big integers?
Terry Reedy
tjreedy at udel.edu
Sun Oct 5 13:10:42 EDT 2008
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
More information about the Python-list
mailing list