Count Set Bits in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>

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

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

C Output

Number of set bits in 13: 3

C++ Program

#include <iostream>
using namespace std;

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

int main() {
    unsigned int num = 29;
    cout << "Number of set bits in " << num << ": " << countSetBits(num) << endl;
    return 0;
}

C++ Output

Number of set bits in 29: 4

JAVA Program

public class Main {
    static int countSetBits(int n) {
        if (n == 0) return 0;
        return (n & 1) + countSetBits(n >> 1);
    }

    public static void main(String[] args) {
        int num = 15;
        System.out.println("Number of set bits in " + num + ": " + countSetBits(num));
    }
}

JAVA Output

Number of set bits in 15: 4

Python Program

def count_set_bits(n):
    if n == 0:
        return 0
    return (n & 1) + count_set_bits(n >> 1)

num = 23
print(f"Number of set bits in {num}: {count_set_bits(num)}")

Python Output

Number of set bits in 23: 4

Explanation

Example

Consider the number 13. In binary, it's 1101. That's three ones, so the count of set bits is 3. The recursive function does this by taking the last bit each time (n & 1) and adding it to the count of the rest of the number (n >> 1). It keeps doing this until n is zero.

Real-Life Analogy

Imagine the binary number as a line of switches, such that 1 is "on" and 0 is "off." Set bit counting is equivalent to following the row and counting the number of "on" switches. Recursion here is like saying, "I'll check the first switch, then have someone else check the remaining ones until we get to the end."

Why It Matters

Set bit counting appears in compression algorithms, cryptography, networking, and even graphics processing. Several system-level optimizations rely on having the ability to rapidly count how many bits are set in a number, which may be used to represent flags, permissions, or states.

Learning Insights

This problem teaches how bitwise operations (& and >>) interact with binary data. The (n & 1) trick isolates the least significant bit, while shifting right (n >> 1) discards it for the next recursive call. Understanding this opens the door to many other bit manipulation techniques, like detecting parity or checking power-of-two values.

Interview and Real-World Usage

During interviews, candidates can be requested to solve this recursively as a starting point, then optimize it to O(1) with the help of instructions available in CPUs or lookup tables. Set bit counting finds application in permission systems, bitmasking in game development, error detection codes, and for storing data compactly in practice.

SEO-Friendly Closing

Recursive counting of set bits is one of those timeless bit manipulation problems that enhances binary number comprehension and recursive problem-solving abilities. This method is essential in algorithms, compression, data protection, and system programming, regardless of whether it is programmed in C, C++, Java, or Python. Knowing it preempts coders for coding interviews as well as effective, production-level usage.