191. Number of 1 Bits (Easy)

Problem

Write a function that takes an unsigned integer and returns the number of 1 bits it has (popcount).

Example

• n = 0b1011 → 3
• n = 0b10000000 → 1

LeetCode 191 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Shift and test each bit

Python

def hamming_weight(n):
    count = 0
    while n:                        # L1: loop up to B iterations (B = bit width)
        count += n & 1              # L2: O(1), test LSB
        n >>= 1                     # L3: O(1), shift right
    return count

TypeScript

function hammingWeight(n: number): number {
    let count = 0;
    while (n) {                     // L1: loop up to B iterations (B = bit width)
        count += n & 1;             // L2: O(1), test LSB
        n >>>= 1;                   // L3: O(1), shift right (unsigned)
    }
    return count;
}

Go

func hammingWeight(n uint32) int {
    count := 0
    for n != 0 {                    // L1: loop up to B iterations (B = bit width)
        count += int(n & 1)         // L2: O(1), test LSB
        n >>= 1                     // L3: O(1), shift right
    }
    return count
}

Swift

final class Solution {
    func hammingWeight(_ n: UInt32) -> Int {
        var value = n
        var count = 0
        for _ in 0..<32 {
            count += Int(value & 1)
            value >>= 1
        }
        return count
    }
}

Where the time goes, line by line

Variables: B = number of bits in n (32 for this problem).

Line	Per-call cost	Times executed	Contribution
L1-L3 (shift loop)	$O(1)$	B	$O(B)$ = $O(1)$ ← dominates (constant)
L2 (test LSB)	$O(1)$	B	$O(B)$
L3 (shift right)	$O(1)$	B	$O(B)$

The loop runs at most B = 32 iterations regardless of input value.

Complexity

• Time: $O(B)$ where B = number of bits (32 for this problem).
• Space: $O(1)$.

Approach 2: Brian Kernighan’s trick (canonical)

n & (n - 1) clears the lowest set bit. Loop until n == 0.

Python

def hamming_weight(n):
    count = 0
    while n:                        # L1: loop popcount(n) times
        n &= n - 1                  # L2: O(1), clear lowest set bit
        count += 1                  # L3: O(1)
    return count

TypeScript

function hammingWeight(n: number): number {
    let count = 0;
    while (n) {                     // L1: loop popcount(n) times
        n &= n - 1;                 // L2: O(1), clear lowest set bit
        count++;                    // L3: O(1)
    }
    return count;
}

Go

func hammingWeight(n uint32) int {
    count := 0
    for n != 0 {                    // L1: loop popcount(n) times
        n &= n - 1                  // L2: O(1), clear lowest set bit
        count++                     // L3: O(1)
    }
    return count
}

Swift

final class Solution {
    func hammingWeight(_ n: UInt32) -> Int {
        var value = n
        var count = 0
        while value != 0 {
            value &= value - 1
            count += 1
        }
        return count
    }
}

Where the time goes, line by line

Variables: B = number of set bits in the input (32 max).

Line	Per-call cost	Times executed	Contribution
L1-L3 (Kernighan loop)	$O(1)$	popcount(n)	$O(popcount)$ ← dominates
L2 (clear lowest bit)	$O(1)$	popcount(n)	$O(popcount)$

The loop runs exactly popcount(n) times, not B times. For sparse inputs this is much faster than Approach 1.

Complexity

• Time: $O(popcount)$. Iterations = number of set bits.
• Space: $O(1)$.

Faster than Approach 1 when the integer has few set bits.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Built-in / bit-parallel tricks

Modern hardware has popcount instructions. Python’s bin(n).count('1') or n.bit_count() (Python 3.10+) compiles to that on supporting platforms. In TypeScript, Math.clz32 counts leading zeros but there is no direct popcount built-in; use Kernighan’s trick instead.

def hamming_weight(n):
    return n.bit_count()            # L1: O(1) on modern hardware

Where the time goes, line by line

Variables: B = number of bits (32 max for this problem).

Line	Per-call cost	Times executed	Contribution
L1 (bit_count)	$O(1)$ hardware	1	$O(1)$ ← dominates

On CPUs with a POPCNT instruction this compiles to a single instruction.

Complexity

• Time: $O(1)$ on most modern hardware, $O(B)$ worst.
• Space: $O(1)$.

Try this approach:

Swift

final class Solution {
    func hammingWeight(_ n: UInt32) -> Int {
        n.nonzeroBitCount
    }
}

Swift notes

UInt32 prevents sign extension during right shifts. The direct scan always checks 32 positions. Kernighan’s loop runs once per set bit. Swift’s nonzeroBitCount expresses the built-in approach directly, but it hides the bit-clearing invariant an interviewer may want to see.

Summary

Approach	Time	Space
Shift + test	$O(B)$	$O(1)$
Kernighan (n &= n - 1)	$O(popcount)$	$O(1)$
Built-in bit_count	$O(1)$ on modern HW	$O(1)$

Kernighan’s is the interview-canonical trick. Know it for problem 338 and any “count bits” variant.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_191.py and run.
# Uses the canonical implementation (Approach 2: Kernighan's trick).

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

def _run_tests():
    assert hamming_weight(0b1011) == 3
    assert hamming_weight(0b10000000) == 1
    assert hamming_weight(0) == 0                # edge: zero has no set bits
    assert hamming_weight(0xFFFFFFFF) == 32      # edge: all 32 bits set
    assert hamming_weight(1) == 1
    assert hamming_weight(0b10110111) == 6
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function hammingWeight(n: number): number {
    let count = 0;
    while (n) {
        n &= n - 1;
        count++;
    }
    return count;
}

console.assert(hammingWeight(11) === 3);
console.assert(hammingWeight(128) === 1);
console.assert(hammingWeight(0) === 0);
console.assert(hammingWeight(4294967295) === 32);
console.assert(hammingWeight(1) === 1);
console.assert(hammingWeight(183) === 6);
console.log("all tests pass");

Go

func hammingWeight(n uint32) int {
    count := 0
    for n != 0 {
        n &= n - 1
        count++
    }
    return count
}

Related data structures

• None, pure bit arithmetic.

Related concepts

• Bit Manipulation, the binary representation pattern for masks, toggles, shifts, and arithmetic shortcuts.
• Math and Number Theory, the arithmetic invariant behind digits, divisibility, modulo behavior, and identities.