how to get the thighest bit position in big integers?

Scott David Daniels Scott.Daniels at Acm.Org
Mon Oct 6 01:35:00 CEST 2008

Terry Reedy wrote:
> ...
> 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

Well, I did test, but poorly.
 >>> high_bit(1<<587)
 >>> high_bit(1<<587-1)

And of course, I _should_ have tested
 >>> high_bit((1<<587)-1)

By the way, I wrote my response before any replies had happened; it was
not a correction to your post.

--Scott David Daniels
Scott.Daniels at Acm.Org

More information about the Python-list mailing list