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