Number of 1 Bits

Problem Statement

Given a positive integer n, return how many 1s appear in its binary representation. This count is also called the Hamming weight or population count of n.

Examples

Example 1:

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

Example 2:

Input: n = 64
Output: 1
Explanation: 64 is 1000000 in binary; a power of two has exactly one 1 bit.

Example 3:

Input: n = 2147483647
Output: 31
Explanation: The largest signed 32-bit integer is 31 consecutive 1 bits.

Constraints

• 1 <= n <= 2^31 - 1

Approach 1: Check Every Bit

Algorithm

Look at each of the 32 bit positions in turn and count the ones that are set.

1. Set count = 0.
2. For each position i from 0 to 31, add (n >> i) & 1 to count.
3. Return count.

Using a logical (unsigned) shift, or an unsigned type, means the same code also counts the bits of a negative 32-bit value correctly, which is how older versions of this problem passed the input.

Implementation

Python:

class Solution:
    def hammingWeight(self, n: int) -> int:
        n &= 0xFFFFFFFF  # view n as a 32-bit pattern (a no-op for positive inputs)
        count = 0
        for i in range(32):
            count += (n >> i) & 1  # 1 if bit i is set
        return count

Java:

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            count += (n >>> i) & 1;  // >>> shifts in zeros, so negatives work too
        }
        return count;
    }
}

Go:

func hammingWeight(n int) int {
    x := uint32(n) // view n as a 32-bit pattern
    count := 0
    for i := 0; i < 32; i++ {
        count += int((x >> i) & 1) // 1 if bit i is set
    }
    return count
}

JavaScript:

/**
 * @param {number} n
 * @return {number}
 */
var hammingWeight = function(n) {
    let count = 0;
    for (let i = 0; i < 32; i++) {
        count += (n >>> i) & 1; // >>> treats n as an unsigned 32-bit value
    }
    return count;
};

C#:

public class Solution {
    public int HammingWeight(int n) {
        uint x = (uint)n;  // view n as a 32-bit pattern
        int count = 0;
        for (int i = 0; i < 32; i++) {
            count += (int)((x >> i) & 1);  // 1 if bit i is set
        }
        return count;
    }
}

C++:

#include <cstdint>

class Solution {
public:
    int hammingWeight(int n) {
        uint32_t x = static_cast<uint32_t>(n);  // view n as a 32-bit pattern
        int count = 0;
        for (int i = 0; i < 32; i++) {
            count += (x >> i) & 1u;  // 1 if bit i is set
        }
        return count;
    }
};

Complexity Analysis

• Time: O(1). Exactly 32 iterations regardless of the input.
• Space: O(1).

Approach 2: Brian Kernighan’s Trick (Optimal)

Algorithm

Subtracting 1 from a number flips its lowest set bit to 0 and turns every 0 below it into 1. ANDing with the original therefore clears exactly that lowest set bit:

n         = 1011000
n - 1     = 1010111
n & (n-1) = 1010000

So repeatedly applying n = n & (n - 1) removes one set bit per step, and the number of steps until n reaches 0 is the answer.

1. Set count = 0.
2. While n != 0: set n = n & (n - 1) and increment count.
3. Return count.

The loop runs once per set bit, so sparse numbers finish quickly. The typed versions work on an unsigned 32-bit copy so that n - 1 never overflows a signed type.

Implementation

Python:

class Solution:
    def hammingWeight(self, n: int) -> int:
        n &= 0xFFFFFFFF  # view n as a 32-bit pattern (a no-op for positive inputs)
        count = 0
        while n:
            n &= n - 1   # clear the lowest set bit
            count += 1
        return count

Java:

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= n - 1;  // clear the lowest set bit (int wraparound is defined in Java)
            count++;
        }
        return count;
    }
}

Go:

func hammingWeight(n int) int {
    x := uint32(n) // view n as a 32-bit pattern
    count := 0
    for x != 0 {
        x &= x - 1 // clear the lowest set bit
        count++
    }
    return count
}

JavaScript:

/**
 * @param {number} n
 * @return {number}
 */
var hammingWeight = function(n) {
    let x = n >>> 0; // unsigned 32-bit view of n
    let count = 0;
    while (x !== 0) {
        x = (x & (x - 1)) >>> 0; // clear the lowest set bit, keep it unsigned
        count++;
    }
    return count;
};

C#:

public class Solution {
    public int HammingWeight(int n) {
        uint x = (uint)n;  // unsigned copy, so x - 1 never overflows a signed type
        int count = 0;
        while (x != 0) {
            x &= x - 1;  // clear the lowest set bit
            count++;
        }
        return count;
    }
}

C++:

#include <cstdint>

class Solution {
public:
    int hammingWeight(int n) {
        uint32_t x = static_cast<uint32_t>(n);  // unsigned, so x - 1 is always well defined
        int count = 0;
        while (x != 0) {
            x &= x - 1;  // clear the lowest set bit
            count++;
        }
        return count;
    }
};

Complexity Analysis

• Time: O(k), where k is the number of set bits. Since k is at most 32, this is also O(1).
• Space: O(1).

Key Insights

• n & (n - 1) clears the lowest set bit. This one identity powers this problem, the power-of-two check ((n & (n - 1)) == 0, with the parentheses, since == binds tighter than & in C-family languages) and the fast version of Counting Bits.
• Work with an unsigned view. Bit counting is about the pattern, not the numeric value. An unsigned type (or a 32-bit mask in Python, >>> in Java and JavaScript) avoids sign extension and signed overflow.
• Built-ins exist. Integer.bitCount (Java), bits.OnesCount32 (Go), BitOperations.PopCount (C#), std::bitset<32>(n).count() (C++) and bin(n).count("1") (Python) all do this. Mention them, but expect to be asked to implement the logic yourself.

Edge Cases

• Powers of two have exactly one set bit; Approach 2 finishes after one iteration.
• n = 1 returns 1.
• n = 2^31 - 1 (all 31 low bits set) returns 31, the worst case for Approach 2 within the constraints.
• Negative input (older version of the problem): -1 is 32 ones and should return 32. Both approaches above handle it because they work on the 32-bit pattern.

Common Mistakes

• Arithmetic right shift on a negative value. In Java or JavaScript, n >> 1 copies the sign bit, so a loop of while (n != 0) { count += n & 1; n >>= 1; } never ends for a negative n. Use >>>.
• Unbounded loop in Python for negatives. Python’s n >>= 1 on a negative number never reaches 0. Mask with 0xFFFFFFFF first.
• Signed overflow in C++. n - 1 overflows when n is INT_MIN; working in uint32_t sidesteps it.
• Using count += n % 2 with negative numbers. In many languages -3 % 2 is -1, which corrupts the count.

Interview Tips

• Present the simple 32-step loop first, then improve it with Brian Kernighan’s trick and explain why n & (n - 1) clears the lowest set bit using a small binary example.
• Point out that Approach 2 is faster when few bits are set, even though both are O(1) for fixed-width integers.
• If the interviewer asks about calling it millions of times, mention a lookup table of 256 byte counts (four lookups per 32-bit word) or the hardware POPCNT instruction behind the built-ins.

Follow-up Questions

• If this function is called very often, how would you optimize it? Precompute the bit counts of all 256 byte values and sum four table lookups, or use the language’s popcount intrinsic.
• How do you count bits for every number from 0 to n? That is Counting Bits, which reuses earlier answers with DP.
• How many bits differ between two integers? Count the set bits of x ^ y (the Hamming distance).
• Can you do it without a loop? Yes, with the SWAR technique that adds bit counts in parallel inside the word: pairs, then nibbles, then bytes.

Related Problems

• Counting Bits
• Reverse Bits
• Power of Two
• Sum of Two Integers
• Single Number