Number of 1 Bits

EASY✓ CHIP-TIMEDLC #191 — FULL STATEMENT

The briefingthe full drill, in my own words

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.

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.

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

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

The hintstake 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 boardthe 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 splitstwo 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-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED