Counting Bits in C

Presenting a nice way of counting the ‘1’ bits of a given integer in C, sacrificing some memory for speed. Comparison with the simple bit-shifting bit by bit method provided.

I would like to quickly share a nice algorithm that I saw which counts the number of ‘1’ bits that a given integer has. So simply a function so that the program below would print “Number of ON bits of 8895 is 9”.

int main()
{
	int num = 8895;
	printf("Number of ON bits of %d is %d\n",num,countBits(num));
	return 0;
}

The simple way to accomplish this would be to go through each bit of the integer and check if it is zero or one. Something like below.

//A simple way to count the '1' bits of an integer
int countBits_simple(int num)
{
	int result = 0;
	//as long as the number is not zero
	while(num != 0)
	{
		//if this bit is 1 increase the counter
		if(num&0x1)		
			result++;
		num=num>>1;//and always keep shifting right
	}
	return result;
}

This algorithm has O(n) complexity as far as comparisons are concerned with n being the number of bits that the integer has. If we are prepared to sacrifice some memory, this can happen a lot faster. We can maintain a precomputed array of the ‘1’ bits count of some numbers. For simplicity’s sake let’s say that we will keep an array of 4-bit numbers count. So we will have something like below:

//the array of precomputed counts of '1' bits for the numbers 0 to 15
static char precomputed[16] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
 
//using a precomputed array to count the '1' bits of an integer
int countBits(int num)
{
	int result=0;
	//as long as the number is not zero
	while(num != 0)
	{//check every 4 bits
		result+=precomputed[num&0xF];
		num=num>>4;//and move right by 4 bits
	}
	return result;
}

In the above we have an array with precomputed counts of ‘1’ bits for numbers zero to fifteen(4 bit numbers). This is used in order to calculate how many ‘1’ bits every 4 bits of the number contain. This way we can read through the integer 4 times as fast, since we simply read every 4 bits. So in the end the complexity of the algorithm is O(n/4) where n is the number of bits of the given integer.

This method can of course be taken a step further by simply keeping a bigger precomputed array. If for example we had an array with size 255 we could hold the count of ‘1’ bits for all possible numbers a byte can hold. This way we could go through the given integer byte by byte and end up with an algorithm of complexity O(n/8).

So there it is. A kind of smarter way to count the ‘1’ bits of a given integer as long as you are prepared to do some memory/speed tradeoffs.

If the post caught your interest and you love C programming in general why not check my work in the Refu Library? It currently needs more contributors and people who are able and willing to provide feedback! You could be one of them 🙂

Elegant Power Set Calculation Algorithm

A very easy to understand and elegant algorithm to calculate the powerset of a given set of numbers. It is based on the properties of binary numbers. An example in C code along with explanation is provided.

Hello all. While looking around for algorithms to calculate the power set of a set I came across the usual recursive algorithm which tries to exhaust all the probable sets and also its iterative version which does pretty much the same thing. But then I saw an algorithm that calculates the power set that is both simple to understand, fast and elegant and I felt the need to write about it and share a sample C implementation.

But first of all what exactly is a power set? For the whole explanation please visit the Wikipedia page. In short, the Power Set of a set S is all the possible subsets of that set including itself and the empty set. For example the power set of S = {3,4,5} is P(S) = { {3,4,5} , {3,4}, {4,5}, {3,5}, {3}, {4}, {5}, {∅} }. The number of subsets of the power set is given by 2s where s is the number of elements in S. s is also called the cardinality of S.

The algorithm works in a very simple and elegant way. You represent the original set S with a string of bits all with a value of 1. For the above example of S that number would be what? 2s-1 = 23-1 = 7. In binary seven is 111 as we can see from the figure below.

Binary representation of 7
Binary representation of 7

Now just picture that each bit of this number is associated with one element of the original set. So in our example the first bit would be associated with 3, the second bit with 4 and so on. Now with a simple iteration from 0 to this number (7 in our case) we can iterate through all the possible permutations of the set by taking the binary number representation at each iteration and matching its bits to the existence(or not) of the corresponding elements of the set. Since pretty pictures are much better than words I made the following diagram to illustrate the algorithm in a graphic manner.

Binary Power Set Representation
Binary Power Set Representation

And just like that we can obtain the power set of any given set.
Let’s see a quick implementation that I cooked up in C.

#include <math.h>
#include <stdio.h>
 
//an example set
int A[] = {1, 5, 7 , 8, 2, 10, 12};
 
//The function to calculate the subset of the original set
//corresponding to the number given at num
void printSet(unsigned int num,int* arr,unsigned int size)
{
    unsigned int i;
    printf("\t{");
    //for each bit
    for(i=0;i<sizeof(unsigned int)*8;i++)
    {
        if(num&(unsigned int)0x1)//if it's ON print the corresponding value
        {
            if(num >>1 ==0)//if it's the last ON bit
            {//print without comma and terminate the loop
                printf("%d",arr[i]);
                break;
            }
            else
                printf("%d,",arr[i]);
        }
        num = num>>1;//keep shifting right to get more bits
    }
    printf("}\n");
}
 
int main()
{
    unsigned int size,i,n;
 
    //get the cardinality of the set and check
    //if it can be represented by an unsigned int
    size = sizeof(A)/sizeof(int);
    if(size > sizeof(unsigned int)*8)
    {
        printf("The given set can not be represented by the size\
         of unsigned int in the system\nQuitting ...");
        return -1;
    }
    //get the number until which we need to iterate
    n = pow(2,size)-1;
 
    //calculate and print the powerset
    printf("The powerset of {");
    for(i=0;i< size-1; i ++)
        printf("%d,",A[i]);
    printf("%d} is:\n{\n",A[size-1]);
    for(i=0;i<=n;i++)
        printSet(i,A,size);
    printf("}\n");
 
    return 0;
}

The above is just a minimal example to demonstrate the algorithm. It should work in most C compilers, including GCC and MSVC and give the following output:

The powerset of {1,5,7,8,2,10,12} is:
{
{}
{1}
{5}
{1,5}
{7}
{1,7}
{5,7}
{1,5,7}
{8}
{1,8}
{5,8}
{1,5,8}
{7,8}
{1,7,8}
{5,7,8}
{1,5,7,8}
{2}
{1,2}
{5,2}
{1,5,2}
{7,2}
{1,7,2}
{5,7,2}
{1,5,7,2}
{8,2}
{1,8,2}
{5,8,2}
{1,5,8,2}
{7,8,2}
{1,7,8,2}
{5,7,8,2}
{1,5,7,8,2}
{10}
{1,10}
{5,10}
{1,5,10}
{7,10}
{1,7,10}
{5,7,10}
{1,5,7,10}
{8,10}
{1,8,10}
{5,8,10}
{1,5,8,10}
{7,8,10}
{1,7,8,10}
{5,7,8,10}
{1,5,7,8,10}
{2,10}
{1,2,10}
{5,2,10}
{1,5,2,10}
{7,2,10}
{1,7,2,10}
{5,7,2,10}
{1,5,7,2,10}
{8,2,10}
{1,8,2,10}
{5,8,2,10}
{1,5,8,2,10}
{7,8,2,10}
{1,7,8,2,10}
{5,7,8,2,10}
{1,5,7,8,2,10}
{12}
{1,12}
{5,12}
{1,5,12}
{7,12}
{1,7,12}
{5,7,12}
{1,5,7,12}
{8,12}
{1,8,12}
{5,8,12}
{1,5,8,12}
{7,8,12}
{1,7,8,12}
{5,7,8,12}
{1,5,7,8,12}
{2,12}
{1,2,12}
{5,2,12}
{1,5,2,12}
{7,2,12}
{1,7,2,12}
{5,7,2,12}
{1,5,7,2,12}
{8,2,12}
{1,8,2,12}
{5,8,2,12}
{1,5,8,2,12}
{7,8,2,12}
{1,7,8,2,12}
{5,7,8,2,12}
{1,5,7,8,2,12}
{10,12}
{1,10,12}
{5,10,12}
{1,5,10,12}
{7,10,12}
{1,7,10,12}
{5,7,10,12}
{1,5,7,10,12}
{8,10,12}
{1,8,10,12}
{5,8,10,12}
{1,5,8,10,12}
{7,8,10,12}
{1,7,8,10,12}
{5,7,8,10,12}
{1,5,7,8,10,12}
{2,10,12}
{1,2,10,12}
{5,2,10,12}
{1,5,2,10,12}
{7,2,10,12}
{1,7,2,10,12}
{5,7,2,10,12}
{1,5,7,2,10,12}
{8,2,10,12}
{1,8,2,10,12}
{5,8,2,10,12}
{1,5,8,2,10,12}
{7,8,2,10,12}
{1,7,8,2,10,12}
{5,7,8,2,10,12}
{1,5,7,8,2,10,12}
}

The limitation above is the size of the unsigned int in the system. If say that size is 32 then the above will only work for sets with cardinality of up to 32. This is a problem that is easy to overcome. Just use bigger integers. For example if you use a compiler that follows the C99 standard then you can include the <stdint.h> header and use uint64_t type instead of the unsigned int to be able to utilize the algorithm for sets with cardinality of up to 64. For bigger sets you would have to use some big integer library or just code it yourself.

Well that’s it. I hope some of you also find this algorithm to be elegant and nice and I wish it has been helpful for you. As always any comments, corrections and feedback are more than welcome. Please use the form below.

Additionally if the post caught your interest and you love C programming in general why not check my work in the Refu Library? It currently needs more contributors and people who are able and willing to provide feedback! You could be one of them 🙂