how to get the thighest bit position in big integers?

[Fredrik Johansson]

On Oct 5, 5:26 pm, mmgar... at gmx.de wrote:
> Hi,
>
> My question to the group: Does anyone know of a non-hackish way to
> determine the required bit position in python? I know that my two
> ideas
> can be combined to get something working. But is there a *better* way,
> that isn't that hackish?

No non-hackish way.

I've myself needed a version of this function for a speed-critical
application. For my purposes, it needs to be fast both for small and
extremely large numbers; the following is the fastest version I've
come up with. The idea to use bisect with a precomputed list when
possible, and math.log (with a correction) for larger numbers. There's
a tradeoff: a longer bisect table makes it fast for larger number, but
the bisection also becomes slower for small numbers. For my
application, 300 turned out to be a reasonable compromise.

from bisect import bisect
from math import log

powers = [1<<_ for _ in range(300)]

def bitcount(n):
    bc = bisect(powers, n)
    if bc != 300:
        return bc
    bc = int(log(n, 2)) - 4
    return bc + bctable[n>>bc]

bctable = map(bitcount, range(1024))

Calling this function is still slow, so when possible, I track the
approximate number of bits in a number across operations, and do (bc
+bctable[n>>bc]) inline (where bc is a low estimate of the number of
bits) to obtain the exact bit count.

Fredrik