如何高效计算二进制字符串对应位不同位数？解决TLE问题

嘿，你的问题我太懂了——原来的逐位循环异或方法在数据量一大就超时，对吧？这很正常，纯Python的字符遍历效率确实拉胯，咱们换个更高效的思路：利用整数位运算替代逐字符操作，底层的C实现可比Python循环快太多了！

问题根源 #

原代码的时间复杂度是O(n*m)，n是数组长度，m是二进制字符串的长度。当n或m很大时，循环次数直接爆炸，自然就触发超时了。

优化方案：整数位运算+统计1的个数 #

二进制字符串可以直接转成整数，两个整数异或后，结果里的每一位1就代表原数对应位不同。我们只需要统计异或结果中1的个数，就能得到单个字符串和目标的差异位数，再累加所有结果即可。

代码实现（Python 3.10+）

def req_fun(arr, b):
    target = int(b, 2)  # 把目标二进制字符串转成整数
    total_diff = 0
    for s in arr:
        num = int(s, 2)
        # 异或后统计1的个数，bit_count()是Python3.10新增的高效方法
        total_diff += (num ^ target).bit_count()
    return total_diff

兼容旧Python版本的写法

如果你的Python版本低于3.10，用bin(x).count('1')替代bit_count()就行，虽然稍慢一点，但还是比原方法快很多：

def req_fun(arr, b):
    target = int(b, 2)
    total_diff = 0
    for s in arr:
        num = int(s, 2)
        total_diff += bin(num ^ target).count('1')
    return total_diff

额外优化：处理重复字符串 #

如果你的数组里有大量重复的二进制字符串，可以先用Counter统计频率，避免重复计算，进一步提升效率：

from collections import Counter

def req_fun(arr, b):
    target = int(b, 2)
    str_counter = Counter(arr)
    total_diff = 0
    for s, count in str_counter.items():
        num = int(s, 2)
        diff_bits = (num ^ target).bit_count()
        total_diff += diff_bits * count
    return total_diff

验证示例 #

拿你给出的例子测试：arr=['1100']，b='1010'

• 1100转整数是12，1010转整数是10
• 异或结果：12 ^ 10 = 6（二进制0110）
• 统计1的个数是2，和示例结果一致，完全正确！

内容的提问来源于stack exchange，提问作者p.ram