Number of 1 Bits

Problem in Plain English

Count the 1 bits in the 32-bit binary form of an unsigned integer, treating a signed input with the same bit pattern identically.

Problem Statement

Given an integer representing a 32-bit unsigned bit pattern, return the number of one bits, called its Hamming weight. The shown inputs are binary representations for readability; the functions receive integers, not strings.

This page retains the generalized unsigned 32-bit form of the problem, including zero and patterns with the high bit set. A signed Java int may carry the same pattern, such as -3 for unsigned 4294967293. The current positive-integer version with 1 <= n <= 2147483647 is a subset of this contract.

Constraints

The functions receive one integer carrying a 32-bit pattern, not a binary string.
$0 \le n \le 2^{32}-1$ for the unsigned numeric representation.
Java uses the equivalent signed int carrier; the snippets also handle signed 32-bit carriers in Python and JavaScript.

Examples

Example 1

Input: n = 00000000000000000000000000001011
Output: 3

The binary form of 11 holds three 1 bits.

Example 2

Input: n = 00000000000000000000000010000000
Output: 1

The binary form of 128 holds a single 1 bit.

Example 3

Input: n = 11111111111111111111111111111101
Output: 31

This 32-bit pattern holds thirty-one 1 bits (it reads as -3 as a signed int).

Example 4

Input: n = 00000000000000000000000000000000
Output: 0

No bit is set. The fixed scan adds zero 32 times; the erasure approach returns immediately without any iteration.

Intuition

A set bit is simply a binary digit equal to one; leading zeros contribute nothing. Example 1 is decimal 11, whose binary form 1011 has three ones. Inspecting each of 32 positions counts them directly. Alternatively, subtracting one and ANDing with the old pattern erases one set bit at a time, so counting erasures skips zero positions. Signed and unsigned carriers must describe the same fixed 32-bit pattern.

Approaches

Scan All 32 Bits

Solution Details

Reveal Scan All 32 Bits: intuition, complexity, and code

Intuition

Every one of the 32 positions can be inspected directly: test the lowest bit with n & 1, then shift right unsigned to bring the next bit down. Thirty-two fixed rounds always finish the count, even when most bits are zero.

Step-by-Step Logic

Read Example 1 as n = 11 (binary 1011) with count = 0 and plan exactly 32 rounds.
Round 1: lowest bit 11 & 1 = 1, so count = 1; unsigned-shift to 5 (binary 101).
Round 2: lowest bit 5 & 1 = 1, so count = 2; unsigned-shift to 2 (binary 10).
Round 3: lowest bit 2 & 1 = 0, so count stays 2; unsigned-shift to 1.
Round 4: lowest bit 1 & 1 = 1, so count = 3; the remaining 28 rounds see only zeros.
Return 3, the expected output.

Why It Works

Before round k, count equals the number of ones among the k original lowest positions, and the working value contains the original pattern shifted right k times with zeros entering from the left. Masking with 1 counts the next position exactly once. Logical right shift preserves the remaining unexamined positions, establishing the invariant for the next round. After exactly 32 rounds all positions have been counted. Python first masks to 32 bits so its ordinary right shift behaves logically on this nonnegative working value.

Dry Run

Scan All 32 Bits: variable states at each step
Round	`n` before	`n & 1`	`count`
`1`	`11` (`1011`)	`1`	`1`
`2`	`5` (`101`)	`1`	`2`
`3`	`2` (`10`)	`0`	`2`
`4`	`1` (`1`)	`1`	`3`
`5` to `32`	`0`	`0`	`3`
return	-	-	`3`

Complexity Analysis

Time Complexity

O(1)

Space Complexity

O(1)

The scan always performs exactly 32 rounds, so time and additional allocated space are O(1) for the fixed-width contract. Only scalar counters and a local working value are stored; the input caller is not mutated. For a generalized w-bit word, this would be O(w) time under constant-time word operations.

Code

Solution.java

1class Solution {2    public int hammingWeight(int n) {3        int count = 0;4        for (int i = 0; i < 32; i++) {5            count += (n & 1);6            // Zero-fill the next position even when the signed carrier is negative.7            n >>>= 1;8        }9        return count;10    }11}

Hints

Hint 1

Look at the lowest bit first: n & 1 is 1 exactly when the current last bit is set.

Hint 2

After testing a bit, shift it away with an unsigned right shift so the next bit slides into place.

Hint 3

To skip zeros entirely, erase the lowest set bit with n & (n - 1) and count erasures until nothing remains.

Edge Cases

Zero returns 0: the erasure loop performs no work.
All 32 bits set, unsigned 4294967295 or signed -1, returns 32.
Only the highest bit set, unsigned 2147483648 or signed -2147483648, returns 1. Java subtraction wraps safely within its fixed-width pattern.
Unsigned 4294967293 or signed -3 returns 31; Python must mask signed carriers before its erasure loop.

Common Mistakes and Interview Tips

Using while (n > 0) with a signed Java carrier skips patterns whose high bit is set. Use n != 0 for bit clearing.
Using arithmetic right shift in a loop that waits for zero keeps adding leading ones for negative carriers. The fixed 32-round scan still terminates, but logical shifting makes its zero-fill invariant explicit.
In Python, clearing bits of a negative integer without first masking to 32 bits never exhausts its infinitely sign-extended representation.
Passing a binary string to these integer signatures, or treating decimal digits as bits, changes the input contract.
Interview tip: state the fixed width before claiming constant time; erasing bits takes one iteration per one, while scanning takes exactly 32.

Key Takeaway

n & (n - 1) always drops the lowest set bit — the single most useful bit-manipulation identity for counting, clearing, and power-of-two tests.