求10^5规模32位二进制数组各二进制位的1的计数方案

嘿，其实这个问题用基础的位操作就能轻松搞定，完全能应对10^5规模的数组，性能上绝对没问题。

核心思路 #

我们只需要初始化一个长度为32的计数数组（对应32位二进制的每一位），然后遍历目标数组中的每个数字，逐个检查它的每一位是否为1，对应位的计数就加1。因为32是固定常数，整个算法的时间复杂度其实是O(n)（n是数组规模），对10^5的数据来说完全不在话下。

代码示例（Python） #

def count_each_bit_ones(arr):
    # 初始化32位的计数数组，初始值全为0
    bit_counts = [0] * 32
    for num in arr:
        for bit_pos in range(32):
            # 用位与操作检查当前位是否为1
            if num & (1 << bit_pos):
                bit_counts[bit_pos] += 1
    return bit_counts

为什么这个方案可行？ #

• 总操作次数是10^5 * 32 = 3.2×10^6次，现代CPU每秒能处理数十亿次操作，这个计算量完全不会有性能瓶颈。
• 位操作1 << bit_pos用来生成对应位的掩码，num & 掩码可以快速判断该位是否为1，是最直接高效的位检查方式。

额外优化思路（可选） #

如果想进一步减少循环次数，可以利用分治法统计位（比如把32位分成高低16位，分别统计），但对于32位来说，这种优化带来的收益微乎其微，反而会增加代码复杂度，所以直接遍历每一位是最简洁高效的选择。

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