Log inSign up
easyLeetCodeNot Started

Number of 1 Bits

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

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

Write a function that takes the binary representation of a positive integer n and returns the number of set bits it has (also known as the Hamming weight).

Follow up: If this function is called many times, how would you optimize it?

Example 1 · Example 1: Standard 32-bit Integer:

Input: n = 11
Output: 3
Explanation: 11 in binary is 00000000000000000000000000001011 (total of three 1s).

Example 2 · Example 2: Power of Two:

Input: n = 128
Output: 1
Explanation: 128 in binary is 10000000, which has only one set bit.

Example 3 · Example 3: Maximum 32-bit Integer with alternating bits:

Input: n = 2147483645
Output: 30
Explanation: Binary representation contains thirty 1-bits.

Constraints:

  • 1 <= n <= 231 - 1

What You'll Learn

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

  • Master the theoretical basis of Brian Kernighan's algorithm.
  • Understand unsigned right shifting across typed languages.
  • Design caching / lookup table architectures for high-throughput popcount workloads.

Pattern Recognition Trigger

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

Signals to Look For:

  • Hamming weight of a 32-bit integer.
  • Count 1 bits with sub-linear iterations.
  • High-throughput multi-query optimization.

Algorithmic Decision Tree:

  • Use while (n != 0) { n &= (n - 1); count++; } for single queries.
  • Use precomputed 8-bit table or built-ins for batch streams.

Connected Patterns:

Count Set BitsCounting BitsPower of Two

1. 32-Bit Fixed Position Check

Intuition

Initialize count = 0. Loop i from 0 to 31. If (n >> i) & 1 == 1, increment count.

When to apply: Baseline comparison.

Algorithm

  1. Step 1: Initialize count = 0.
  2. Step 2: Loop i from 0 to 31.
  3. Step 3: If ((n >> i) & 1) != 0, count++.
  4. Step 4: Return count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int hammingWeightBrute(uint32_t n) {
6 int count = 0;
7 for (int i = 0; i < 32; ++i) {
8 if ((n >> i) & 1) count++;
9 }
10 return count;
11}
12
13int main() {
14 cout << "Brute (11): " << hammingWeightBrute(11) << endl; // 3
15 cout << "Brute (128): " << hammingWeightBrute(128) << endl; // 1
16 return 0;
17}

Time & Space Complexity

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

2. Unsigned Right Shift Scan

Intuition

Loop while n > 0. Add n & 1 to count, then perform logical unsigned shift n >>>= 1.

When to apply: When input magnitude is frequently small.

Algorithm

  1. Step 1: Set count = 0.
  2. Step 2: While n != 0: count += (n & 1), n >>>= 1.
  3. Step 3: Return count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int hammingWeightShift(uint32_t 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 << "Shift (11): " << hammingWeightShift(11) << endl; // 3
16 return 0;
17}

Time & Space Complexity

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

3. Brian Kernighan's Algorithm

Intuition

Each iteration of n &= (n - 1) clears the least significant 1-bit. The loop terminates in exactly k iterations, where k is the number of 1-bits in n.

When to apply: Optimal canonical solution for Hamming weight.

Algorithm

  1. Step 1: Initialize count = 0.
  2. Step 2: While n != 0: n &= (n - 1), count++.
  3. Step 3: Return count.

Kernighan Algorithm Trace: n = 11 (1011_2)

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

Step 1: n = 11 (binary 1011). n & (n - 1) = 11 & 10 = 10 (binary 1010). count = 1.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 int hammingWeight(uint32_t n) {
8 int count = 0;
9 while (n != 0) {
10 n &= (n - 1);
11 count++;
12 }
13 return count;
14 }
15};
16
17int main() {
18 Solution sol;
19 cout << "Optimal (11): " << sol.hammingWeight(11) << endl; // 3
20 cout << "Optimal (128): " << sol.hammingWeight(128) << endl; // 1
21 return 0;
22}

Time & Space Complexity

  • Time complexity: O(k) where k is the number of 1-bits (at most 32)
  • 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 — 32-Bit Shift MaskO(32) = O(1)O(1)Check bit i from 0 to 31 using (n >> i) & 1.Fixed 32 iterations.
2.Better — Unsigned Right Shift While Non-ZeroO(log n)O(1)While n != 0, add n & 1 and unsigned shift n >>>= 1.Sequential shifting.
3.Optimal — Brian Kernighan's AlgorithmOptimalO(k) where k is the count of 1 bitsO(1)Repeatedly clear rightmost set bit: n &= (n - 1). Increment counter.Hardware bit clearing.

Common Pitfalls & Crucial Edge Cases

Signed infinite loop

while (n != 0) { count += n & 1; n >>= 1; } loops forever in Java for negative numbers. Use n >>>= 1 or n &= (n - 1).

String conversion overhead

n.toString(2).split('1').length - 1 allocates string memory and is frowned upon in interviews.

Signed comparison

Using while (n > 0) terminates prematurely for negative numbers where the sign bit is 1.

Crucial Edge Cases to Validate:

  • n = 0 — Zero set bits; returns 0.
  • n = 2^31 - 1 (INT_MAX) — 31 set bits; returns 31.
  • n = 0xFFFFFFFF (All 32 bits set) — Returns 32.
  • Power of two (e.g. n = 1024) — Exactly 1 set bit; returns 1.

Interview Tips & Best Practices

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

  1. Explain both the bit-shift check and Brian Kernighan's trick.
  2. Mention hardware-assisted POPCNT instructions on x86-64 and ARM architectures.
  3. Emphasize safe unsigned handling across language boundaries (e.g. Java signed 32-bit integers vs unsigned inputs).

Quick Comprehension Check

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

1.What is another name for the number of set bits in an integer?

2.How does Brian Kernighan's algorithm optimize counting 1-bits compared to shifting 32 times?

3.In Java/JavaScript, why must you use the unsigned right shift >>> when iterating bit by bit?

Back to DSA Sheet