Micro-Drill #56 — Count set bits (Brian Kernighan)

Divide & Conquer Target: 10s

Counting set bits via n &= n-1 runs in O(k) where k is the number of set bits.

count = 0
while n:
    n &amp;= n - 1
    count += 1

Type it from memory. Go.