how to get the thighest bit position in big integers?
Mark Dickinson
dickinsm at gmail.com
Mon Oct 6 04:37:50 EDT 2008
On Oct 5, 11:40 pm, Terry Reedy <tjre... at udel.edu> 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
>
> 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.
See also http://bugs.python.org/issue3439
where there's a proposal to expose the _PyLong_NumBits method. This
would give an O(1) solution.
Mark
More information about the Python-list
mailing list