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

[Wei Qin <wqin@EE.Princeton.EDU>]

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.

/*need to generate the table yourself*/
unsigned char mytable[256] = {0, 1, 1, 2, 1, ...};
int count (long long x) {

	int ret;
	union {
		long long val;
		unsigned char s[8];
	} a;

	ret = mytable[a.s[0]];
	ret += mytable[a.s[1]];
	....
	ret += mytable[a.s[7]];

	return ret;
}


On Thu, 25 Apr 2002 kelley.r.cook@gm.com wrote:

> int count (long long x) {
>
> int result;
>
> result =
> (x & 0x00000001 ? 1 : 0) +
> (x & 0x00000002 ? 1 : 0) +
> (x & 0x00000004 ? 1 : 0) +
> (x & 0x00000008 ? 1 : 0) +
> (x & 0x00000010 ? 1 : 0) +
> (x & 0x00000020 ? 1 : 0) +
> (x & 0x00000040 ? 1 : 0) +
> (x & 0x00000080 ? 1 : 0) +
> (x & 0x00000100 ? 1 : 0) +
> (x & 0x00000200 ? 1 : 0) +
> (x & 0x00000400 ? 1 : 0) +
> (x & 0x00000800 ? 1 : 0) +
> (x & 0x00001000 ? 1 : 0) +
> (x & 0x00002000 ? 1 : 0) +
> (x & 0x00004000 ? 1 : 0) +
> (x & 0x00008000 ? 1 : 0) +
> (x & 0x00010000 ? 1 : 0) +
> (x & 0x00020000 ? 1 : 0) +
> (x & 0x00040000 ? 1 : 0) +
> (x & 0x00080000 ? 1 : 0) +
> (x & 0x00100000 ? 1 : 0) +
> (x & 0x00200000 ? 1 : 0) +
> (x & 0x00400000 ? 1 : 0) +
> (x & 0x00800000 ? 1 : 0) +
> (x & 0x01000000 ? 1 : 0) +
> (x & 0x02000000 ? 1 : 0) +
> (x & 0x04000000 ? 1 : 0) +
> (x & 0x08000000 ? 1 : 0) +
> (x & 0x10000000 ? 1 : 0) +
> (x & 0x20000000 ? 1 : 0) +
> (x & 0x40000000 ? 1 : 0) +
> (x & 0x80000000 ? 1 : 0);
> return result;
> }
>
>