Reini Urban <rurban@sbox.tu-graz.ac.at> wrote:
+---------------
| I vaguely remember that there existed some trick to count the bits == 1
| in a fixnum in constant time.  ...
| something with logior, logand or similar...
| can anybody point me to the trick?
+---------------

Not sure how to make this work nicely with arbitrarily-large bignums,
but for fixed-sized numbers the standard "trick" you're probably thinking
of is to add up the bits in ever-widening "combs". Please excuse my use of
C here -- I'm not familiar enough with the corresponding operations in CL.
Assuming type "unsigned long" is 32 bits, then we have:

	int countbits(unsigned long x) {
	    if (x == 0)	/* fast case */
	      return 0;
	    x = ((x >> 1) & 0x55555555) + (x & 0x55555555);
	    x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
	    x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
	    x = ((x >> 8) & 0x00ff00ff) + (x & 0x00ff00ff);
	    x = ((x >> 16) & 0x0000ffff) + (x & 0x0000ffff);
	    return (int)x;
	}

After the first assignment, successive pairs of bits within "x" each
have the value 0, 1, or 2, depending on whether the original pair was
both clear, one set, or both set. The "trick" is that this sum cannot
overflow into an adjacent pair. And so it goes, with the width of
the "sum buckets" doubling each time until there is just one "bucket"
containing the count of the total number of non-zero bits in the
original word.


-Rob

-----
Rob Warnock, 8L-855		rpw3@sgi.com
Applied Networking		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		FAX: 650-933-0511
Mountain View, CA  94043	PP-ASEL-IA