Log inSign up
easyGeeksforGeeksNot Started

Count Set Bits

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a positive integer n, compute and return the number of set bits (bits with value 1) in its binary representation.

Example 1 · Example 1: Basic Integer:

Input: n = 6
Output: 2
Explanation: Binary representation of 6 is 110, which contains two 1s.

Example 2 · Example 2: Power of Two:

Input: n = 16
Output: 1
Explanation: Binary representation of 16 is 10000, which contains exactly one 1.

Example 3 · Example 3: All Bits Set (7):

Input: n = 7
Output: 3
Explanation: 7 in binary is 111, having 3 set bits.

Constraints:

  • 1 <= n <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master Brian Kernighan's n & (n - 1) bit-clearing mechanism.
  • Understand divide-and-conquer parallel bit counting (SWAR).
  • Benchmark loop-based vs branchless popcount strategies.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Need to count how many bits are 1 in an integer.
  • Hamming weight calculation.
  • Subroutine needed inside parity and subset algorithms.

Algorithmic Decision Tree:

  • Use Brian Kernighan's while (n > 0) { n &= (n - 1); count++; } for concise, optimal code.
  • Use parallel bitmask algorithm or built-ins for high-throughput inner loops.

Connected Patterns:

Counting BitsNumber of 1 BitsPower of Two

1. Bit-by-Bit Shift Scan

Intuition

While n > 0, check if the least significant bit is set using n & 1. If it is, increment count. Then right shift n >>= 1. Repeat until n becomes 0.

When to apply: Basic demonstration of binary representation traversal.

Algorithm

  1. Step 1: Set count = 0.
  2. Step 2: Loop while n > 0.
  3. Step 3: count += (n & 1).
  4. Step 4: n >>= 1.
  5. Step 5: Return count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int countSetBitsBrute(int n) {
6 int count = 0;
7 while (n > 0) {
8 count += (n & 1);
9 n >>= 1;
10 }
11 return count;
12}
13
14int main() {
15 cout << "Brute (6): " << countSetBitsBrute(6) << endl; // 2
16 cout << "Brute (13): " << countSetBitsBrute(13) << endl; // 3
17 return 0;
18}

Time & Space Complexity

  • Time complexity: O(log n)
  • Space complexity: O(1)

2. Brian Kernighan's Algorithm

Intuition

Subtracting 1 from a number flips all bits after the rightmost set bit (including the bit itself). AND-ing n with n - 1 zeroes out that rightmost set bit while preserving all bits to its left. Loop terminates after exactly k iterations.

When to apply: Preferred in most practical code: intuitive, optimal loop count.

Algorithm

  1. Step 1: Set count = 0.
  2. Step 2: Loop while n > 0.
  3. Step 3: n &= (n - 1).
  4. Step 4: count++.
  5. Step 5: Return count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int countSetBitsKernighan(int n) {
6 int count = 0;
7 while (n > 0) {
8 n &= (n - 1);
9 count++;
10 }
11 return count;
12}
13
14int main() {
15 cout << "Kernighan (6): " << countSetBitsKernighan(6) << endl; // 2
16 cout << "Kernighan (13): " << countSetBitsKernighan(13) << endl; // 3
17 return 0;
18}

Time & Space Complexity

  • Time complexity: O(k) where k is the number of set bits
  • Space complexity: O(1)

3. Parallel Bit Counting (Divide & Conquer SWAR)

Intuition

Count bits by grouping them hierarchically into 2-bit, 4-bit, 8-bit, 16-bit, and 32-bit fields using masks 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, and 0x0000FFFF. This executes in exactly 5 constant-time parallel steps without any loop or branch predictions.

When to apply: Optimal for high-performance systems and branch-free computation.

Algorithm

  1. Step 1: n = n - ((n >> 1) & 0x55555555).
  2. Step 2: n = (n & 0x33333333) + ((n >> 2) & 0x33333333).
  3. Step 3: n = (n + (n >> 4)) & 0x0F0F0F0F.
  4. Step 4: n = n + (n >> 8).
  5. Step 5: n = n + (n >> 16).
  6. Step 6: Return n & 0x3F.

Kernighan Algorithm Trace for n = 13

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Iteration 1: n = 13 (1101_2)
Visual state
Values and pointers at this exact step
pointers
S
1100
0
↑ count = 1
Check / comparison
13 & 12 = 12
Decision / next transition
Rightmost bit 0 cleared.
Why this step matters

Iteration 1: n = 13 (1101_2). n - 1 = 12 (1100_2). n & (n - 1) = 12. count = 1.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 int setBits(int n) {
8 unsigned int u = n;
9 u = u - ((u >> 1) & 0x55555555);
10 u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
11 u = (u + (u >> 4)) & 0x0F0F0F0F;
12 u = u + (u >> 8);
13 u = u + (u >> 16);
14 return u & 0x3F;
15 }
16};
17
18int main() {
19 Solution sol;
20 cout << "Optimal SWAR (6): " << sol.setBits(6) << endl; // 2
21 cout << "Optimal SWAR (13): " << sol.setBits(13) << endl; // 3
22 cout << "Optimal SWAR (16): " << sol.setBits(16) << endl; // 1
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(1)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear Bit ScanO(log n)O(1)Loop through bits using (n & 1) and right shift n >>= 1 until n is 0.Inspects up to 32 bits regardless of how many 1s exist.
2.Better — Brian Kernighan's AlgorithmO(k) where k is the number of set bitsO(1)Repeatedly clear the lowest set bit: n = n & (n - 1). Increment count each time.Number of 1 bits.
3.Optimal — Divide-and-Conquer Parallel MaskingOptimalO(1) (5 arithmetic steps)O(1)Count bits in pairs, then nibbles, bytes, and words using fixed masks: 0x55555555, 0x33333333, 0x0F0F0F0F.Arithmetic operations.

Common Pitfalls & Crucial Edge Cases

Infinite loop on negative numbers with arithmetic shift

In while (n > 0) loops, negative numbers in signed types will loop indefinitely or fail if >> propagates sign.

Assuming linear O(n) complexity

The naive bit-by-bit check is O(log n) (or O(32)), NOT O(n).

Not using unsigned types in C++

Signed integer overflow or negative bit manipulation can trigger undefined behavior.

Crucial Edge Cases to Validate:

  • n = 0 — Binary representation has no set bits; loop terminates immediately with count 0.
  • n = 2^k (Power of two) — Has exactly one set bit; algorithm terminates in 1 iteration.
  • n = -1 (All 1s in two's complement) — Contains 32 set bits; requires unsigned handling.
  • n = INT_MIN (0x80000000) — Single set bit at the sign position; must not cause underflow.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the progression: (1) Check lowest bit and shift right 32 times, (2) Brian Kernighan's n & (n - 1), (3) Lookup table / SWAR, (4) Built-in popcount.
  2. Highlight that Brian Kernighan's trick is ideal for sparse numbers (numbers with few set bits).
  3. Write clean, parenthesized code for n = n & (n - 1).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does n & (n - 1) clear the lowest (rightmost) set bit of n?

2.What is the worst-case number of iterations for Brian Kernighan's algorithm on a 32-bit integer?

3.What is the parallel divide-and-conquer approach to counting set bits (SWAR/Hamming weight)?

Back to DSA Sheet