ansi_c_pg48_ch02_ex09.c

/*
 * Exercise 2-9.
 * 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 <stdio.h>


/*
 * In a two's complement  numbering system x &= (x - 1) unsets the right most 1
 * bit to zero. This can be explained in two setps
 *
 * a- (x - 1) unsets the right most bit and inverts all the bit in its right.
 * For example 8 - 1 = 7
 *
 *
 *                     __ the right most 1 bit
 *                    |
 *                    |
 * 			8 = 0b00001000
 *                     |-|
 *                      |
 *                       - The bits in it's right
 *
 *
 * Unsetting the right most 1 bit and inverting the bits in its right will give
 *              0b00000111 = 7
 * b- Anding this with x will unset the right most 1 bit. That should be obvious
 * now :)
 */


int
bitcount(unsigned int x) {
	unsigned int ret = 0;

	while (x) {
		x &= (x - 1);
		ret++;
	}

	return ret;
}
int
main() {
	unsigned int x = 14;
	printf ("bitcount(%X) = %d\n",x, bitcount(x));
}