beautiful_code__ch10__warren__pop_count.c

#include <stdio.h>

/* Introduction

 Code for "Beautiful Code" Chapter 10, "The Quest for an Accelerated 
  Population Count" by Henry Warren.
 The function pop*() counts the number of 1 bits in a word
 Used in set operations represented as bit arrays (e.g. DB bit indexes)
  among other uses discussed in the book.
 This code just makes working versions of the examples, so one can step
  through in a debugger to better understand them.
 The code uses bit operations and tricks not intuitive/arcane to the average
  programmer who doesn't do that sort of programming regularly, so seeing
  how the code works step by step is very helpful
*/

/* "Beautiful Code" p. 148
 
 Notes
 -----
 - First naive version of population count
 - From the book: "Here word is an unsigned int so the right-shift is with 0-fill."
 - Assumes 4-byte (32-bit) word size, i.e. - 32-bit machine architecture
 
 Explanation of Algorithm
 ------------------------
 - right shift moves all bits to the right by one position, fills with 0
    in left-most position
 - that is, right shift pops off the least significant bit (left-most), which
    is the first bit, equaling 0 or 1
 - so, testing (x & 1) is testing whether the *current* LSB is 0 or 1
 - if current LSB is 1, we increment count (because detected a bit that is set)
 - and *since we are right-shifting*, we are moving all the bits in the word
    over one at a time into this first LSB position, then testing them
 - so, the result is to move each of the 32 bits in the word through the LSB
    position one at a time, test each one, and increment 'pop' for each set bit
 */
int pop1(unsigned int x)
{
	int pop = 0;
	for (int i = 0; i < 32; i++)
	{
		if (x & 1) pop = pop + 1;
		x = x >> 1;
	}
	return pop;
}

/* "Beautiful Code" p. 148
 
 Notes
 -----
 - Improved version of pop1()
 - Removes loop test altogether by observing that x must go to 0 after 32
    iterations because we are right-shifting and left-filling with 0's
 - Removes if test becuase right-shift returns value of first bit (LSB), which
    is of course 0 or 1, so we can just add this directly to 'pop' and it
    adds one to that value only if the bit is set
 */
int pop2(unsigned int x)
{
	int pop = 0;
	while(x)
	{
		pop = pop + (x & 1);
		x = x >> 1;
	}
	return pop;
}

/* "Beautiful Code" p. 148-9
 
 Notes
 -----
 - Optimized version of pop2()
 - Removes shift operation by using a bitwise trick, which is that x & (x-1)
    is x with it's least significant 1-bit turned off.  This is because if LSB
    is first bit, then it goes from 1 to 0.  If it's already 0 then x is even
	and so the next lowest bit that is set must go from 1 to 0 while the 0th bit
    will go from 0 to 1 because the even number minus 1 must become odd.
 - Notice that now the algo just increments pop until x is 0; this is because
    each step now removes the next lowest set bit, whatever position it's in --
    so the loop only occurs as many times as there are set bits in x
 */
int pop3(unsigned int x)
{
	int pop = 0;
	while(x)
	{
		pop = pop + 1;
		x = x & (x - 1);
	}
	return pop;
}


void test_pop1()
{
	/* setup step, init testing vars */
    int test_num = 0;
	unsigned int x = 0;  /* word which has 1-bits being counted */
	int expected = 0;
	int actual = 0;
	
	printf("\n\nTesting pop1()\n\n");
	
	/* x = 0*/
    test_num = 0;
	x = 0;
	expected = 0;
	actual = pop1(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
	
	/* x = 1*/
    test_num = 1;
	x = 1;
	expected = 1;
	actual = pop1(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
	
	/* x = 2*/
    test_num = 2;
	x = 2;
	expected = 1;
	actual = pop1(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
    
	/* x = 3*/
    test_num = 3;
	x = 3;
	expected = 2;
	actual = pop1(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
	
	/* x = 64*/
    test_num = 4;
	x = 64;
	expected = 1;
	actual = pop1(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
	
	/* x = 255*/
    test_num = 5;
	x = 255;
	expected = 8;
	actual = pop1(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
}

void test_pop2()
{
	/* setup step, init testing vars */
    int test_num = 0;
	unsigned int x = 0;  /* word which has 1-bits being counted */
	int expected = 0;
	int actual = 0;

	printf("\nTesting pop2()\n\n");	
	
	/* x = 0*/
    test_num = 0;
	x = 0;
	expected = 0;
	actual = pop2(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
	
	/* x = 1*/
    test_num = 1;
	x = 1;
	expected = 1;
	actual = pop2(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
	
	/* x = 2*/
    test_num = 2;
	x = 2;
	expected = 1;
	actual = pop2(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
    
	/* x = 3*/
    test_num = 3;
	x = 3;
	expected = 2;
	actual = pop2(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
	
	/* x = 64*/
    test_num = 4;
	x = 64;
	expected = 1;
	actual = pop2(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
	
	/* x = 255*/
    test_num = 5;
	x = 255;
	expected = 8;
	actual = pop2(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
}

void test_pop3()
{
	/* setup step, init testing vars */
    int test_num = 0;
	unsigned int x = 0;  /* word which has 1-bits being counted */
	int expected = 0;
	int actual = 0;
	
	printf("\nTesting pop3()\n\n");	
	
	/* x = 0*/
    test_num = 0;
	x = 0;
	expected = 0;
	actual = pop3(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
	
	/* x = 1*/
    test_num = 1;
	x = 1;
	expected = 1;
	actual = pop3(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
	
	/* x = 2*/
    test_num = 2;
	x = 2;
	expected = 1;
	actual = pop3(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
    
	/* x = 3*/
    test_num = 3;
	x = 3;
	expected = 2;
	actual = pop3(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
	
	/* x = 64*/
    test_num = 4;
	x = 64;
	expected = 1;
	actual = pop3(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
	
	/* x = 255*/
    test_num = 5;
	x = 255;
	expected = 8;
	actual = pop3(x);
	printf("Test %d  result %d\n", test_num, (expected == actual));
}

int main (int argc, const char * argv[]) {

	test_pop1();
	test_pop2();
	test_pop3();	
	return 0;
}