求与给定整数集中所有元素汉明距离≤k的整数个数

嘿，我懂你现在的难处——学校编程作业里的这个汉明距离统计问题确实有点挠头，尤其是当你搜遍全网找不到靠谱提示，自己写的解法还慢得离谱的时候。咱们一起来捋清楚怎么搞定它！

问题明确 #

给定整数向量v和整数k，统计存在多少个整数，使其与v中所有整数的汉明距离（转换为原整数需翻转的比特数）均≤k。例如当v={0000, 0001}、k=2时，符合条件的整数包括{0000, 0001, 0010, 0011, 0100, 0101, 1000, 1001}，总共8个。

先聊聊低效解法的问题 #

我猜你最开始的思路可能是遍历所有可能的整数，挨个检查它和v里每个元素的汉明距离是否都达标？如果是这样的话，当比特位数n稍微大一点（比如n=20），2^20已经超过百万，再加上v的长度不小，效率肯定会崩——这确实不是最优解。

高效解法的核心思路 #

核心就是利用汉明球的交集：每个v中的元素都对应一个“汉明球”（所有和它汉明距离≤k的整数集合），我们要算的就是所有这些球的交集大小。

步骤1：先确定统一的比特长度n

首先得明确所有整数的比特位数——比如例子里是4位。如果输入的是十进制整数，就取v中最大数的比特位数；如果是二进制字符串，直接取字符串长度就行，总之要统一所有数的比特长度。

步骤2：高效生成并筛选汉明球

直接生成所有可能的数肯定不行，我们可以从第一个元素的汉明球开始，逐步和后续元素的汉明球求交集，每次只保留符合当前约束的数：

1. 以v的第一个元素为基准，生成所有和它汉明距离≤k的数的集合S；
2. 遍历v中剩下的每个元素，对S里的每个数做检查：如果这个数和当前元素的汉明距离≤k，就保留，否则剔除；
3. 最终S的大小就是答案。

而生成初始汉明球的时候，不用暴力遍历所有数，而是用组合生成的方式：比如要生成和基准数距离≤k的数，就是生成所有翻转0到k个比特的组合，再和基准数异或得到对应的数，这样能省去大量无效计算。

步骤3：快速计算汉明距离

计算两个整数x和y的汉明距离，直接用位运算就够了：比如在Python里用bin(x ^ y).count('1')，比手动逐位检查快得多。

示例代码（Python） #

def count_valid_numbers(v, k, n):
    # 生成与基准数汉明距离<=k的所有数
    def generate_hamming_ball(base, max_flips, bit_length):
        ball = set()
        
        # 递归生成所有翻转m个比特的组合
        def backtrack(pos, remaining_flips, current):
            if remaining_flips == 0:
                ball.add(current)
                return
            if pos >= bit_length:
                return
            # 不翻转当前位
            backtrack(pos + 1, remaining_flips, current)
            # 翻转当前位
            flipped = current ^ (1 << pos)
            backtrack(pos + 1, remaining_flips - 1, flipped)
        
        # 生成翻转0到k个比特的所有情况
        for m in range(0, k+1):
            backtrack(0, m, base)
        return ball
    
    # 处理输入：如果是二进制字符串，转成整数
    if isinstance(v[0], str):
        v = [int(num, 2) for num in v]
    
    # 初始汉明球
    valid_numbers = generate_hamming_ball(v[0], k, n)
    
    # 遍历剩余元素，过滤不符合条件的数
    for num in v[1:]:
        valid_numbers = {x for x in valid_numbers if bin(x ^ num).count('1') <= k}
        if not valid_numbers:  # 提前终止，已经没有符合条件的数了
            break
    
    return len(valid_numbers)

# 测试示例
v = ["0000", "0001"]
k = 2
n = 4
print(count_valid_numbers(v, k, n))  # 输出8

进阶优化方向 #

如果n特别大（比如n=30），初始汉明球的元素数量可能会爆炸（比如k=10时，组合数C(30,10)超过3千万），这时候可以试试这些优化：

• 先对v去重，避免重复计算；
• 利用分治思想，把v分成几组，先算每组的交集，再合并；
• 提前剪枝：如果当前交集已经为空，直接终止计算。

内容的提问来源于stack exchange，提问作者Karel Křesťan