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)
587
 >>> high_bit(1<<587-1)
586

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

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