求集合所有非空子集的最小与最大元素的按位或之和

这个问题我之前也遇到过，暴力枚举所有非空子集肯定行不通——当集合元素超过20个时，2^20已经是百万级，再往上直接爆炸。最优思路是按二进制位独立分析贡献，因为按位或的每一位是独立的，我们只需要计算每一位在最终总和里的贡献，再累加即可。

核心思路 #

按位或的特性是：只要min或max的某二进制位为1，结果的该位就为1。反过来想，我们可以先计算总非空子集数，减去那些min|max该位为0的子集数，得到该位为1的子集数，再乘以该位的权重（2^k）就是这一位的贡献。

具体来说：

• 设集合S有n个元素，总非空子集数为2^n - 1；
• 对于第k位（从0开始计数，对应权重2^k）：
  1. 统计S中第k位为0的元素数量m；
  2. 这些m个元素组成的非空子集，它们的min和max的第k位必然都是0（因为所有元素该位都是0），所以这类子集的min|max第k位为0，数量是2^m - 1；
  3. 因此，第k位为1的子集数为：(2^n - 1) - (2^m - 1) = 2^n - 2^m；
  4. 该位的贡献为：(2^n - 2^m) * (1 << k)；
• 累加所有位的贡献，就是最终结果。

示例验证（S={1,2,3}） #

把集合元素转成二进制：1(01)、2(10)、3(11)

• 第0位（权重1）：第0位为0的元素是2，m=1。贡献=(8-2)1=61=6；
• 第1位（权重2）：第1位为0的元素是1，m=1。贡献=(8-2)2=62=12；
• 更高位都是0，贡献为0；
  总和=6+12=18，和题目示例一致。

代码实现（Python） #

def calculate_total_or_sum(S):
    n = len(S)
    total_sum = 0
    # 遍历0到30位，覆盖绝大多数整数场景
    for bit_pos in range(31):
        mask = 1 << bit_pos
        count_zero_bit = 0
        for num in S:
            if (num & mask) == 0:
                count_zero_bit += 1
        # 计算当前位的有效子集数
        valid_subsets = (1 << n) - (1 << count_zero_bit)
        # 累加当前位的贡献
        total_sum += valid_subsets * mask
    return total_sum

# 测试示例
print(calculate_total_or_sum({1,2,3}))  # 输出18
print(calculate_total_or_sum({4,5}))    # 输出14，验证正确

时间复杂度分析 #

这个方法的时间复杂度是O(n * 31)，也就是O(n)，即使n是1e5级别的超大集合，也能在瞬间计算完成，完全碾压暴力枚举的O(2^n)。

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