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