191. Number of 1 Bits

At a Glance

• Topic: bit-manipulation
• Pattern: Brian Kernighan trick (Bit Manipulation)
• Difficulty: Easy
• Companies: Apple, Microsoft, Google, Amazon, Meta
• Frequency: High
• LeetCode: 191

Problem (one-liner)

Return Hamming weight of an unsigned 32-bit integer: count of 1 bits in binary representation.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• "Number of 1 bits" / popcount
• Clear lowest set bit repeatedly — sublinear in bit width

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — check all 32 positions — O(32) time.
• Optimal — Brian Kernighan: value &= value - 1 removes lowest set bit — O(popcount) time.

Optimal Solution

Go

package main

func hammingWeight(value uint32) int {
	count := 0
	for value != 0 {
		// clear the lowest set bit: isolates one 1 per iteration
		value &= value - 1
		count++
	}
	return count
}

JavaScript

function hammingWeight(value) {
	let count = 0;
	let remaining = value >>> 0;
	while (remaining !== 0) {
		remaining &= remaining - 1;
		count++;
	}
	return count;
}

Walkthrough

value = 0b1011

Invariant: each step eliminates exactly one 1 bit.

Edge Cases

• Zero → 0
• 0xFFFFFFFF → 32

Pitfalls

• JS signed shift — use >>> for unsigned operations
• Treating parameter as signed int32 — mask if needed

Similar Problems

• 338. Counting Bits — popcount for every prefix size.
• 190. Reverse Bits — bit rearrangement companion.

Variants

• Compute parity (xor of bits) in log steps.
• Population count on 64-bit.

Mind-Map Tags

#popcount #brian-kernighan #lowest-set-bit #bit-tricks