deepSWE.io

Number of 1 Bits

Bit Manipulation

10 min

Problem Statement

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Example

Example 1:

Input: n = 00000000000000000000000000001011

Output: 3

Solution (Bitwise AND)

The problem can be solved efficiently using a bitwise AND operation and a loop. The key idea is to use the expression n & (n - 1), which clears the least significant bit of n.

Algorithm Steps

Initialize a counter to 0.
While n is not 0, apply the operation n = n & (n - 1) and increment the counter.
Each time the operation is performed, one '1' bit is cleared.
The final value of the counter is the number of '1' bits.

n

00000000000000000000000000001011

count

0

Start: n = 11 (00000000000000000000000000001011), count = 0

Number of 1 Bits Solution


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