Number of 1 Bits

• Difficulty: Easy
• Topics: Divide and Conquer, Bit Manipulation
• Link: https://leetcode.com/problems/number-of-1-bits/

Problem Description

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

Example 1:

Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

Example 2:

Input: n = 128

Output: 1

Explanation:

The input binary string 10000000 has a total of one set bit.

Example 3:

Input: n = 2147483645

Output: 30

Explanation:

The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

Constraints:

• 1 <= n <= 231 - 1

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

Solution

1. Problem Deconstruction

Technical Definition
Given a 32-bit unsigned integer n, compute its Hamming weight (cardinality of set bits). The solution must use bitwise operations or optimized string processing to count 1s efficiently.

Beginner Explanation
Convert the number to binary (base-2) and count how many times the digit 1 appears. For example, 5 becomes 101, so the answer is 2.

Mathematical Formulation
Let $f(n) = \sum_{i=0}^{31} \left( \left\lfloor \frac{n}{2^i} \right\rfloor \mod 2 \right)$,
or equivalently, $f(n) = \sum_{i=0}^{31} \text{bit}(n, i)$,
where $\text{bit}(n, i) = (n \gg i) \& 1$.

Constraint Analysis

• $1 \leq n \leq 2^{31} - 1$:
  • Limits binary length to 31 bits (no leading zeros).
  • Edge cases: All bits set (31 1s), single-bit numbers (e.g., $128 = 2^7$).
  • Excludes zero, so no need to handle empty bitstrings.

---

2. Intuition Scaffolding

Real-World Metaphor
A parking lot with 32 spaces. Each space has a car (1) or is empty (0). Count occupied spaces by checking each spot or removing cars one by one.

Gaming Analogy
In a dungeon, each enemy (set bit) requires a spell (bitwise AND) to eliminate. The number of casts equals the number of enemies.

Math Analogy
Summing the binary digits of $n$. Equivalent to $\text{popcount}(n)$ in computer architecture.

Common Pitfalls

1. Infinite Loops for Negative Numbers: Not applicable here (input is positive).
2. String Conversion Overhead: bin(n) in Python is optimized, but bitwise methods avoid string allocation.
3. Bit Shifting Without Bounds: Unbounded shifts in Python risk infinite loops; limit to 32 iterations.
4. Assuming O(n) Time: All solutions are O(1) due to fixed 32-bit length.
5. Modulo/Division Inefficiency: Bitwise operations are faster than arithmetic methods.

---

3. Approach Encyclopedia

Approach 1: Bit Shifting
Pseudocode

def count_bits(n):  
    count = 0  
    for _ in range(32):  
        count += n & 1  
        n >>= 1  
    return count  

Complexity

• Time: $O(32) = O(1)$.
• Space: $O(1)$.

Visualization

n = 11 (1011)  
Iteration 1: n=1011 → LSB=1, count=1  
Iteration 2: n=101 → LSB=1, count=2  
Iteration 3: n=10 → LSB=0, count=2  
Iteration 4: n=1 → LSB=1, count=3  
... (continues for 32 bits)  

Approach 2: Brian Kernighan’s Algorithm
Pseudocode

def count_bits(n):  
    count = 0  
    while n:  
        n &= n - 1  # Remove rightmost set bit  
        count += 1  
    return count  

Complexity

• Time: $O(k)$, $k$ = number of set bits (≤31 → $O(1)$).
• Space: $O(1)$.

Visualization

n = 11 (1011) → 1011 & 1010 = 1010 (count=1)  
n = 1010 → & 1001 = 1000 (count=2)  
n = 1000 → & 0111 = 0 (count=3)  

Approach 3: Binary String Conversion
Pseudocode

def count_bits(n):  
    return bin(n).count('1')  

Complexity

• Time: $O(32)$ for string conversion and count.
• Space: $O(32)$ for the string (negligible).

---

4. Code Deep Dive

Optimal Solution (Brian Kernighan’s)

def hammingWeight(n):  
    count = 0  
    while n:  
        n &= n - 1  # Key: Remove rightmost 1  
        count += 1  
    return count  

Line-by-Line

1. count = 0: Initialize counter.
2. while n:: Loop until all bits are unset.
3. n &= n - 1: Bitwise AND removes the rightmost 1 (e.g., 1010 → 1000).
4. count += 1: Increment for each eliminated bit.

Edge Case Handling

• Example 1: n=11 (1011) → 3 iterations (3 bits).
• Example 2: n=128 (10000000) → 1 iteration.
• Example 3: n=2147483645 (30 bits) → 30 iterations.

---

5. Complexity War Room

Hardware-Aware Analysis

• 32-bit operations use minimal CPU cycles (<< 1 ns/op).
• Memory usage: <10 bytes (counter + loop variables).

Industry Comparison

Method	Time	Space	Readability	Interview Viability
Bit Shifting	O(1)	O(1)	8/10	✅ Clear logic
Brian Kernighan	O(k)	O(1)	9/10	✅ Optimal & Elegant
Binary String	O(1)	O(1)	10/10	✅ Pythonic

---

6. Pro Mode Extras

Variants

• LC 338 (Counting Bits for All Numbers): Precompute using DP.
• LC 477 (Total Hamming Distance): Combine bit counts across numbers.

Follow-Up Optimization
Precompute a 256-entry lookup table (byte-wise counts). Split n into 4 bytes and sum:

lookup = [0] * 256  
for i in range(256):  
    lookup[i] = lookup[i // 2] + (i & 1)  
def count_bits(n):  
    return (lookup[n & 0xff] + lookup[(n >> 8) & 0xff] +  
            lookup[(n >> 16) & 0xff] + lookup[(n >> 24) & 0xff])  

Interview Cheat Sheet

• Key Insight: Bitwise AND (&) and shifts (>>) are your friends.
• Mention: Trade-offs between readability (string) and efficiency (bitwise).
• Gotcha: Python handles big integers, but constraints cap at 32 bits.