Count Set Bits of a Number in C

A number consists of multiple bits in its binary representation. For example, an integer would have 32 bits and a long would have 64 bits on 64-bit system. Bit values could either be 0 (not set) or 1 (set).

From the diagram above, we can see that the binary representation of 2392 has 5 set bits.

Here we’ll see how to write C program to count the set bits of a number.

Checking All Bits

We can check all bits of a number in a loop and increment the counter if the a particular bit is 1 (set).

Logic

1. If the bitwise AND (&) operation between the number and 1 is 1, then increment the set bit count.
2. Right shift the number by 1, and repeat step 1 as the many times as the size of the number in bits.

The Program

#include <stdio.h>

int count_set_bits(unsigned int n) {
  int size, count = 0;
  
  size = sizeof(unsigned int) * 8;
  
  while(size--) {
    count += n & 0x01;
    n = n >> 1;
  }
  
  return count;
}

void binary(unsigned int n)
{
    if(n > 0)
    {
        binary(n/2);
        printf("%d", n%2);
    }
}

void main()
{
    unsigned int num, result;

    printf("Enter an integer: ");
    scanf("%d", &num);

    printf("Binary of %d: ", num);
    binary(num);
    
    result = count_set_bits(num);
    
    printf("\nNumber of set bits in %d is %d.\n", num, result);
}

This program first takes an integer as input and prints its binary representation. It calls the count_set_bits() function to count the set bits in the number and print that.

Here is the output.

Recursive version

We can write this count_set_bits() as a recursive function.

1. If the input number n is 0, return 0. There is no set bits.
2. Get the set bit counts of (n >> 1) calling the same function recursively. The result would be the returned value plus 1 if the least significant bit of the input is 1, i.e. (n & 0x01) is 1.

int count_set_bits(unsigned int n) {
  
  if (n == 0) return 0;
  
  return count_set_bits(n >> 1) + (n & 0x01);
}

Using Brian Kernighan’s Algorithm

In the previous section’s solution we iterated as many times as the number of bits in the number. But if we apply Brian Kernighan’s algorithm, we can get the result with less number of iterations.

In this article, I discussion about the Brian Kernighan’s algorithm in detail. Here we’ll see the count_set_bits() function’s implementation.

Non-recursive Version

int count_set_bits(unsigned int n) {
  int count = 0;
  while(n) {
    count++;
    n = n & (n-1);
  }
  
  return count;
}

Recursive Version

int count_set_bits(unsigned int n) {
  unsigned int res;
  
  if (n == 0) return 0;
  
  res = n & (n-1);
  if (res == 0) return 1;
  
  return count_set_bits(res) + 1;
}

If you also want to contribute, click here.