Number of 1 Bits

easy
Bit ManipulationBit Manipulation

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

Examples

Example 1

  • Input: n = 11
  • Output: 3
  • Explanation: The binary representation of 11 is 1011, which has three set bits.

Example 2

  • Input: n = 128
  • Output: 1
  • Explanation: The binary representation of 128 is 10000000, which has one set bit.

Example 3

  • Input: n = 2147483645
  • Output: 30

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Loop Through Bits

Intuition

The simplest approach is to examine each bit of the number one at a time. We check the least significant bit using AND with 1, count it if it is set, then right-shift the number. We repeat until the number becomes zero. This inspects every bit position that could be set, giving us the total count of 1s.

Algorithm

  1. Initialize a counter to zero.
  2. While `n` is not zero, check if the least significant bit is 1 using `n & 1`.
  3. If it is 1, increment the counter.
  4. Right-shift `n` by one position.
  5. Return the counter.
TimeO(32) which is O(1) — we check at most 32 bitsSpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
};
Java 21
class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>>= 1;
        }
        return count;
    }
}
Python 3.12
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            count += n & 1
            n >>= 1
        return count
Go 1.26
func hammingWeight(n int) int {
    count := 0
    for n != 0 {
        count += n & 1
        n >>= 1
    }
    return count
}
Approach 2

Brian Kernighan's Algorithm

Intuition

A more efficient approach uses the trick n & (n - 1), which clears the lowest set bit of n. Each time we apply this operation, exactly one set bit is removed. We count how many times we can do this before n becomes zero. This runs in O(k) time where k is the number of set bits, which is often fewer than 32 iterations.

Algorithm

  1. Initialize a counter to zero.
  2. While `n` is not zero, apply `n = n & (n - 1)` to clear the lowest set bit.
  3. Increment the counter for each cleared bit.
  4. Return the counter.
TimeO(k) where k is the number of set bits — at most O(32) which is O(1)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
};
Java 21
class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
}
Python 3.12
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count
Go 1.26
func hammingWeight(n int) int {
    count := 0
    for n != 0 {
        n &= n - 1
        count++
    }
    return count
}

Frequently asked questions

What is the optimal time complexity of Number of 1 Bits?

The most efficient approach in this guide ("Brian Kernighan's Algorithm") runs in O(k) where k is the number of set bits — at most O(32) which is O(1) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Number of 1 Bits use?

Number of 1 Bits is a easy-level Bit Manipulation problem involving Bit Manipulation. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Number of 1 Bits be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Counting BitsReverse Bits

Original problem: leetcode.com

Loading editor...
Input
n=
0
Expected Output
0