SUMMARY: count of bits set in a word
Neal R. Wagner
nwagner at ut-emx.uucp
Thu Sep 27 08:15:39 AEST 1990
The net is wonderful! Within 24 hours I had a dozen replies. No, I was not
asking the net to do my homework. I'm a faculty member writing a program to
generate Steiner systems, and the bit counting problem seemed like an
interesting C question, so I threw it out for comment.
Much thanks to the following for their e-mail replies.
karl at IMA.ISC.COM (Karl Heuer)
luciano at canuck.Berkeley.EDU (Luciano Lavagno)
munnari!batserver.cs.uq.oz.au!grue at uunet.UU.NET (Paul Dale)
munnari!wolfen.cc.uow.edu.au!pejn at uunet.UU.NET (Paul Nulsen)
Icarus Sparry <I.Sparry at gdr.bath.ac.uk>
jvl at idca.tds.PHILIPS.nl (J. van Loenen)
Schijf Ardie <schijf at cs.vu.nl>
motcsd!dms!albaugh at apple.com (Mike Albaugh)
calvin!johns at nwnexus.wa.com (John Sahr)
teda!ehp at ames.arc.nasa.gov (Ed Porter)
friedl at mtndew.Tustin.CA.US (Steve Friedl)
dmi at peregrine.COM (Dean Inada)
Christoph Splittgerber <alderan!chris at uunet.UU.NET>
troi!allan at uunet.UU.NET (C. Allan Rofer)
ingres.com!jab at lad-shrike.UUCP (jeff bowles)
The fastest solutions fell into three categories:
1) a cryptic one;
2) table look-up and pre-calculate the number of bits in all
possible 256 byte values;
3) for 2's complement signed longs, use the fact that i&(i-1)
removes the lowest bit set from i.
Five solutions based on the above follow.
===============================================================================
#define NELEM(array) (sizeof(array)/sizeof(array[0]))
typedef unsigned long bit_set;
int bit_count();
main()
{
/*
* Some random test data.
*/
static bit_set test[] = {
0x7, 0x40000006, 0x7007, 0xf2f4, 0x1f2001f4, 0x80000000,
0xffffffff, 0xabcabcdd, 0x0, 0x10000000, 0x00070000,
0x11111111, 0x22222222, 0x33333333, 0x44444444
};
int i;
for (i=0; i<NELEM(test); i++)
printf(" 0x%08x has %2d bits on\n",
test[i], bit_count(test[i]));
}
===============================================================================
int bit_count(i)
bit_set i;
{
i = (i & 0x55555555) + ((i>>1) & 0x55555555);
i = (i & 0x33333333) + ((i>>2) & 0x33333333);
i = (i & 0x0F0F0F0F) + ((i>>4) & 0x0F0F0F0F);
return (i % 255);
}
===============================================================================
int bit_count(i)
bit_set i;
{
static int on[256] = {
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};
return on[ i & 0xff] + on[(i >> 8) & 0xff] +
on[(i >> 16) & 0xff] + on[(i >> 24) & 0xff];
}
===============================================================================
int bit_count(i)
bit_set i; /* MUST BE SIGNED!!! */
{
int j = 0;
while( i != 0 ) {
j++;
i = i & (i-1);
}
return j;
}
===============================================================================
static char nbits[] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
int bit_count(i)
bit_set i;
{
union {
bit_set v;
unsigned char c[4];
} t;
t.v = i;
return nbits[t.c[0]] + nbits[t.c[1]] + nbits[t.c[2]] +
nbits[t.c[3]];
}
===============================================================================
static char nbits[] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
int bit_count(i)
bit_set i;
{
unsigned char *p = (unsigned char *)&i;
return nbits[p[0]] + nbits[p[1]] + nbits[p[2]] + nbits[p[3]];
}
===============================================================================
More information about the Comp.lang.c
mailing list