191. Number of 1 Bits - Explanation

Description

You are given an unsigned integer n. Return the number of 1 bits in its binary representation.

You may assume n is a non-negative integer which fits within 32-bits.

Example 1:

Input: n = 00000000000000000000000000010111

Output: 4

Example 2:

Input: n = 01111111111111111111111111111101

Output: 30

Topics

Divide and Conquer Bit Manipulation

Recommended Time & Space Complexity

You should aim for a solution with O(1) time and O(1) space.

Hint 1

The given integer is a 32-bit integer. Can you think of using bitwise operators to iterate through its bits? Maybe you should consider iterating 32 times.

Hint 2

We iterate 32 times (0 to 31) using index i. The expression (1 << i) creates a bitmask with a set bit at the i-th position. How can you check whether the i-th bit is set in the given number? Maybe you should consider using the bitwise-AND ("&").

Hint 3

Since the mask has a set bit at the i-th position and all 0s elsewhere, we can perform a bitwise-AND with n. If n has a set bit at the i-th position, the result is positive; otherwise, it is 0. We increment the global count if the result is positive and return it after the iteration.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Number Representation - Understanding how integers are stored as sequences of bits (0s and 1s)
Bitwise AND Operator - Using & to check if specific bits are set
Bit Shifting - Using left shift (<<) and right shift (>>) to move bits or create masks
Bitwise Tricks - Understanding that n & (n-1) removes the rightmost set bit

1. Bit Mask - I

Intuition

We are asked to count how many 1 bits are present in the binary representation of an integer n.
This value is also known as the Hamming Weight or population count.

A straightforward way to do this is to:

check each bit position one by one
see whether that bit is set (1) or not (0)

Since integers are typically represented using 32 bits, we can safely check all 32 bit positions.

At each position:

create a mask with a single 1 at that position using 1 << i
use bitwise AND (&) to test whether that bit is set in n

Algorithm

Initialize a counter res = 0.
For each bit position i from 0 to 31:
Create a mask with only the i-th bit set:
- mask = 1 << i
Check if this bit is set in n:
- If (mask & n) != 0, increment res
After checking all 32 bits, return res.

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        for i in range(32):
            if (1 << i) & n:
                res += 1
        return res

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

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

class Solution {
    /**
     * @param {number} n - a positive integer
     * @return {number}
     */
    hammingWeight(n) {
        let res = 0;
        for (let i = 0; i < 32; i++) {
            if ((1 << i) & n) {
                res++;
            }
        }
        return res;
    }
}

public class Solution {
    public int HammingWeight(uint n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            if ((1 << i & n) != 0) {
                res++;
            }
        }
        return res;
    }
}

class Solution {
    fun hammingWeight(n: Int): Int {
        var res = 0
        for (i in 0 until 32) {
            if ((1 shl i) and n != 0) {
                res++
            }
        }
        return res
    }
}

class Solution {
    func hammingWeight(_ n: Int) -> Int {
        var res = 0
        for i in 0..<32 {
            if (1 << i) & n != 0 {
                res += 1
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

2. Bit Mask - II

Intuition

We want to count the number of 1 bits in the binary representation of an integer n.

Instead of checking every bit position explicitly, we can:

look at the least significant bit of n
then shift the number right to bring the next bit into that position

At each step:

n & 1 tells us whether the current least significant bit is 1
shifting n right by one (n >>= 1) moves us to the next bit

We repeat this until n becomes 0.

Algorithm

Initialize a counter res = 0.
While n > 0:
- If the least significant bit is 1 (n & 1):
  - increment res
- Shift n one bit to the right (n >>= 1)
When n becomes 0, all bits have been processed.
Return res.

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += 1 if n & 1 else 0
            n >>= 1
        return res

public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            res += (n & 1) == 1 ? 1 : 0;
            n >>= 1;
        }
        return res;
    }
}

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while (n != 0) {
            res += (n & 1) ? 1 : 0;
            n >>= 1;
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number} n - a positive integer
     * @return {number}
     */
    hammingWeight(n) {
        let res = 0;
        while (n !== 0) {
            res += (n & 1) === 1 ? 1 : 0;
            n >>= 1;
        }
        return res;
    }
}

public class Solution {
    public int HammingWeight(uint n) {
        int res = 0;
        while (n != 0) {
            res += (n & 1) == 1 ? 1 : 0;
            n >>= 1;
        }
        return res;
    }
}

class Solution {
    fun hammingWeight(n: Int): Int {
        var res = 0
        var num = n
        while (num != 0) {
            if ((num and 1) != 0) {
                res++
            }
            num = num shr 1
        }
        return res
    }
}

class Solution {
    func hammingWeight(_ n: Int) -> Int {
        var n = n
        var res = 0
        while n != 0 {
            res += (n & 1) != 0 ? 1 : 0
            n >>= 1
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

3. Bit Mask (Optimal)

Intuition

We want to count the number of 1 bits in the binary representation of an integer n (Hamming Weight).

A very efficient trick comes from this key observation:

Subtracting 1 from a number flips the rightmost 1 bit to 0 and turns all bits to its right into 1
Performing n & (n - 1) removes the rightmost 1 bit from n

So every time we do:
n = n & (n - 1) we eliminate exactly one 1 bit.

This means:

the number of iterations equals the number of 1 bits
we don’t waste time checking bits that are 0

That’s why this approach is considered optimal.

Algorithm

Initialize a counter res = 0.
While n is not zero:
- Update n = n & (n - 1) to remove the rightmost 1 bit
- Increment res by 1
When n becomes 0, all 1 bits have been removed.
Return res.

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            n &= n - 1
            res += 1
        return res

class Solution {
    /**
     * @param {number} n - a positive integer
     * @return {number}
     */
    hammingWeight(n) {
        let res = 0;
        while (n !== 0) {
            n &= n - 1;
            res++;
        }
        return res;
    }
}

class Solution {
    fun hammingWeight(n: Int): Int {
        var res = 0
        var num = n
        while (num != 0) {
            num = num and (num - 1)
            res++
        }
        return res
    }
}

class Solution {
    func hammingWeight(_ n: Int) -> Int {
        var n = n
        var res = 0
        while n != 0 {
            n &= (n - 1)
            res += 1
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

4. Built-In Function

Intuition

We want to find the Hamming Weight of a number, which means counting how many 1 bits are present in its binary representation.

Most programming languages provide:

a way to convert a number into binary form, or
a built-in utility to count set bits

Instead of manually checking each bit using bit manipulation, we can rely on these built-in features. This makes the solution short, easy to understand, and less error-prone, especially for beginners.

This approach focuses on clarity and simplicity, not on low-level optimizations.

Algorithm

Convert the given number n into its binary representation
(using a built-in binary conversion or bit-count utility provided by the language).
Count the number of 1 bits in that representation.
Return the count.

class Solution:
    def hammingWeight(self, n: int) -> int:
        return bin(n).count('1')

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

Common Pitfalls

Signed vs Unsigned Integer Handling

In some languages, right-shifting a signed negative integer fills with 1s (arithmetic shift) instead of 0s (logical shift). This can cause infinite loops when using while (n != 0) with negative inputs. Use unsigned types or the >>> operator in languages that support it.

Using Division Instead of Bit Shift

While n / 2 and n >> 1 produce the same result for positive integers, division can behave differently for negative numbers and is generally slower. Stick to bitwise operations for clarity and consistency with the problem's intent.