Exercise 2.09

Page 51

In a two's complement number system, x &= (x-1) deletes the rightmost 1-bit in x. Explain why. Use this observation to write a faster version of bitcount.

#include <limits.h>
#include <stdio.h>

/* Subtracting 1 from a binary number has the effect of inverting all the bits up to and
 * including the first 1-bit. ANDing the inverted with the original will ensure all bits
 * up to the first 1-bit are 0. */

int bitcount(unsigned x);

int main()
{
	printf("%d\n", bitcount(0b000));
}

int bitcount(unsigned x)
{
	int count = 0;
	while (x &= (x - 1)) {
		count++;
	}
	return count ? count + 1 : count;
}