C Program to Count Set Bits in an Integer

To count set bits in C, use a loop with n & 1 to check the last bit and n >>= 1 to shift bits right, incrementing a counter for each set bit.

Examples

Input5

OutputNumber of set bits in 5 is 2

Input15

OutputNumber of set bits in 15 is 4

Input0

OutputNumber of set bits in 0 is 0

How to Think About It

To count set bits, think of the number as a row of bits. Check the last bit using AND with 1. If it is 1, increase the count. Then move to the next bit by shifting the number right by one. Repeat until the number becomes zero.

Algorithm

1

Get the input number.

2

Initialize a count to zero.

3

While the number is not zero:

4

Check if the last bit is 1 using bitwise AND with 1.

5

If yes, increment the count.

6

Shift the number right by one bit.

7

Return the count.

Code

c

#include <stdio.h>

int countSetBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int main() {
    int num = 5;
    printf("Number of set bits in %d is %d\n", num, countSetBits(num));
    return 0;
}

Output

Number of set bits in 5 is 2

Dry Run

Let's trace the number 5 through the code to count set bits.

1

Initial value

n = 5 (binary 0101), count = 0

2

Check last bit

5 & 1 = 1, so count = 1

3

Shift right

n >>= 1 → n = 2 (binary 0010)

4

Check last bit

2 & 1 = 0, count stays 1

5

Shift right

n >>= 1 → n = 1 (binary 0001)

6

Check last bit

1 & 1 = 1, count = 2

7

Shift right

n >>= 1 → n = 0, loop ends

n (decimal)	n (binary)	n & 1	count
5	0101	1	1
2	0010	0	1
1	0001	1	2

Why This Works

Step 1: Check last bit

Using n & 1 isolates the last bit of the number to see if it is set (1).

Step 2: Count increment

If the last bit is 1, we add 1 to the count to keep track of set bits.

Step 3: Shift bits

Right shifting n >>= 1 moves to the next bit by discarding the last bit already counted.

Alternative Approaches

Brian Kernighan's Algorithm

c

#include <stdio.h>

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

int main() {
    int num = 5;
    printf("Number of set bits in %d is %d\n", num, countSetBits(num));
    return 0;
}

This method is faster because it reduces the number of iterations to the number of set bits only.

Using built-in GCC function

c

#include <stdio.h>

int main() {
    int num = 5;
    int count = __builtin_popcount(num);
    printf("Number of set bits in %d is %d\n", num, count);
    return 0;
}

This uses a compiler built-in function for counting bits, which is very efficient but not portable to all compilers.

Complexity: O(k) time, O(1) space

Time Complexity

The loop runs once for each bit in the integer (usually 32 or 64), so it is O(k) where k is the number of bits.

Space Complexity

Only a few variables are used, so space complexity is O(1), constant space.

Which Approach is Fastest?

Brian Kernighan's algorithm is faster when the number has fewer set bits because it loops only as many times as there are set bits.

Approach	Time	Space	Best For
Bitwise check each bit	O(k)	O(1)	Simple and clear for beginners
Brian Kernighan's Algorithm	O(m) where m = set bits	O(1)	Faster for sparse set bits
Built-in function (__builtin_popcount)	O(1)	O(1)	Fastest but compiler-dependent