Re: [OT] Re: Number of 1's in 64 bit number...[don't read if not intereste d in algos/math...]

[Gabriel Paubert <paubert at iram dot es>]

Bernd Jendrissek wrote:

 > -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
 >
 > On Thu, Apr 25, 2002 at 08:13:17PM +0200, Gabriel Paubert wrote:
 >
 >> Nathan Sidwell wrote:
 >>
 >>
 >>> Wei Qin wrote:
 >>>
 >>>
 >>>> First, I see only 32 bits being counted. The top 32 bits seems
 >>>>
 >> missing.
 >>
 >>>> Second, this is a very slow implementation. A faster one can be
implemented
 >>>> through table lookup. It takes no masking, no branching.
 >>>>
 >>>>
 >>>>
 >>> I suspect something like... int bitson (unsigned long x) {    x =
 >>> (x & 0x55555555) + ((x >> 1) & 0x55555555);
 >>>
 >>
 >> Actually the most clever way of implementing that step that I know
 >> is:
 >>

 >>
 >> x -= (x>>1)&0x55555555;
 >>
 >> This happens to give the correct result for each pair of bits.
 >>
 >> Credit where credit is due: I found this trick on IBM´s website in
 >> their PPC compiler writer´s guide.
 >>
 >
 > I think the HAKMEM would predate this?  Item 169 - and it's in PDP-11
assembly.
 >



Certainly, I had never heard of HAKMEM before and i don't remember seeing
any reference in IBM's document.

However the base 2 decomposition looks comparable for many machines with 
32 or 64 bits words. The modulo 63 trick is neat, but can't be used for 64 
bit values and is costlier than a series of shifts, masks (easily skipped 
or factored on most steps) and adds on most RISC machines, including PPC 
which has a rather fast multiply-high instruction.


 >> From XFree86 source:
 > programs/Xserver/dix/colormap.c: /* next 3 magic statements count
 > number of ones (HAKMEM #169) */ pixel = (mask >> 1) & 033333333333;
 > pixel = mask - pixel - ((pixel >> 1) & 033333333333); if ((((pixel +
 > (pixel
 >>> 3)) & 030707070707) % 077) != planes) continue;
programs/Xserver/fb/fbcmap.c:
 >

 > static int popCount (int i) { int count;
 >
 > count = (i >> 1) & 033333333333; count = i - count - ((count >> 1) &
033333333333);
 > count = (((count + (count >> 3)) & 030707070707) % 077);    /* HAKMEM
 > 169 */ return count; }

Hmm, any algorithm like this should only use unsigned values, as should
any value on which you want to work at the bit level. Yes, the algorithm
seems to work in the corner cases, but I hate seeing int used in this context.

	Gabriel.