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.

Recognition Cues

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

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