Holger ishoej at gmail.com
Mon Oct 6 06:39:44 EDT 2008

• Previous message (by thread): how to get the thighest bit position in big integers?
• Next message (by thread): how to get the thighest bit position in big integers?
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

---

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

---

• Previous message (by thread): how to get the thighest bit position in big integers?
• Next message (by thread): how to get the thighest bit position in big integers?
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

---

More information about the Python-list mailing list