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 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)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