On Oct 5, 5:26 pm, [EMAIL PROTECTED] 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
--
http://mail.python.org/mailman/listinfo/python-list
