基于拆分查找表的128位置位计算及数组1的个数实现咨询

嘿，这个问题我刚好折腾过，咱们一步步把它讲明白！拆分查找表是个效率很高的位操作技巧，尤其适合批量计算置位（也就是1的个数），完全能覆盖你说的字符串、数组甚至128位数据的需求。

简单来说，就是把大的位数据拆成固定大小的小块（通常是8位，也就是1个字节），提前预计算好每个小块的所有可能结果（比如1的个数、置位位置），然后处理数据时只需要拆分查累加/组合就行。这种方式比逐位判断快得多——毕竟预计算是一次性的，后续查表都是O(1)操作。

8位总共有256种可能的取值（0~255），我们先把每个取值对应的1的个数算好存在表里，这是整个方案的基础：

# 预计算8位字节的1的个数查找表
lookup_table = [0] * 256
for i in range(256):
    # 用bin()转二进制字符串后统计'1'的数量
    lookup_table[i] = bin(i).count('1')

如果用C语言实现，还可以用更高效的位运算逻辑预计算：lookup_table[i] = lookup_table[i >> 1] + (i & 1)，不过Python的写法已经足够清晰易懂。

字符串的每个字符本质上就是一个8位字节（ASCII编码下），直接遍历每个字符查表累加即可：

def count_ones_in_string(input_str):
    total_ones = 0
    for char in input_str:
        # 把字符转成对应的ASCII值（即8位字节的数值）
        byte_val = ord(char)
        total_ones += lookup_table[byte_val]
    return total_ones

如果是处理字节数组（比如bytes类型），逻辑更简单，直接遍历数组元素求和：

def count_ones_in_byte_array(byte_arr):
    return sum(lookup_table[byte] for byte in byte_arr)

128位刚好是16个8位字节，不管你用字节数组存储还是大整数表示，都可以拆成8位块处理：

情况1：128位数据是16字节的bytes对象 #

def count_ones_in_128bit_bytes(bit_data):
    # 确保输入是16字节的bytes
    assert len(bit_data) == 16, "128位数据必须是16字节"
    total_ones = 0
    for byte in bit_data:
        total_ones += lookup_table[byte]
    return total_ones

情况2：128位数据是整数（比如Python的大整数） #

def count_ones_in_128bit_int(num):
    total_ones = 0
    # 循环16次，每次取低8位，然后右移8位
    for _ in range(16):
        # 取当前低8位
        current_byte = num & 0xFF
        total_ones += lookup_table[current_byte]
        # 右移8位，处理下一个字节
        num = num >> 8
    return total_ones

如果你需要的不只是1的个数，还要知道哪些位是置位的（比如字符串中第3位、第10位是1），可以扩展查找表，预计算每个字节的置位位置：

# 预计算每个字节的置位位置列表（比如字节0b00000011的置位位置是[0,1]）
bit_pos_table = [[] for _ in range(256)]
for i in range(256):
    for bit_idx in range(8):
        if i & (1 << bit_idx):
            bit_pos_table[i].append(bit_idx)

def get_set_bit_positions(input_str):
    set_bits = []
    for char_idx, char in enumerate(input_str):
        byte_val = ord(char)
        # 每个字符的位偏移是 char_idx * 8，加上字节内的位位置就是全局位置
        offset = char_idx * 8
        set_bits.extend([offset + pos for pos in bit_pos_table[byte_val]])
    return set_bits

调用这个函数后，就能得到字符串中所有置位的全局位置列表啦。

内容的提问来源于stack exchange，提问作者Sohamraje137