how to get the thighest bit position in big integers?
tjreedy at udel.edu
Mon Oct 6 00:40:22 CEST 2008
Scott David Daniels wrote:
> Since floating point has to identify the position of the highest bit,
> you can use that hardware to "quickly" get to the highest bit. IEEE
> has the mantissa .5 <= mantissa < 1., but some other floating point
> formats treated the mantissa in different ranges. This should work
> for anything where the exponent is truly a "binary point." In an older
> IBM floating point format, for example, the exponent was a "hexadecimal
> point," so the exponent only went up 1 when you multiplied by 16.
> EXP_OF_ONE = math.frexp(1.0)
> def high_bit(value):
> '''Find the highest order bit of a positive integer <= maxfloat'''
> assert value > 0
> return math.frexp(value) - EXP_OF_ONE
Your point, that taking floor(log2(x)) is redundant, is a good catch.
However, you should have added 'untested' ;-). When value has more
significant bits than the fp mantissa can hold, this expression can be 1
off (but no more, I assume). The following correction should be
res = math.frexp(value) - EXP_OF_ONE
test = 1<<res
if test > r: res -= 1
elif 2*test < r: res += 1
For value = 2**n -1, n > 53, it is always 1 too high on my Intel
machine, so the first correction is sometimes needed. I do not know if
the second is or not.
Terry Jan Reedy
More information about the Python-list