Bits set in a number

Write Program to count the number of bits set in a number.

Answer:

/**
 * Program to count the number of bits in a program
 * */

#include "stdio.h"
#include "stdlib.h"

void PrintBinary(size_t num)
{
    for( int i = 31; i >=0; --i )
        if ( num & ( 1 << i) )
            printf("1");
        else
            printf("0");
    printf("\n");
}

/**
 * O(n) algorithm, where n is the number of bits set
 * This algorithm works on the fact that when 1 is subtracted,
 * there exists a bit k, below which all the bit places get changed
 * so, num & num-1 will clear all the bits below the bit k.
 * ( to see this enable PrintBinary() function below )
 * */
size_t CountBits(size_t num)
{
    size_t count = 0;
    while (num)
    {
        //PrintBinary(num);
        num &= num-1;
        ++count;
    }
    return count;
}

/**
 * This is O(1) algorithm, but uses a lookup table.
 * Initially fill the lookup table with the bit count
 * then look into it :)
 * we can bring down the memory even further by using a lookup
 * table of size 16 (4 bits instead of 8 )
 * */
size_t lookup[256] = {};
void InitLookup()
{
    for( int i = 0; i <= 0xFF; ++i)
        lookup[i] = CountBits(i);
}

size_t CountBits_O1(size_t num)
{
    size_t count = lookup[num&0xFF] +
        lookup[ (num >> 8) & 0xFF ] +
        lookup[ (num >> 16) & 0xFF ] +
        lookup[ (num >> 24) & 0xFF ];

    return count;
}

int main (int argc, char* argv[])
{
    size_t num = atoi( argv[1] );
    printf("Bit count O(n) %d \n", CountBits(num) );
    InitLookup();
    printf("Bit count O(1) %d \n", CountBits_O1(num) );
    return 0;
}