Home Original page

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