求数组所有子集按位或的和，寻求O(nlogn)及更优复杂度解法

暴力枚举所有子集的方法虽然直观，但时间复杂度是O(2^n)，当数组长度n稍微大一点（比如n=20）就会直接超时。我们可以利用二进制位的独立性来优化，把问题拆解到每一位上计算贡献，最终得到O(n)的时间复杂度（比你要求的O(nlogn)更优）。

核心思路 #

按位或的结果中，每一位的取值是独立的——某一位最终是否为1，只和子集中是否存在至少一个元素在该位上是1有关。我们可以分别计算每一位对总和的贡献，再把所有位的贡献相加：

1. 对于第k位（从0开始计数，最低位是第0位），计算有多少个非空子集的按位或结果中该位为1。
2. 该位的总贡献 = 符合条件的子集数 × (2^{k)（因为第k位的权重是2}k）。

怎么计算符合条件的子集数？反过来想更简单：

• 总非空子集数是 2^n - 1（每个元素可选或不选，减去空集）。
• 减去所有元素第k位都是0的非空子集数，剩下的就是该位为1的子集数。
  • 如果数组中有cnt个元素的第k位是0，那么这些元素能组成的非空子集数是 2^cnt - 1。

具体步骤 #

1. 遍历每一个二进制位（通常遍历0到30位即可，覆盖32位整数的正整数范围）。
2. 对每一位k：
   • 统计数组中第k位为0的元素数量cnt_zero。
   • 计算该位为1的非空子集数：valid_subsets = (2^n - 1) - (2^cnt_zero - 1)。
   • 累加该位的贡献：total += valid_subsets × (1 << k)。
3. 最终的total就是所有子集按位或的总和。

代码实现（Python） #

def subset_or_sum(arr):
    n = len(arr)
    total = 0
    # 遍历0到30位，覆盖32位正整数的所有二进制位
    for bit_pos in range(31):
        mask = 1 << bit_pos
        count_zero = 0
        for num in arr:
            # 检查当前元素的第bit_pos位是否为0
            if (num & mask) == 0:
                count_zero += 1
        # 计算总非空子集数
        total_subsets = (1 << n) - 1
        # 计算所有元素该位都是0的非空子集数
        zero_only_subsets = (1 << count_zero) - 1
        # 得到该位为1的子集数
        valid = total_subsets - zero_only_subsets
        # 累加贡献
        total += valid * mask
    return total

# 测试示例
print(subset_or_sum([1, 2, 3]))  # 输出18，与示例结果一致

复杂度分析 #

• 时间复杂度：O(n × 31) = O(n)，因为我们只需要遍历31个二进制位，每个位遍历一次数组。
• 空间复杂度：O(1)，只用到了几个临时变量。

边界情况验证 #

比如数组包含0的情况：arr = [0, 1]，所有非空子集的按位或结果是0、1、1，总和为2。用上述函数计算：

• 第0位：count_zero=1，valid=(4-1)-(2-1)=3-1=2，贡献2×1=2。
• 高位（1到30位）：所有元素该位都是0，valid=0，贡献为0。
• 总和为2，结果正确。

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