Bit counting
Rich Neitzel
thor at stout.ucar.edu
Wed Jan 11 04:56:25 AEST 1989
Recently jim at athsys.uucp (Jim Becker) wrote:
> The problem is the most efficient method to simply count the
>number of on bits in a sixteen bit short. This is a really easy
>exercise, but one that has a variety of different approaches. I would
>be interested in the opinions of programmers out there, an efficient
>algorithm that is understandable.
>
> Assume that this is a basic sample algorithm:
>
> int
> BitCount( num )
> short num;
> {
> int count = 0;
>
> while( num ) {
>
> count += (num & 1);
> num = (num >> 1);
> }
>
> return count;
> }
>
> Is this efficient? Is this understandable? What is a better
>algorithm?
First a comment on this, what I call the 'classical shift' version. As
listed above, it will not function on many cpus, since it uses right
shifts. Since many cpus propagate the high bit, the loop will never
terminate.
Second, I do not consider this to be an efficient algorithm. While it
appears to be good, since it terminates when there are no more set
bits, it does not function well if there are many set bits or the only
set bit is in the last position tested.
A common solution is to use a lookup table and parse the word into
nibbles or bytes. This is faster, but you must be certain that the
table is correct. I do not relish the thought of entering 256 table
entries. Efficiency suffers from the fact that the table lookup
requires pointer indexing.
I have found that the most efficient algorithm is one involving 'bit
pair' addition. Attached are two routines that implement this
algorithm. They rely on 'parallel' addition. The word involved is
added as successively larger bit pairs. Both a 16 bit and 32 bit form
are provided. I have chosen not to attempt to apply it to any other
word lengths. This is because the algorithm is not truely 'portable',
that is, the idea is portable, but the implemenation is dependent on
the word size. The larger the word size the more pairs are involved.
These routines have been tested in two environments. The first was on
a PDP-11 under RSX-11M-Plus and the second on a Motorola MV133 (20 MHz
68020) under VxWorks. In both cases the test routine was the only job.
They easily out performed the other algorithms tested. The completeing
algorithms were the 'classical' shift and nibble lookup tables. The
results were:
Classical shift lut pair addition
RSX 12.3 7.4 4.6
VxWorks 25 12 8
RSX times are seconds/65K iterations, VxWorks times are microseconds
per iterations. The lookup table code would increase in speed if a
byte table were used, but I doubt it would increase enough to beat the
pair addition time.
Supplied here are both the 16 and 32 bit routines, as well as the
classic and lut routines.
---------------------------------------------------------------------
/*
Module: s_bitcnt.c
Author: Richard E. K. Neitzel
revision history
----------------
1.0,9jan89,rekn written
Explanation:
This routine takes an integer and returns the number of bits it contains
which are set. It does this via 'parallel' addition, turning the integer
into sets of bit pairs of increasing size. WARNING! This assumes that
shorts are 16 bits!
*/
int s_bitcnt(word)
short word;
{
register short i, j, k; /* our work area */
if (!word) /* Why bother? */
return(0);
j = word;
k = j & 0x5555; /* Clear every other bit */
j >>= 1; /* Repeat for other bits */
j &= 0x5555;
j += k; /* 1st pairs */
k = j & 0x3333; /* Clear every two bits */
j >>= 2; /* shift and repeat */
j &= 0x3333;
j += k; /* 2nd pairs */
k = j & 0xff; /* Get lower pairs */
j &= 0xff00; /* Get upper pairs */
j >>= 8;
j += k; /* 3rd pairs */
k = j & 0xf; /* Get last pairs */
j >>= 4;
j += k;
return(j); /* bye */
}
---------------------------------------------------------------------
/*
Module: l_bitcnt.c
Author: Richard E. K. Neitzel
revision history
----------------
1.0,9jan89,rekn written
Explanation:
This routine takes an integer and returns the number of bits it contains
which are set. It does this via 'parallel' addition, turning the integer
into sets of bit pairs of increasing size. WARNING! This assumes that
integers are 32 bits!
*/
int l_bitcnt(word)
int word;
{
register int j, k; /* Our work area */
if (!word) /* Why bother? */
return(0);
j = word;
k = j & 0x55555555; /* Clear every other bit */
j >>= 1; /* Do again for cleared bits */
j &= 0x55555555;
j += k; /* 1st pairs done */
k = j & 0x33333333; /* Clear every two bits */
j >>= 2;
j &= 0x33333333;
j += k; /* 2nd pairs done */
k = j & 0xffff; /* Only need last 4 sets */
j &= 0xffff0000; /* and top 4 here */
j = j >> 16; /* ready - */
j += k; /* add 3rd pairs */
k = j & 0xf0f; /* Clear bits */
j >>= 4; /* Repeat */
j &= 0xf0f;
j += k; /* add 4th pairs */
k = j & 0xff; /* Now add the 8 bit pairs */
j >>= 8;
j += k;
return(j); /* bye */
}
---------------------------------------------------------------------
int bitCount( num )
short num;
{
register short count = 0;
register short tmp;
tmp = num;
while(tmp) /* Note fix to avoid looping forever */
{
count += (tmp & 0x8000);
tmp <<= 1;
}
return(count);
}
---------------------------------------------------------------------
short lut[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
int luts(word)
short word;
{
register short j, k,l;
if (!word)
return(0);
j = word;
k = j & 0xf;
l += lut[k];
j >>= 4;
k = j & 0xf;
l += lut[k];
j >>= 4;
k = j & 0xf;
l += lut[k];
j >>= 4;
k = j & 0xf;
l += lut[k];
return(l);
}
-------------------------------------------------------------------------------
Richard Neitzel
National Center For Atmospheric Research
Box 3000
Boulder, CO 80307-3000
303-497-2057
thor at thor.ucar.edu
Torren med sitt skjegg Thor with the beard
lokkar borni under sole-vegg calls the children to the sunny wall
Gjo'i med sitt shinn Gjo with the pelts
jagar borni inn. chases the children in.
-------------------------------------------------------------------------------
More information about the Comp.lang.c
mailing list