Bob Felts <wrf3@stablecross.com> wrote:
+---------------
| One of the standard problems is to implement "countBits",
| which counts all of the bits set in an integer.  [1]
| One solution uses the fact that and'ing n with (n - 1)
| removes the leastmost bit set in n:
|    int countBits(int n)
|    { int count;
|      for (count = 0; n; n &= (n - 1))
|         ++count;
|      return (count);
|    }
+---------------

Unless you have some strong reason to expect that a *very* small
number of bits in "n" will be set on average, this method is horribly
slow. Much better is the standard iterated comb method, variations
of which were already well-known in the early days of computing
<http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item169>:

    int countBits(int n)	/* Assumes 32-bit ints */
    {
      n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
      n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
      n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
      n += (n >>  8);
      n += (n >> 16);
      return n & 0xff;
    }

This is branch-free, and runs in a constant number of cycles for all
inputs. [For 64 bits, add one more line and use wider constants.]

Of course, in Common Lisp one would simply use the built-in LOGCOUNT,
though if you allow negative arguments you will have to pick a
presumed "machine word size" for the result to be meaningful,
either this way:

    (defparameter +count-bits-word-width+ 64)	; For example

    (defun count-bits (n)
      (if (minusp n)
        (- +count-bits-word-width+ (logcount n)) ; See def'n of LOGCOUNT
        (logcount n)))

or this way:

    (defun count-bits (n &optional (bits-per-word 64))
      (if (minusp n)
        (- bits-per-word (logcount n)) 
        (logcount n)))

[Of course, some error-checking for the value being in range
of ints with BITS-PER-WORD bits would be nice.]


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607