⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#191) before relying on it.

Number of 1 Bits (Hamming Weight)

Count the number of set bits (1s) in the binary representation of an unsigned integer. Watch how the n &= (n - 1) trick efficiently drops the lowest set bit in each iteration.

Bit Manipulation LeetCode 191 ↗ Easy

The Problem

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

Constraints: The input must be a binary string of length 32.

Note: In some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.

Interactive Visualization

Number (0 to 4294967295)

Preset

Speed:

1 Bits Count

32-Bit Binary Representation

Operation: n &= (n - 1)

n: -

n - 1: -

n & (n-1): -

Code

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

def hammingWeight(n):    count = 0    while n:        n &= n - 1        count += 1    return count

Status

Press Step or Play to begin.

How It Works

Key Insight

The operation n &= (n - 1) is a clever bit manipulation trick that clears the lowest set bit (rightmost 1) in the binary representation of n. By repeatedly applying this operation until n becomes 0, we can count exactly how many 1 bits were present.

Why Does This Work?

When you subtract 1 from a number, all the bits after the rightmost 1 (including that 1) get flipped:

If n = 1011 (binary), then n - 1 = 1010
The rightmost 1 became 0, and all bits to its right flipped
When we compute n & (n-1) = 1011 & 1010 = 1010, the rightmost 1 is cleared

The Algorithm

Initialize: count = 0
While n > 0:
- Apply n &= (n - 1) to clear the lowest set bit
- Increment count
Return: count (the number of times we cleared a bit)

Complexity

Time O(k)

Space O(1)

Where k is the number of set bits. This algorithm runs in time proportional to the number of 1 bits, not the total number of bits (32). For sparse numbers (few 1s), this is much faster than checking every bit position.