Number of 1 Bits (LC 191)

Pattern: Bit Manipulation (Hamming weight)
Difficulty: Easy
Key Concept: Each n & (n - 1) clears the lowest set bit—count how many times you can do that before n becomes 0.

Problem Statement

Given a positive integer n, return the number of set bits in its binary representation (also called Hamming weight).

Note: In Java the input is an int; treat bit positions as the usual 32 bits (for unsigned-style problems, LeetCode often passes values as int that represent unsigned semantics).

Input

• n: int

Output

• int — count of 1 bits

Example

• n = 11 (binary 1011) → 3
• n = 128 (binary 10000000) → 1

---

1. Algorithm & Pseudocode

Brute force

Check every bit position (0..31): if that bit is 1, increment the answer.

count = 0
for i from 0 to 31:
    if (n >> i) & 1 == 1:
        count++
return count

Optimal

Repeatedly clear the lowest set bit with n = n & (n - 1) and count clears.

count = 0
while n != 0:
    n = n & (n - 1)
    count++
return count

Each step removes exactly one 1, so the loop runs once per set bit.

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why the brute works There are only 32 bits. Testing each with (n >> i) & 1 is exhaustive and simple.

2. Why n & (n - 1) clears the lowest 1 Subtracting 1 flips the lowest 1 to 0 and flips all trailing zeros after it to 1. AND-ing with the original keeps everything above that lowest 1 the same and forces that position to 0.

3. Why count iterations = number of ones Each iteration destroys exactly one 1. When no 1s remain, n is 0.

4. Comparison to shifting The “clear lowest bit” trick skips over long runs of 0 bits without scanning them one by one (still O(32) worst case, but proportional to popcount, not bit width).

---

3. The Dry Run

Sample: n = 11 → binary 1011 (three ones). Optimal n & (n-1).

Step	n (decimal)	n (binary)	n - 1	n & (n-1)	count
init	11	1011	—	—	0
1	11	1011	1010	1010 (10)	1
2	10	1010	1001	1000 (8)	2
3	8	1000	0111	0000 (0)	3

Result: count = 3.

ASCII: lowest set bit

n:     ...1 0 0 1 1 0 0
n-1:   ...1 0 0 1 0 1 1   (borrow ripples through trailing 0s)
       -----------------
n&(n-1) ...1 0 0 1 0 0 0   lowest 1 cleared

---

4. Java Solution

Brute Force

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (((n >> i) & 1) == 1) {
                count++;
            }
        }
        return count;
    }
}

Time: O(1) — 32 iterations.
Space: O(1).

Optimal

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
}

Time: O(1) — at most 32 clears; often fewer when sparse.
Space: O(1).

Built-in (interview note): Integer.bitCount(n) is O(1) at the CPU level on modern JVMs; know it exists, but explain the bit trick first.

---

5. The “Java vs. Others” Edge

• Integer.bitCount HotSpot often lowers this to a POPCNT-style intrinsic—great in production, but interviews want the n & (n-1) story.
• Unsigned confusion If the problem treats n as unsigned (e.g. large positive values above Integer.MAX_VALUE cannot be represented as positive int in Java). LeetCode 191 passes int; use >>> if you need to shift without sign extension while inspecting bits: (n >>> i) & 1.
• C++ Often uses unsigned or uint32_t to match hardware exactly; Java uses int + >>> when needed.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute (scan 32 bits)	O(1)	O(1)	Always 32 steps.
Optimal (n & (n-1))	O(1)	O(1)	Steps = number of 1 bits; worst 32.
Integer.bitCount	O(1)	O(1)	JVM may use CPU popcount; know conceptually.