LeetCode 191 Number of 1 Bits - Example and Complexity Analysis

Trace Brian Kernighan's trick on n = 12 (binary: 1100).

Iteration 1: n & (n-1) = 1100 & 1011 = 1000. count = 1. Iteration 2: n & (n-1) = 1000 & 0111 = 0000. count = 2. n = 0. Done.

Answer: $2$ set bits.

Compare to checking all bits: 12 in binary is 1100. Two 1s.

Brian Kernighan: $O(k)$ where $k$ is number of set bits. Basic approach: $O(32)$. Both are $O(1)$ for fixed-width integers. Space: $O(1)$.