[EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
