Home Original page

how to get the thighest bit position in big integers?

Aaron "Castironpi" Brady castironpi at gmail.com
Mon Oct 6 14:20:08 EDT 2008 
On Oct 6, 3:37 am, Mark Dickinson <dicki... at gmail.com> wrote:
> 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 alsohttp://bugs.python.org/issue3439
> where there's a proposal to expose the _PyLong_NumBits method.  This
> would give an O(1) solution.
>
> Mark

That generates an odd error with ctypes.

>>> from ctypes import *
>>> _PyLong_NumBits= PYFUNCTYPE( c_int, py_object )( pythonapi._PyLong_NumBits )
>>> _PyLong_NumBits( 1<<50 )
Traceback (most recent call last):
  File "_ctypes/callbacks.c", line 295, in 'calling callback function'
ctypes.ArgumentError: argument 1: <type 'exceptions.OverflowError'>:
long int to
o long to convert
2227205
>>>

Seems 'ctypes' tries to call PyLong_AsUnsignedLong for you.  Anyone
know a way around it?
More information about the Python-list mailing list