``` Subject: Re: Squeezing blood from a turnip From: rpw3@rpw3.org (Rob Warnock) Date: Sun, 23 Jul 2006 00:07:58 -0500 Newsgroups: comp.lang.lisp Message-ID: <sp6dndOAdvezmV7ZnZ2dnUVZ_u6dnZ2d@speakeasy.net> ```
```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

```