how to get the thighest bit position in big integers?

[Terry Reedy]

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)[1]
> 
> def high_bit(value):
>     '''Find the highest order bit of a positive integer <= maxfloat'''
>     assert value > 0
>     return math.frexp(value)[1] - 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 
sufficient:

res = math.frexp(value)[1] - 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