Counting the Number of 1 Bits in an Unsigned Integer

January 10, 2025

Counting the Number of 1 Bits in an Unsigned Integer

In the world of computer programming, binary representations of numbers are fundamental.

A common problem that arises is counting how many bits are set to 1 in the binary form of a given number. In this article, we will explore how to solve this problem efficiently.

Problem Overview

You are given an unsigned integer n. The task is to count the number of 1 bits in its binary representation. The number n is non-negative and fits within a 32-bit unsigned integer, meaning it is guaranteed to be a valid number in the range from 0 to 4,294,967,295.

The binary representation of a number is simply its equivalent expression in base-2, where each digit (bit) can either be a 0 or a 1. Our goal is to count how many 1 bits there are in the binary representation of n.

Understanding the Input and Output

Input: An unsigned integer n, which fits within 32-bits.
Output: The number of 1 bits in the binary representation of n.

Example Walkthrough

Let’s break down a couple of examples to understand the problem better.

Example 1

Input: n = 00000000000000000000000000010111

output: 4

This is the binary representation of the integer 23:

Binary: 00000000000000000000000000010111
Number of 1 bits: There are 4 ones in this binary number.

Example 2

Input: n = 01111111111111111111111111111101

Output: 30

This is the binary representation of the integer 2147483645:

Binary: 01111111111111111111111111111101
Number of 1 bits: There are 30 ones in this binary number.

Approach to Solving the Problem

The task can be solved in several ways, but the most efficient method is to use bit manipulation. Here’s a step-by-step approach:

Right Shift and Check Each Bit:
- We can iterate through each bit of the integer, checking whether it is 1 or 0.
- We do this by repeatedly shifting the number to the right and checking the least significant bit (the rightmost bit).
Using Bitwise AND:
- A simple way to check if a bit is 1 is to use the bitwise AND operation with 1. If the result is 1, then the bit is 1, otherwise, it is 0.
- Example: n & 1 will return 1 if the least significant bit of n is 1, and 0 if it is 0.
Continue Shifting:
- After checking the least significant bit, shift the number right by one bit (n >>= 1) to examine the next bit.
- Repeat this process until the number becomes 0, meaning we’ve checked all bits.

There are mainly 4 approach to solve this problem –

Bit Mask – I Method
Bit Mask – II Method
Bit Mask (Optimal)
Built In Function

1. Bit Mask – I

Time & Space Complexity

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

Python

C++

Java

JavaScript

Python

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

C++

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;
    }
};

Java

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;
    }
}

JavaScript

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;
    }
}

2. Bit Mask – II

Time & Space Complexity

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

Code

C++

Java

Python

JavaScript

C++

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

Java

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

Python

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

JavaScript

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

3. Bit Mask (Optimal)

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

Code

C++

Java

Python

JavaScript

C++

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

Java

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

Python

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

JavaScript

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

4. Built-In Function

Time & Space Complexity

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

Code

C++

Java

Python

JavaScript

C++

class Solution {
public:
    int hammingWeight(uint32_t n) {
        return __builtin_popcount(n);
    }
};

Java

public class Solution {
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}

Python

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

JavaScript

class Solution {
    /**
     * @param {number} n - a positive integer
     * @return {number}
     */
    hammingWeight(n) {
        return n.toString(2).split('0').join('').length;
    }
}

Unlock this article for Free,
by logging in

Counting the Number of 1 Bits in an Unsigned Integer