位计数、缺失数字与位反转
使用 DP 和最低有效置位技巧计算 0..n 的位计数，通过 XOR 找出缺失数字，并反转 32 位整数的所有位。
位计数、缺失数字与位反转 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
位计数问题概览
位计数问题（LeetCode 338）要求：给定 n，返回一个大小为 n+1 的数组 ans，其中 ans[i] 是 i 中 1 位的数量。朴素方法需要 O(n log n) 时间，即分别统计每个数字中的位。DP 方法利用 i 与其一半或最低置位位之间的关系，将时间复杂度降为 O(n)。
DP 由两个关键观察驱动：(1) i >> 1 会去掉最低位，因此 bits[i] = bits[i >> 1] + (i & 1)。(2) 清除最低置位位：bits[i] = bits[i & (i-1)] + 1。两种方法的时间复杂度都是 O(n)，空间复杂度都是 O(n)（用于输出数组）。
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))为何 DP 递推式成立
对于the 右移递推式 dp[i] = dp[i >> 1] + (i & 1)：除以 2（右移）会移除最后一位。如果最后一位是 1，计数增加 1；如果是 0，则不变。因此，bits[i] = bits[i // 2] + (i mod 2)。
对于最低置位位递推式 dp[i] = dp[i & (i-1)] + 1：i & (i-1) 会清除最右侧的 1 位，因此它比 i 少一个置位位。所以，计数就是该缩小后数值的计数加 1。两种递推式都按 i 递增的顺序处理，因此较小的子问题总会先得到解决。
# 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)缺失数字：XOR 与求和方法
缺失数字问题（LeetCode 268）给定一个包含 n 个互不相同数字的数组，这些数字属于 [0, n]，其中恰好缺少一个数字。XOR 方法：将索引 0..n 与数组中的所有值进行 XOR。成对的值会相互抵消，最后留下缺失数字。求和方法：expected = n*(n+1)//2，返回 expected - sum(nums)。
两种方法的时间复杂度都是 O(n)，空间复杂度都是 O(1)。在使用固定宽度整数的语言中，XOR 方法更加稳健，因为它可以避免潜在的溢出。在这种语言中，两种方法都能正常工作，因为整数具有任意精度。
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)}')反转 32 位整数中的位
位反转问题（LeetCode 190）要求您反转一个 32 位无符号整数的二进制表示。迭代方法是：从输入值的右向左处理 32 个位，并将它们从左向右放入输出值。每次迭代都要使用 n & 1 提取最右侧的位，将输出值左移以腾出空间，使用 OR 运算放入该位，然后将 n 右移。
经过 32 次迭代后，输出整数将包含 n 的全部 32 个位，只是顺序相反。该方法的复杂度为 O(32) = O(1)（每次调用），对于使用 8 位块的重复调用，配合缓存后摊销复杂度为 O(1)。
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)) # 1位反转：分治法
一种更快的 O(log 32) = O(1) 方法使用分治交换来反转位。首先交换相邻位，然后交换相邻的 2 位组，再交换 4 位组，以此类推。每一层交换都使用掩码分离交替的位组，并通过移位将它们交错合并。经过 5 次交换后，全部 32 个位都会被反转。
无论输入是什么，该方法都只使用 O(1) 个固定操作，因此用于硬件实现。掩码是常量：0x55555555（交替的 01 模式）、0x33333333（交替的 0011）、0x0f0f0f0f（交替的 00001111）等。
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}')1 位数量（汉明重量）
1 位数量问题（LeetCode 191）要求计算一个无符号整数的汉明重量（1 位计数）。有三种权衡不同的方法：朴素循环（O(32)）、克尼汉方法（O(k)，其中 k = 置位位的数量），以及内置的 n.bit_count()（3.10 及更高版本）。
面试中通常推荐克尼汉方法，因为它展示了对 n & (n-1) 技巧的理解。每次迭代都会移除最低置位位，因此循环恰好运行与 1 位数量相同的次数——对于稀疏整数，这比完整扫描 32 位快得多。
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}')连续位计数：前缀方法
有时您需要快速统计范围 [l, r] 中的 1 位数量。为 0..n 建立一个置位位前缀和：prefix[i] = prefix[i-1] + bin(i).count('1')。然后，范围 [l, r] 的计数为 prefix[r] - prefix[l-1]。预处理需要 O(n) 时间，之后即可用 O(1) 时间回答范围查询。
这种方法可以推广到范围上的任何基于位的聚合。例如，要统计 [l, r] 中具有偶数个置位位的数字，可以使用相同的前缀技术，只需更换累加函数。
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)}')负数的位反转
在这种语言中，整数带符号且位宽任意。对于 LeetCode 问题中的位反转，我们必须将输入视为32 位无符号整数。处理前使用 & 0xFFFFFFFF 对输入进行掩码，以确保只考虑 32 个位。输出也应是一个无符号的 32 位整数（非负数）。
如果给定的整数可能为负数（按照二进制补码的含义），请先对其应用 & 0xFFFFFFFF，得到无符号的 32 位表示，然后再进行反转。结果始终是介于 0 和 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}') # 0x7fffffff位操作 DP：位计数模式
位计数问题揭示了位 DP 的一个通用模式：如果您知道较小版本 i 的答案，就可以通过一次常数时间的位操作计算 i 的答案。该模式还可以推广到其他位计数问题，例如统计 [0, n] 中恰好有 k 个置位位的数字（使用二进制枚举），或者求每个数字的最大二次幂因子。
另一个有用的观察是：在每个二次幂区间内，i 的置位位数量会呈现重复模式。区间 [2^k, 2^(k+1) - 1] 的模式与 [0, 2^k - 1] 相同，只是每个值都增加了 1，因为在这个范围内第 k 位始终为置位状态。
# 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]}')综合练习：结合三种方法
许多面试题会将位计数、缺失数字逻辑和位反转结合在一个问题中。例如：给定一个数组，其中的元素是 n 位整数且缺少一个值，找出缺失的值。或者：给定一个位计数数据流，重建缺失的整数。这些问题要求您识别应使用哪种子技术。
请练习建立思维导图：如果问题提到查找缺失元素，请考虑 XOR 或求和。如果问题要求“高效地统计 1 的数量”，请考虑克尼汉方法或 DP。如果问题要求“反转位”，请考虑迭代法或分治法。这三种方法是面试中位操作的核心工具。
# 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}')位反转缓存
对于重复执行的位反转调用（例如在硬件模拟中），请为 8 位块缓存结果。由于每个字节只能取 256 个值，因此可以预先计算 0-255 中每个值的反转字节。要反转一个 32 位整数，请将其拆分为四个 8 位块，分别反转，然后按相反顺序重新组合。
这样，每次调用只需进行四次表查找和位操作——批量处理时比 32 次迭代的循环快得多。缓存只需使用 O(256 × 8) 时间构建一次，之后的所有调用都可以用 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}')快速检查
检查您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课介绍了：位计数使用 DP，通过 dp[i] = dp[i >> 1] + (i & 1) 或 dp[i] = dp[i & (i-1)] + 1，在 O(n) 时间内完成，缺失数字可以通过将所有索引与所有值进行 XOR，或使用算术求和公式，在 O(n)/O(1) 时间和空间复杂度下解决，以及32 位反转可以通过 O(32) 的迭代方法，或使用分治掩码技术完成。接下来我们将学习单调栈，从递增与递减不变量以及下一个更大元素查询开始。
常见问题解答
「位计数、缺失数字与位反转」课时是免费的吗？
是的 — 「位计数、缺失数字与位反转」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「位计数、缺失数字与位反转」这节课中我会学到什么？
使用 DP 和最低有效置位技巧计算 0..n 的位计数，通过 XOR 找出缺失数字，并反转 32 位整数的所有位。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「位计数、缺失数字与位反转」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。