Xref: utzoo comp.lang.c:15364 comp.std.c:658
Path: utzoo!attcan!uunet!ubvax!ardent!worley
From: worley@ardent.UUCP (John Worley)
Newsgroups: comp.lang.c,comp.std.c
Subject: Re: BIT Counting: C programming problem
Message-ID: <1553@ardent.UUCP>
Date: 10 Jan 89 18:58:19 GMT
References: <225@tityus.UUCP>
Organization: Dana Computer, Inc., Sunnyvale, CA
Lines: 90

> 	The problem is the most efficient method to simply count the
> number of on bits in a sixteen bit short. ...
> 
> 		int	
> 		BitCount( num )
> 		short	num;
> 
> -Jim Becker 	...!sun!athsys!jim

    First, the parameter num must be declared unsigned.  Otherwise, the high
order bit is propagated in the shift; if set, this is an infinite loop.  Also,
since parameters as passed as ints, there may be extra high order bits set
when num is negative.

    I prefer the following algorithm:

		/*  Count the number of bits set in num.  While num is not
		 *  zero, increment the count and turn off the lowest bit
		 *  set.
		 */

		int
		BitCout(num)
			unsigned short num;
		{
			int cnt;

			for (cnt = 0; num != 0; ++cnt)
				num &= num - 1;

			return (cnt);
		}

    For N bit parameters, there will be on average N/2 iterrations if the
numbers are randomly distributed; the simple mask and shift will need an
average of N - 1 iterations (proofs on request).  You could speed up the
shift and mask scheme by looking at more than one bit each iteration:

		int
		BitCount(num)
			unsigned short num;
		{
			static int value2bits[] = {
				0, 1, 1, 2,
				1, 2, 2, 3,
				1, 2, 2, 3,
				2, 3, 3, 4
			};

			int cnt;

			for (cnt = 0; num != 0; num >>= 4)
				cnt += value2bits[num & 0xf];

			return (cnt);
		}

    However, this requires extra data space, an index computation and a
memory load for each iteration, where as the previous approaches could all
run in registers.  For certain architectures and applications, however,
it could run faster.

    For the fans (like me) of falling through in switch statements:

		int
		BitCount(num)
			unsigned short num;
		{
			int cnt;

			for (cnt = 0; num != 0; num >>= 2)
				switch (num & 0x3) {
				case 3:
					++cnt;

				case 2:
				case 1:
					++cnt;

				case 0:
					break;
				}

			return (cnt);
		}

					Regards,
					John Worley
					Ardent Computer
					uunet!ardent!worley