Pattern this teaches:Bit Manipulation
Counting Bits
An easy Bit Manipulation interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Bit Manipulation
- Sheets
- 2
- Core for
- 9 roles
The problem
For every whole number i from 0 up to num, count how many 1 bits appear when i is written in binary. Return those counts as an array whose position i holds the count for i.
Example 1
- Input
- num = 2
- Output
- [0, 1, 1]
- Why
- 0 in binary is 0 (zero 1's). 1 in binary is 1 (one 1). 2 in binary is 10 (one 1).
Example 2
- Input
- num = 5
- Output
- [0, 1, 1, 2, 1, 2]
- Why
- 0->0, 1->1, 2->10->1, 3->11->2, 4->100->1, 5->101->2 ones respectively.
Constraints
- 0 <= num <= 10^5
How to think about it
Updated 2026-09-29Every integer i has an identical binary structure to i shifted right by one, except for its least significant bit. That means the set-bit count of i is already known the instant i >> 1 has been computed. Counting bits for an entire sequence is a dynamic programming recurrence, not a series of isolated bit-counts.
Approaches, worst first
Independent bit count per number
time O(n log n) · space O(1)
Compute the population count of each integer from 0 to num independently using bitwise masks or Kernighan cycles. Simple, but discards all shared subproblem work across the numbers.
Dynamic programming with lowest set bit
time O(n) · space O(1)
Notice that clearing the lowest bit via i & (i - 1) always yields a strictly smaller integer whose count is already memoized in ans. Setting ans[i] = ans[i & (i - 1)] + 1 builds the table in one linear pass.
Dynamic programming with right shiftWrite this one
time O(n) · space O(1)
Express each value as ans[i] = ans[i >> 1] + (i & 1). Because right-shifting halves the index, the required lookup is always computed beforehand, executing with minimal bitwise primitives and optimal sequential memory locality.
Where people lose marks · 3
- Allocating an array of size num instead of num + 1 drops the value for num itself, failing the boundary right at the top.
- Writing `ans[i >> 1] + i & 1` without parentheses binds addition before bitwise AND in most languages, calculating `(ans[i >> 1] + i) & 1` and returning erroneous zeroes and ones.
- Assuming num = 0 requires a special condition; properly initializing `ans[0] = 0` and sizing to num + 1 naturally handles the zero-only edge case.
The theory behind it
Bit Manipulation — the ground this problem stands on. All Bit Manipulation problems
What Bit Manipulation is
Bit manipulation is the practice of working directly on the individual ones and zeros that form numbers in computer memory. Every integer is stored as a tiny row of electrical switches that are either on or off. Instead of running arithmetic loops, bitwise operations flip, mask, shift, or combine these switches in a single hardware cycle. This allows compact storage of sets and blazing-fast checks without allocating extra memory.
When to reach for it
Reach for bit manipulation when problems ask to find a unique non-duplicate number, count set bits, determine if a value is a power of two, or pack a set of small booleans into a single integer. Prompts mentioning constant O(1) auxiliary space constraints on array queries often hint at XOR cancellation. It is also the foundation of bitmask dynamic programming, where subsets of up to twenty items are tracked as integer masks.
How the pattern works
Think of an integer as a fixed-length set of flags. Use bitwise AND to inspect if a specific bit is set, bitwise OR to turn a bit on, and bitwise XOR to flip a bit or cancel out matched pairs. Learn the standard bit tricks: n AND with n minus one clears the lowest set bit, which counts ones quickly, while n AND with negative n isolates the lowest set bit. When packing sets into masks, represent the empty set as zero and add item i by shifting one left by i and combining with OR.
More Bit Manipulation problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .