Write a C program to count number of set bits in an integer.

• Iterative Method to Count Set Bits
• Count Set Bits by Brian Kernighan's Algorithm
• Count Set Bits by Divide and Conquer Strategy
• Count Set Bits by Lookup Table

To count number of 1's or set bits in an unsigned integer, there could exist more than one solution. This is commonly asked interview question. If you have heard of Hamming weight of a string then you perhaps know that it is the number of symbols that are different from the zero-symbol of the alphabet used. For a typical case consider a string of bits and count the number of 1's in the string. In this binary case, it is also called the population count. It is the digit sum of the binary representation of a given number. Here, we will look into the available solutions and will compare there running time to pick the fastest one.

In order to count number of ones in an unsigned integer we will develop a C function having signature int countSetBits(unsigned int n). This function will receive an unsigned int and return the sum of ones present in the binary string. For example, if we input 17 to countSetBits, it will return 2 because binary of 17 is 10001 that contains two 1's.

Iterative Method to Count Set Bits

The iterative approach requires one iteration per bit. It runs utmost sizeof(int) number of times. Iteration terminates when no more bits are set. In worst case, on a 32-bit word with only the most significant bit set, it will loop through 32 iterations. This solution is the simplest one and useful if 1's are sparse and among the least significant bits.

C program: iterative approach of counting set bits in an unsigned integer

/* Iterative approach of counting set bits*/
#include <stdio.h>
#include <string.h>
 
int countSetBits(unsigned int n)
{
  unsigned int c; // the total bits set in n
  for (c = 0; n; n >>= 1)
  {
    c += n & 1;
  }
  return c;
}
 
int main(void)
{
  unsigned int n;
  printf("Enter a positive integer: ");
  scanf("%u", &n);
  printf("%d\n", countSetBits(n));
}
 

Count Set Bits by Brian Kernighan's Algorithm

Brian Kernighan's algorithm every time performs a bitwise AND operation between inputted integer n and n-1 and keep c incrementing by 1 until n becomes zero. This solution iterates the number of set bits times through the loop. For example, if we input 17 then loop will iterate only two times, whereas in former solution (iterative method to count set bits) it would iterate 5 times.

/* Brian Kernighan's algorithm  of counting set bits*/
#include <stdio.h>
#include <string.h>
 
int countSetBits(unsigned int n)
{
  unsigned int c; // the total bits set in n
  for (c = 0; n; n = n & (n-1))
  {
    c++;
  }
  return c;
}
 
int main(void)
{
  unsigned int n;
  printf("Enter a positive integer: ");
  scanf("%u", &n);
  printf("%d\n", countSetBits(n));
}
 

Count Set Bits by Divide and Conquer Strategy

By divide and conquer technique of counting set bits we have to first set each 2-bit field equal to the sum of the two single bits that were originally in the field, and then sum adjacent 2-bit fields, putting the results in each 4-bit field, and so on. The method is illustrated in Figure 1, in which the first row shows a computer word whose 1-bits are to be summed, and the last row shows the result (decimal 6).

Following C program implements the divide and conquer strategy of counting set bits in a binary string.

C program: Counting set bits by divide and conquer strategy

/* C program: Counting set bits by divide and conquer strategy */
#include <stdio.h>
#include <string.h>
 
int countSetBits(unsigned int n)
{
  n = n - ((n >> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
  n = (n + (n >> 4)) & 0x0F0F0F0F;
  n = n + (n >> 8);
  n = n + (n >> 16);
  return n & 0x0000003F;
}
 
int main(void)
{
  unsigned int n;
  printf("Enter a positive integer: ");
  scanf("%u", &n);
  printf("%d\n", countSetBits(n));
}
 

In the above mentioned solution of counting set bits in a binary string, the ultimate small problems (summing adjacent bits) can all be done in parallel, and combining adjacent sums can also be done in parallel in a fixed number of steps at each stage. The result is an algorithm that can be executed in log₂⁽³²⁾ = 5 steps.

Counting Set Bits by Lookup Table

To count set bits by lookup table we construct a static table, lookup_t having 256 entries giving the number of set bits in each possible byte value (e.g. 0 = 0, 1 = 1, 2 = 1, 3 = 2, and so on). Then use this table to find the number of ones in each byte of the integer and sum them to get total number of set bits in an integer. Here, we take the size of integer by sizeof operator and iterates the loop maximum for sizeof(int) times. While counting the set bits we iterate the for loop with i <= sizeof(int) && ncondition. For loop terminates upon either condition becomes false.

/* C program: Counting set bits by lookup table */
#include <stdio.h>
#include <string.h>
 
int countSetBits(unsigned int n)
{
  unsigned char lookup_t[256] = {0}; 
  int i, count = 0;
 
  // generate the lookup table
  for (i = 0; i < 256; i++)
  {
    lookup_t[i] = (i & 1) + lookup_t[i / 2];
  }
 
  /* Get sie of int program by size of operator. 
     It makes the solution consistent for different word sizes */
  for (i = 1; i <= sizeof(int) && n; i++)
  {
    count += lookup_t[n & 255];
    n >>= 8;
  }
 
  return count;
}
 
int main(void)
{
  unsigned int n;
  printf("Enter a positive integer: ");
  scanf("%u", &n);
  printf("Binary of %d has %d set bits.\n", n, countSetBits(n));
}
 
OUTPUT
======
Enter a positive integer: 528977
Binary of 528977 has 6 set bits.
 

As we can see the above program constructs a lookup table lookup_t algorithmically by iterating a for loop 256 times. To generate look up table faster than we created in above program, Hallvard Furuseth suggested the macro compacted table as follows.

static const unsigned char lookup_t[256] =
{
#   define B2(n) n,     n+1,     n+1,     n+2
#   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
    B6(0), B6(1), B6(1), B6(2)
};

Above table lookup_t uses macro definitions to form the table by patterns. They are recursive macros, B6 uses B4 and B4 uses B2. B6(0) will get expanded into B4(0), B4(1), B4(1), B4(2). Then B4(0) will get expanded into 0, 1, 1, 2. By using the above macro compacted table, we can rewrite the above program as follows.

C program: Counting set bits by macro compacted lookup table

/* C program: Counting set bits by lookup table */
#include <stdio.h>
#include <string.h>
 
int countSetBits(unsigned int n)
{
  static const unsigned char lookup_t[256] =
  {
    # define B2(n) n,     n+1,     n+1,     n+2
    # define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
    # define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
      B6(0), B6(1), B6(1), B6(2)
  };
  int i, count = 0;
 
  for (i = 1; i <= sizeof(int) && n; i++)
  {
    count += lookup_t[n & 255];
    n >>= 8;
  }
  return count;
}
 
int main(void)
{
  unsigned int n;
  printf("Enter a positive integer: ");
  scanf("%u", &n);
  printf("Binary of %d has %d set bits.\n", n, countSetBits(n));
}
 
OUTPUT
======
Enter a positive integer: 528977
Binary of 528977 has 6 set bits.
 

Hope you have enjoyed reading C program to count the number of bits set to one in an unsigned integer. Here we counted set bits by Brian Kernighan's Algorithm, divide and conquer technique, and counting set bits by lookup table. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!