how to get the thighest bit position in big integers?
Fredrik Johansson
fredrik.johansson at gmail.com
Mon Oct 6 20:08:37 CEST 2008
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
More information about the Python-list
mailing list