Snippet: bitcount()
Christian Tismer
tismer at appliedbiometrics.com
Sat Jul 17 15:20:18 EDT 1999
Tim Peters wrote:
>
> This has been beaten beyond death so often I don't have the heart to do it
> all again <wink>. Some factoids:
>
> + Christian's post summarizes best efforts pre-1.5.2. For popcount4 it's
> missing the nbits function. Here's an elegant one that's reasonably fast:
>
> def nbits(x): # x >= 0 assumed
> if x <= 2:
> return x
> sum = 1
> while x:
> shift = 1
> x = x2 = x >> 1
> while x2:
> x = x2
> sum = sum + shift
> shift = shift + shift
> x2 = x >> shift
> return sum
Sorry, I forgot this one. It is exactly what was in my file.
> + About once a year someone gets excited about providing a pile of fast,
> basic longint ops (via extension module or adding methods to longs -- like
> popcount, trailing zero count, parity, nbits, long <-> int vector
> conversions, set/clear/test/invert bit number i, find closest 0/1 bit
> before/after bit number i). Unfortunately, nobody has persisted long enough
> to write a line of code, perhaps because people take such delight in endless
> argument about what to name things <0.1 wink>.
If someone should consider it at all:
Add a fast multiplication (with O(1.5)) or I won't look at it.
> the-next-person-to-get-excited-should-keep-it-a-secret-until-the-code-
> is-released-ly y'rs - tim
But I'm willing to help on the fast stuff via private emails :-)
more-code-less-words-ly y´rs - chris
--
Christian Tismer :^) <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH : Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net
10553 Berlin : PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF
saving one multiply by spending a few adds is the trick
no I don't mean Schoenhage-Strassen here.
More information about the Python-list
mailing list