Snippet: bitcount()

[Tim Peters]

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

Jurjen N.E. Bos's implementation of the constructive reals (Python FTP
contrib) contains a marshal-based method that's quicker for very large
longs.

+ nbits *should* be a constant-time operation, but there's no way to do that
in Python today.

+ hex(long) takes time linear in the number of bits in 1.5.2.  It used to be
quadratic-time.  This makes old tradeoffs open to question.  The notion that
it's too memory-intensive is misguided (longs are immutable -- you can't
even add 1 to a long without consuming 2*nbits(long) bits, and hex(long) is
no worse wrt memory than adding 1 twice <wink>).

+ "long1 & long2" (both > 0) takes time proportional to
       min(nbits(long1), nbits(long2))
in 1.5.2.  It used to take time proportional to the max of those.  This
makes shift-and-mask methods more attractive than they used to be.

+ The format of Python longs is defined in the source distribution's
    Include/longintrepr.h
  marshal-based tricks exploit that more-than-less directly.

+ 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>.

the-next-person-to-get-excited-should-keep-it-a-secret-until-the-code-
    is-released-ly y'rs  - tim