In C programming, counting set bits is the process of determining the number of bits that are set to 1 in a binary number. This operation is useful in various applications including network programming, error detection, and cryptography.

In this article, we will learn how to count the number of set bits (1s) in a binary number in C. We will also look at different methods to achieve this.

How to Count Set Bits in C?

Counting set bits involves determining how many 1s are present in the binary representation of a number. There are several methods to achieve this in C.

Method 1: Using Bitwise AND and Shift Operator

In this method, we repeatedly check each bit of the number using the bitwise AND operator and right shift the number to move to the next bit.

Example:

Input:
binary_number: 01100111

Output:
Number of set bits: 5

C Program to Count Set Bits using Bitwise AND and Shift Operator

#include <stdio.h>

int countSetBits(unsigned int num)
{
    int count = 0;
    while (num) {
        count += num & 1; // Add the least significant bit
        num >>= 1; // Right shift the number
    }
    return count;
}

int main()
{
    unsigned int num = 103; // Binary: 01100111

    // Count the number of set bits
    int result = countSetBits(num);

    // Print the result
    printf("Number of set bits: %d\n", result);

    return 0;
}

Number of set bits: 5

Time Complexity: O(log⁡n)
Space Complexity: O(1)

Method 2: Using Brian Kernighan’s Algorithm

This efficient method reduces the number of iterations by turning off the rightmost set bit in each iteration.

Example:

Input:
binary_number: 01100111

Output:
Number of set bits: 5

C Program to Count Set Bits using Brian Kernighan’s Algorithm

#include <stdio.h>

int countSetBits(unsigned int num)
{
    int count = 0;
    while (num) {
        num &= (num - 1); // Turn off the rightmost set bit
        count++;
    }
    return count;
}

int main()
{
    unsigned int num = 103; // Binary: 01100111

    // Count the number of set bits
    int result = countSetBits(num);

    // Print the result
    printf("Number of set bits: %d\n", result);

    return 0;
}

Number of set bits: 5

Time Complexity: O(k), where k is the number of set bits.

Space Complexity: O(1)

Method 3: Using Lookup Table

This method precomputes the number of set bits for all possible bytes (0 to 255) and uses it for fast lookups.

Example:

Input:
binary_number: 01100111

Output:
Number of set bits: 5

C Program to Count Set Bits using Lookup Table

#include <stdio.h>

// Lookup table to count set bits in a byte
unsigned char bitsSetTable256[256];

// Function to initialize the lookup table
void initialize()
{
    bitsSetTable256[0] = 0;
    for (int i = 1; i < 256; i++) {
        bitsSetTable256[i]
            = (i & 1) + bitsSetTable256[i / 2];
    }
}

int countSetBits(unsigned int num)
{
    return bitsSetTable256[num & 0xFF]
           + bitsSetTable256[(num >> 8) & 0xFF]
           + bitsSetTable256[(num >> 16) & 0xFF]
           + bitsSetTable256[(num >> 24) & 0xFF];
}

int main()
{
    initialize(); // Initialize the lookup table

    unsigned int num = 103; // Binary: 01100111

    // Count the number of set bits
    int result = countSetBits(num);

    // Print the result
    printf("Number of set bits: %d\n", result);

    return 0;
}

Number of set bits: 5

Time Complexity: O(1)

Space Complexity: O(1) (for the lookup table of size 256 bytes)

Conclusion

Counting set bits is a fundamental operation in many applications. We have explored three different methods to count set bits in C: using bitwise AND and shift operator, Brian Kernighan’s algorithm, and a lookup table. Each method has its own advantages and can be chosen based on the specific requirements of the application.