← All Foundations

Bit Manipulation

Foundation drill for this topic

Drill #83 — Count set bits

Easy Bit Counting

In plain English: Count how many 1s appear in the binary form of a number.

n & (n-1) clears the lowest set bit each time — loop until n is zero and count the iterations.

Prompt

Count the number of 1-bits (set bits) in the binary representation of a non-negative integer.

Try to write it from scratch before scrolling down.

Solution

def count_bits(n):
    count = 0
    while n:
        n &= n - 1  # clear lowest set bit
        count += 1
    return count

# Test: count_bits(11) == 3  (1011 in binary)
# Test: count_bits(128) == 1  (10000000)
# Test: count_bits(0) == 0
O(k) time where k = number of set bits · O(1) space

Related Micro Drills

Quick recall drills to reinforce this pattern.

253 Hamming distance (count differing bits) Interval & Math 10s

XOR marks differing bits, then Brian Kernighan's trick counts them in O(k) where k is the number of set bits.

xor = x ^ y
count = 0
while xor:
    xor &= xor - 1  # clear lowest set bit
    count += 1
59 Count nodes Tree Traversal 10s

Recursive node counting teaches divide-and-conquer tree thinking.

def count(node):
    if not node: return 0
    return 1 + count(node.left) + count(node.right)
264 Count connected components Graph Exploration 15s

Loop over all nodes, DFS/BFS from unvisited ones, increment count each time. Works on adjacency list or matrix.

visited = set()
count = 0
for node in range(n):
    if node not in visited:
        count += 1
        stack = [node]
        while stack:
            cur = stack.pop()
            if cur in visited: continue
            visited.add(cur)
            stack.extend(graph[cur])
See all drills in Bit Manipulation →