Number of 1 Bits

EASY✓ CHIP-TIMEDLC #191 — FULL STATEMENT ↗

The drill: Count how many bits are set to 1 in a 32-bit integer — the classic warm-up for every bit trick that follows.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A 32-bit integer arrives, and the task is to count how many of its bits are set to 1 in its binary representation.

The value is treated as a fixed-width 32-bit pattern rather than a mathematical integer that could grow arbitrarily large, so the count only ever ranges from zero, for an all-zero pattern, up to 32, for a pattern of all ones.

The result is that single count — an integer between 0 and 32 — with no need to report which positions held the 1 bits, only how many there were.

EX 01

n = 0

→ 0

NO BITS SET

EX 02

n = 1

→ 1

SINGLE LOWEST BIT

EX 03

n = 2

→ 1

SINGLE BIT, NOT THE LOWEST

input is always exactly 32 bits wide
the value can represent any bit pattern, including all zeros or all ones
the answer is an integer from 0 to 32 inclusive
only the count of set bits matters, not their positions

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Checking whether a value is odd tells you its lowest bit; shifting right walks that check across every position. What's the ceiling on how many shifts you'd ever need?

HINT 2 THE STRUCTURE

A fixed 32 checks always works, but most of that work is wasted once the remaining bits are all zero. Is there a move that skips straight past the zero stretches?

HINT 3 ONE STEP FROM THE ANSWER

n & (n − 1) always clears exactly the lowest set bit. Loop that operation and count iterations until n hits zero — you touch each 1-bit once, nothing else.

COACH'S BOARD — THE PATTERN, STEP BY STEP

KERNIGHAN'S DROPPATTERN · KERNIGHAN'S TRICKn = 7 (0111)

BITS CLEARED

count → 0

STEP 1

7 in binary is 0111. n & (n − 1) always drops the lowest set bit — count how many drops it takes to reach zero.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/number-of-1-bits.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1  # clear the lowest set bit
            count += 1
        return count

TIME O(K) FOR K SET BITSSPACE O(1)PYTHON · RACE PACE · 7 LN

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

TIME O(32)SPACE O(1)PYTHON · TRAINING PACE · 7 LN

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
}

TIME O(K) FOR K SET BITSSPACE O(1)JAVA · RACE PACE · 10 LN

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (((n >>> i) & 1) != 0) {
                count++;
            }
        }
        return count;
    }
}

TIME O(32)SPACE O(1)JAVA · TRAINING PACE · 11 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED