how to get the thighest bit position in big integers?
Holger
ishoej at gmail.com
Mon Oct 6 06:39:44 EDT 2008
On 6 Okt., 10:37, Mark Dickinson <dicki... at gmail.com> wrote:
> See alsohttp://bugs.python.org/issue3439
> where there's a proposal to expose the _PyLong_NumBits method. This
> would give an O(1) solution.
Doesn't that depend on the underlying implementation?
Anyway, here's a pretty one (I think):
def highest_bit(n, maxbits = 256):
bit = 0
while maxbits > 1:
maxbits = maxbits >> 1
mask_b = ((1<<maxbits)-1)
mask_a = mask_b<<maxbits
a = n & mask_a
b = n & mask_b
if a:
bit = bit + maxbits
n = a >> maxbits
else:
n = b
return bit
I suspect you would call that a O(logn)) solution
Holger
More information about the Python-list
mailing list