145.Number of 1 Bits

EasyBlind 75Bit Manipulation · 2/7

Problem

Given a positive integer n, return the number of set bits (bits equal to 1) in its binary representation. This count is also known as the Hamming weight.

Examples

Input:  n = 11
Output: 3
Explanation: 11 in binary is 1011, which has three 1 bits.

Input:  n = 128
Output: 1
Explanation: 128 in binary is 10000000, a single 1 bit.

Input:  n = 2147483645
Output: 30
Explanation: 2147483645 = 1111111111111111111111111111101 (31 bits), thirty of which are 1.

Constraints

1 <= n <= 2^31 - 1

💡 Key Insight

n & (n - 1) clears the lowest set bit of n: subtracting 1 turns the lowest 1 into 0 and all zeros below it into 1s, and the AND wipes out that whole tail. So repeating n &= n - 1 until n == 0 takes exactly as many iterations as there are 1 bits — no need to visit the zeros at all.

Brute Force (Check All 32 Bits)

TimeO(32) = O(1)SpaceO(1).

Intuition

An int has 32 bit positions. For each position i, shift n right by i and check whether the lowest bit is 1.

Algorithm

count = 0.
For i from 0 to 31: if ((n >> i) & 1) == 1, increment count.
Return count.

Visualization

n = 11 = ...0000 1011
i=0: 1 ✓   i=1: 1 ✓   i=2: 0     i=3: 1 ✓   i=4..31: 0
count = 3

Code

java

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

Complexity

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

Shift Until Zero

TimeO(b) where b is the position of the highest set bit (≤ 32).SpaceO(1).

Intuition

Instead of a fixed 32 iterations, keep inspecting the lowest bit (n & 1) and then shift n right with the unsigned shift >>>. Stop when n becomes 0, so leading zeros are never examined.

Algorithm

count = 0.
While n != 0: count += n & 1; n >>>= 1.
Return count.

Visualization

n = 1011 → +1, shift → 101 → +1, shift → 10 → +0, shift → 1 → +1, shift → 0
count = 3 (4 iterations = number of significant bits)

Code

java

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1; // add the lowest bit
            n >>>= 1;       // unsigned shift: never loops forever on negatives
        }
        return count;
    }
}

Complexity

Time: O(b) where b is the position of the highest set bit (≤ 32).
Space: O(1).

Brian Kernighan's TrickOptimal

TimeO(k) where k is the number of set bits (≤ 32).SpaceO(1).

Intuition

n & (n - 1) removes exactly one set bit — the lowest one. Count how many times we can do that before n reaches 0. The loop runs once per 1 bit, so sparse numbers like 128 finish in a single iteration.

Algorithm

count = 0.
While n != 0: n = n & (n - 1); count++.
Return count.

Dry Run

flowchart TD
    A["n = 1011 (11), count = 0"] --> B["n - 1 = 1010<br/>n AND (n-1) = 1010"]
    B -->|"count = 1"| C["n = 1010, n - 1 = 1001<br/>AND = 1000"]
    C -->|"count = 2"| D["n = 1000, n - 1 = 0111<br/>AND = 0000"]
    D -->|"count = 3"| E{"n == 0?"}
    E -->|"yes"| F["return 3"]

Code

java

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= n - 1; // drop the lowest set bit
            count++;
        }
        return count;
    }
}

Complexity

Time: O(k) where k is the number of set bits (≤ 32).
Space: O(1).

In production Java you would simply call Integer.bitCount(n), which uses a constant-time bit-parallel algorithm (and often a single CPU POPCNT instruction).

Complexity Comparison

Approach	Time	Space
Check All 32 Bits	O(32)	O(1)
Shift Until Zero	O(highest bit position)	O(1)
Brian Kernighan	O(number of set bits)	O(1)

Common Pitfalls

Using the signed shift >> in a while (n != 0) loop — for a negative n the sign bit is copied in forever and the loop never ends. Use >>>.
Writing n & 1 == 1 without parentheses — in Java == binds tighter than &, so it does not compile (or means something else in other languages). Write (n & 1) == 1.
Using n % 2 and n / 2 — they behave differently for negative numbers (-3 % 2 == -1), which matters in the variant where the input is treated as an unsigned 32-bit value.
Forgetting that n - 1 borrows through trailing zeros — that borrow is exactly why the Kernighan trick removes only the lowest set bit.