Count Number of Set Bits - Visualization

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given a non-negative integer n, your task is to count the number of set bits (1s) in its binary representation.

For example, the number 13 has binary form 1101, which contains three set bits. The expected output is 3.

Examples❯

n Output Description
0 0 Binary of 0 is 0; no set bits
1 1 Binary of 1 is 1; one set bit
2 1 Binary of 2 is 10; one set bit
3 2 Binary of 3 is 11; two set bits
7 3 Binary of 7 is 111; three set bits
13 3 Binary of 13 is 1101; three set bits
31 5 Binary of 31 is 11111; five set bits
255 8 Binary of 255 is 11111111; eight set bits
1024 1 Binary of 1024 is 10000000000; only one set bit at position 10
4294967295 32 All 32 bits set in unsigned 32-bit integer max value
"" 0 Empty input treated as 0; no set bits

Solution❯

Understanding the Problem

We are given a non-negative integer n. Our goal is to count how many set bits (1s) are present in its binary representation. A set bit is simply a bit with a value of 1.

For example, the number 13 in binary is 1101. It has three set bits: the first, third, and fourth bits from the right.

So, for input n = 13, the output should be 3.

Step-by-Step Solution with Example

step 1: Understand the core idea

We'll use Brian Kernighan’s Algorithm to count the set bits efficiently. This algorithm relies on a clever bit manipulation trick: n & (n - 1) clears the rightmost set bit of n.

Each time we perform this operation, we reduce the number of set bits by one. We repeat the process and count how many times it happens before n becomes zero.

step 2: Initialize variables

We start with count = 0. This will keep track of how many set bits we have encountered so far.

step 3: Work through an example — n = 13

The binary of 13 is 1101.

  • n = 13. Binary: 1101. Count = 0
  • Apply n = n & (n - 1) → n = 13 & 12 → 1101 & 1100 = 1100 → n = 12. Count = 1
  • Apply n = 12 & 11 → 1100 & 1011 = 1000 → n = 8. Count = 2
  • Apply n = 8 & 7 → 1000 & 0111 = 0000 → n = 0. Count = 3

At this point, n becomes 0, so we stop. The final count is 3.

step 4: Return the result

Return count as the final answer. For n = 13, the output is 3.

Edge Cases

  • n = 0: The binary representation is 0. No set bits. Output should be 0.
  • n = 1: Binary is 1. One set bit. Output should be 1.
  • Large n (e.g., 1023): Binary is 1111111111 (10 ones). Output should be 10.

We do not need to handle negative numbers, since the input is guaranteed to be non-negative.

Final Thoughts

This problem introduces a very efficient bit manipulation technique that reduces runtime significantly compared to checking every bit individually. The n & (n - 1) trick ensures that the loop runs only as many times as there are set bits.

It’s a great way for beginners to practice binary representations and understand how to manipulate bits smartly using bitwise operators.

Algorithm Steps❯

  1. Initialize a counter variable count to 0.
  2. While n is not equal to 0:
    • Update n as n & (n - 1). This operation removes the rightmost set bit.
    • Increment count.
  3. Once n becomes 0, return count.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int countSetBits(unsigned int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1); // remove rightmost set bit
        count++;
    }
    return count;
}

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

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)In the best case, the input number n is 0, which immediately satisfies the loop condition and returns the count without any iterations.
Average CaseO(k)The algorithm runs in O(k), where k is the number of set bits in the binary representation of n. This is because each iteration removes one set bit.
Worst CaseO(log n)In the worst case, all bits in n are set (e.g., n = 2^k - 1). Since there are log n bits in total, the loop runs log n times.

Space Complexity❯

O(1)

Explanation: The algorithm uses only a constant amount of extra space — a counter variable and the input integer n. No additional data structures are used.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...