nwagner@ut-emx.uucp (Neal R. Wagner) (09/27/90)
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@IMA.ISC.COM (Karl Heuer)
luciano@canuck.Berkeley.EDU (Luciano Lavagno)
munnari!batserver.cs.uq.oz.au!grue@uunet.UU.NET (Paul Dale)
munnari!wolfen.cc.uow.edu.au!pejn@uunet.UU.NET (Paul Nulsen)
Icarus Sparry <I.Sparry@gdr.bath.ac.uk>
jvl@idca.tds.PHILIPS.nl (J. van Loenen)
Schijf Ardie <schijf@cs.vu.nl>
motcsd!dms!albaugh@apple.com (Mike Albaugh)
calvin!johns@nwnexus.wa.com (John Sahr)
teda!ehp@ames.arc.nasa.gov (Ed Porter)
friedl@mtndew.Tustin.CA.US (Steve Friedl)
dmi@peregrine.COM (Dean Inada)
Christoph Splittgerber <alderan!chris@uunet.UU.NET>
troi!allan@uunet.UU.NET (C. Allan Rofer)
ingres.com!jab@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]];
}
===============================================================================karl@haddock.ima.isc.com (Karl Heuer) (09/29/90)
In article <6476@wolfen.cc.uow.oz> pejn@wolfen.cc.uow.oz (Paul Nulsen) writes: >nwagner@ut-emx.uucp (Neal R. Wagner) writes: > The fastest solutions fell into three categories: > i = (i & 0x55555555) + ((i>>1) & 0x55555555); > i = (i & 0x33333333) + ((i>>2) & 0x33333333); > i = (i & 0x0F0F0F0F) + ((i>>4) & 0x0F0F0F0F); > return (i % 255); > >Too cryptic I fear. This will only count the bottom 8 bits (try it on >0x101). I did; works fine. I think you misread the last expression as "i & 255" or "i % 256" when it's actually "i % 255 /* casting out 255s */". Your suggestion of adding two more folds may indeed be useful, though, if "%" is a sufficiently expensive operation. (Somebody else suggested that the "%" operation can be eliminated in favor of a loop. This isn't necessary, since in either the %63 or %255 case the algorithm can be extended by another step or two to yield the complete answer; the only reason for using mod is to bum a few instructions. And the whole point of the exercise was to get rid of the loop.) Karl W. Z. Heuer (karl@kelp.ima.isc.com or ima!kelp!karl), The Walking Lint