Counting Bits, Missing Number, and Reverse Bits
Compute bit counts for 0..n using DP and the lowest-set-bit trick, find a missing number via XOR, and reverse the bits of a 32-bit integer.
Counting Bits, Missing Number, and Reverse Bits is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Counting Bits Problem Overview
The Counting Bits problem (LeetCode 338) asks: given n, return an array ans of size n+1 where ans[i] is the number of 1 bits in i. The naive approach is O(n log n) — count bits in each number individually. The DP approach is O(n) by exploiting the relationship between i and its half or lowest-set-bit.
Two key observations power the DP: (1) i >> 1 drops the lowest bit, so bits[i] = bits[i >> 1] + (i & 1). (2) Clearing the lowest set bit: bits[i] = bits[i & (i-1)] + 1. Both give O(n) time and O(n) space (for the output array).
def count_bits_v1(n):
# O(n log n): naive individual count
return [bin(i).count('1') for i in range(n + 1)]
def count_bits_dp(n):
# O(n): DP using right shift
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 1) # i >> 1 drops last bit
return dp
def count_bits_dp2(n):
# O(n): DP using lowest-set-bit trick
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i & (i - 1)] + 1 # i & (i-1) clears lowest set bit
return dp
n = 10
print('Naive:', count_bits_v1(n))
print('DP v1:', count_bits_dp(n))
print('DP v2:', count_bits_dp2(n))Why the DP Recurrences Work
For the right-shift recurrence dp[i] = dp[i >> 1] + (i & 1): dividing by 2 (right shift) removes the last bit. If the last bit was 1, the count increases by 1; if 0, no change. So bits[i] = bits[i // 2] + (i mod 2).
For the lowest-set-bit recurrence dp[i] = dp[i & (i-1)] + 1: i & (i-1) clears the rightmost 1 bit, so it has one fewer set bit than i. The count is therefore that reduced value's count plus 1. Both recurrences process i in increasing order so smaller sub-problems are always solved first.
# Trace both recurrences for i = 0..8
print('i | i>>1 | i&1 | dp[i>>1]+(i&1) | i&(i-1) | 1+dp[i&(i-1)]')
print('-' * 60)
dp = [0] * 9
for i in range(1, 9):
# Right shift method
v1 = dp[i >> 1] + (i & 1)
# Lowest set bit method
v2 = dp[i & (i - 1)] + 1
dp[i] = v1 # either works
print(f'{i:2d} ({bin(i)[2:]:4s}) | {i>>1:2d} | {i&1} | {v1} | {i&(i-1):2d} | {v2}')
print('\nFinal dp:', dp)Missing Number: XOR and Sum Approaches
The Missing Number problem (LeetCode 268) gives an array of n distinct numbers in [0, n] with exactly one missing. The XOR approach: XOR all indices 0..n with all values in the array. Pairs cancel, leaving the missing number. The sum approach: expected = n*(n+1)//2, return expected - sum(nums).
Both are O(n) time and O(1) space. The XOR approach is more robust in languages with fixed-width integers (avoids potential overflow). In Python, both work fine since integers have arbitrary precision.
def missing_xor(nums):
n = len(nums)
result = n
for i, val in enumerate(nums):
result ^= i ^ val # each index i cancels its matching value
return result
def missing_sum(nums):
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
test_cases = [
[3, 0, 1], # missing 2
[0, 1], # missing 2
[9,6,4,2,3,5,7,0,1], # missing 8
[0], # missing 1
]
for nums in test_cases:
print(f'{nums} => XOR={missing_xor(nums)}, Sum={missing_sum(nums)}')Reverse Bits of a 32-Bit Integer
The Reverse Bits problem (LeetCode 190) asks you to reverse the binary representation of a 32-bit unsigned integer. The iterative approach: process each of the 32 bits from right to left in the input, placing them from left to right in the output. Each iteration: extract the rightmost bit with n & 1, shift the output left to make room, OR in the bit, then right-shift n.
After 32 iterations, the output integer contains all 32 bits of n in reversed order. This is O(32) = O(1) per call, or O(1) amortised with caching for repeated calls on 8-bit chunks.
def reverse_bits(n):
result = 0
for _ in range(32):
result = (result << 1) | (n & 1) # shift result left, OR in rightmost bit
n >>= 1 # move to next bit
return result
# Test with known values
print(reverse_bits(0b00000010100101000001111010011100)) # 964176192
print(reverse_bits(0b11111111111111111111111111111101)) # 3221225471
print(reverse_bits(0)) # 0
print(reverse_bits(1)) # 2147483648 (bit 0 goes to bit 31)
print(reverse_bits(0b10000000000000000000000000000000)) # 1Reverse Bits: Divide and Conquer
A faster O(log 32) = O(1) approach reverses bits using a divide-and-conquer swap. First swap adjacent bits, then swap adjacent 2-bit groups, then 4-bit groups, and so on. Each level of swapping uses masks to separate alternating groups and shift to interleave them. After 5 swaps, all 32 bits are reversed.
This approach uses O(1) fixed operations regardless of input and is used in hardware implementations. The masks are constants: 0x55555555 (alternating 01 pattern), 0x33333333 (alternating 0011), 0x0f0f0f0f (alternating 00001111), etc.
def reverse_bits_dc(n):
# Treat n as 32-bit unsigned
n &= 0xFFFFFFFF
# Swap adjacent bits
n = ((n & 0x55555555) << 1) | ((n >> 1) & 0x55555555)
# Swap adjacent 2-bit groups
n = ((n & 0x33333333) << 2) | ((n >> 2) & 0x33333333)
# Swap adjacent 4-bit groups
n = ((n & 0x0f0f0f0f) << 4) | ((n >> 4) & 0x0f0f0f0f)
# Swap adjacent bytes
n = ((n & 0x00ff00ff) << 8) | ((n >> 8) & 0x00ff00ff)
# Swap adjacent 16-bit halves
n = ((n & 0x0000ffff) << 16) | ((n >> 16) & 0x0000ffff)
return n & 0xFFFFFFFF
# Verify against iterative version
def reverse_bits_iter(n):
result = 0
for _ in range(32):
result = (result << 1) | (n & 1); n >>= 1
return result
for test in [0b10110100, 0b11111111, 0, 1, 0xDEADBEEF]:
assert reverse_bits_dc(test) == reverse_bits_iter(test)
print(f'{test:#010x} reversed: {reverse_bits_dc(test):#010x}')Number of 1 Bits (Hamming Weight)
The Number of 1 Bits problem (LeetCode 191) asks for the Hamming weight (popcount) of an unsigned integer. Three approaches with different trade-offs: naive loop (O(32)), Brian Kernighan (O(k) where k = set bits), and Python's built-in n.bit_count() (3.10+).
The Brian Kernighan method is preferred in interviews because it demonstrates understanding of the n & (n-1) trick. Each iteration removes the lowest set bit, so the loop runs exactly as many times as there are 1-bits — much faster than a full 32-bit scan for sparse integers.
def hamming_weight_naive(n):
count = 0
while n:
count += n & 1
n >>= 1
return count
def hamming_weight_kernighan(n):
count = 0
while n:
n &= n - 1 # clear lowest set bit
count += 1
return count
# Python 3.10+
# def hamming_weight_builtin(n): return n.bit_count()
for n in [0, 1, 11, 128, 255, 0xDEADBEEF]:
naive = hamming_weight_naive(n)
kern = hamming_weight_kernighan(n)
bits = bin(n).count('1')
print(f'{n:#012b} ({n:10d}): naive={naive}, kern={kern}, bin={bits}')Sum of Consecutive Bits: Prefix Approach
Sometimes you need to count 1 bits in a range [l, r] quickly. Build a prefix sum of set bits for 0..n: prefix[i] = prefix[i-1] + bin(i).count('1'). Then the count for range [l, r] is prefix[r] - prefix[l-1]. This enables O(1) range queries after O(n) preprocessing.
This generalises to any bit-based aggregate over a range. For example, counting numbers in [l, r] with an even number of set bits uses the same prefix technique but with a different accumulation function.
def build_bit_prefix(n):
prefix = [0] * (n + 2)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + bin(i).count('1')
return prefix
def count_bits_range(prefix, l, r):
return prefix[r] - prefix[l - 1]
# Build prefix for 0..15
prefix = build_bit_prefix(15)
print('Prefix sums (set bit counts up to i):')
for i in range(16):
print(f' i={i:2d} ({bin(i)[2:]:4s}): bits={bin(i).count("1")}, prefix={prefix[i]}')
# Range queries
print(f'\nSet bits in [5, 10]: {count_bits_range(prefix, 5, 10)}')
print(f'Set bits in [1, 15]: {count_bits_range(prefix, 1, 15)}')Reverse Bits for Negative Numbers
In Python, integers are signed and have arbitrary width. When reversing bits for the LeetCode problem, we must treat the input as a 32-bit unsigned integer. Mask the input with & 0xFFFFFFFF before processing to ensure only 32 bits are considered. The output should also be an unsigned 32-bit integer (non-negative).
If you are given a Python integer that may be negative (in a two's-complement sense), first apply & 0xFFFFFFFF to get the unsigned 32-bit representation, then reverse. The result is always a non-negative integer between 0 and 2^32 - 1.
def reverse_bits_signed_safe(n):
n &= 0xFFFFFFFF # treat as 32-bit unsigned
result = 0
for _ in range(32):
result = (result << 1) | (n & 1)
n >>= 1
return result & 0xFFFFFFFF
# Python treats -1 as all 1s in two's complement
print(f'-1 as 32-bit unsigned: {-1 & 0xFFFFFFFF:#010x}') # 0xffffffff
print(f'Reversed: {reverse_bits_signed_safe(-1):#010x}') # 0xffffffff (all 1s reversed = all 1s)
# -2 in 32-bit = 0xFFFFFFFE = 11...10
print(f'-2 as 32-bit unsigned: {-2 & 0xFFFFFFFF:#010x}') # 0xfffffffe
print(f'Reversed: {reverse_bits_signed_safe(-2):#010x}') # 0x7fffffffBit Manipulation DP: Counting Bits Patterns
The counting-bits problem reveals a general pattern for bit DP: if you know the answer for a smaller version of i, you can compute it for i using a constant-time bit operation. This pattern generalises to other bit-counting problems, such as counting numbers with exactly k set bits in [0, n] (use binary enumeration) or the highest power of two dividing each number.
Another useful observation: the set-bit count for i follows the repeating pattern within each power-of-two interval. The pattern for [2^k, 2^(k+1) - 1] is the same as for [0, 2^k - 1] with each value incremented by 1, because bit k is always set in this range.
# Visualise the repeating pattern
def show_bit_pattern(n):
bits = [bin(i).count('1') for i in range(n + 1)]
print('i | bits | pattern')
for i, b in enumerate(bits):
block = i.bit_length() - 1 if i > 0 else 0
print(f'{i:2d} ({bin(i)[2:]:4s}) | {b} | block {block}')
return bits
bits = show_bit_pattern(15)
# Verify the pattern: bits[i] = bits[i - highest_power] + 1 for i >= 2^k
print('\nVerify pattern:')
for i in range(1, 16):
highest_pow = 1 << (i.bit_length() - 1)
if highest_pow < i:
prev_i = i - highest_pow
print(f'bits[{i}] = bits[{prev_i}] + 1 = {bits[prev_i]} + 1 = {bits[i]}')Combining All Three: An Integrated Exercise
Many interview problems combine bit counting, missing-number logic, and bit reversal in one question. For example: given an array where elements are n-bit integers and one is missing, find the missing value. Or: given a stream of bit counts, reconstruct the missing integer. These require recognising which sub-technique applies.
Practice building a mental map: if a problem mentions finding missing elements, think XOR or sum. If it says 'count 1s efficiently', think Kernighan or DP. If it says 'reverse bits', think iterative or divide-and-conquer. These are the three core tools of bit manipulation in interviews.
# Integrated exercise: given bit-count array, find the missing number
# arr[i] = number of 1 bits in i, for all i in 0..n except one
# Reconstruct the missing number
def find_missing_from_bit_counts(bit_counts, n):
# Rebuild full count array
full = [bin(i).count('1') for i in range(n + 1)]
# Find which index is missing by comparing
for i, count in enumerate(bit_counts):
if full[i] != count:
return i - 1 # the entry before the mismatch is missing
return n # last element missing
# Simpler: use XOR on indices matching bit counts
# (This is simplified for illustration)
bits = [0,1,1,2,1,2,2,3,0,1] # bit counts for 0..9 with 8 missing
# Normal: [0,1,1,2,1,2,2,3,1,2]
# Missing is index 8
full = [bin(i).count('1') for i in range(10)]
missing_idx = None
for i in range(10):
if i >= len(bits) or bits[i] != full[i]:
missing_idx = i
break
print(f'Missing number: {missing_idx}')Bit Caching for Reverse Bits
For repeated calls to reverse bits (e.g., in a hardware simulation), cache results for 8-bit chunks. Since each byte can take only 256 values, precompute the reversed byte for each value 0-255. To reverse a 32-bit integer, split it into four 8-bit chunks, reverse each, and reassemble in reverse order.
This reduces each call to four table lookups and bit operations — much faster than a 32-iteration loop for bulk processing. The cache is built once in O(256 × 8) time and reused for all subsequent calls in O(1).
# Build 8-bit reverse cache
def build_reverse_byte_cache():
cache = [0] * 256
for i in range(256):
n, result = i, 0
for _ in range(8):
result = (result << 1) | (n & 1)
n >>= 1
cache[i] = result
return cache
cache = build_reverse_byte_cache()
def reverse_bits_cached(n):
return (cache[n & 0xFF] << 24 |
cache[(n >> 8) & 0xFF] << 16 |
cache[(n >> 16) & 0xFF] << 8 |
cache[(n >> 24) & 0xFF])
# Test
for test in [0b10110100, 0b11111111, 0x12345678]:
cached = reverse_bits_cached(test)
# Reference: iterative
n, result = test, 0
for _ in range(32): result = (result << 1) | (n & 1); n >>= 1
assert cached == result
print(f'{test:#010x} => {cached:#010x}')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: counting bits uses DP with dp[i] = dp[i >> 1] + (i & 1) or dp[i] = dp[i & (i-1)] + 1 for O(n) time, missing number is solved in O(n)/O(1) by XOR-ing all indices with all values or using the arithmetic sum formula, and reversing 32 bits is done iteratively in O(32) or with the divide-and-conquer mask technique. Next up we explore monotonic stacks, starting with the increasing vs decreasing invariant and next-greater-element queries.
Frequently asked questions
Is the “Counting Bits, Missing Number, and Reverse Bits” lesson free?
Yes — the full text of “Counting Bits, Missing Number, and Reverse Bits” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Counting Bits, Missing Number, and Reverse Bits”?
Compute bit counts for 0..n using DP and the lowest-set-bit trick, find a missing number via XOR, and reverse the bits of a 32-bit integer. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Counting Bits, Missing Number, and Reverse Bits” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Bitwise Operators: AND, OR, XOR, NOT, Shifts
- Single Number and XOR Properties
- Bit Masks: Set, Clear, Toggle, Check
- Counting Bits, Missing Number, and Reverse Bits