如何用Java高效计算数组所有子集的按位与之和？

当然有！你的当前实现通过枚举所有2ⁿ个子集来计算，时间复杂度是O(n×2ⁿ)——这个复杂度在n超过20之后会变得非常慢（比如n=30时需要执行30亿次操作）。我们可以通过分析每个二进制位的贡献，把时间复杂度降到O(n×k)（k是整数的二进制位数，比如32或64），即使n是10万级别的数据也能轻松处理。

核心原理 #

对于每个二进制位pos（比如从0到31），只有当一个子集里所有元素的第pos位都是1时，这个子集的按位与结果的第pos位才会是1。我们只需要统计：

1. 数组中有多少个元素的第pos位是1，记为count。
2. 这样的有效子集数量是2^count - 1（所有由这count个元素组成的非空子集，因为空集的按位与通常不纳入你的计算范围）。
3. 该位对总和的贡献就是(2^count - 1) × (1 << pos)（子集数量乘以该位的权重）。

把所有位的贡献相加，就是最终的总和。

修正你的原代码问题 #

顺便提一句：你的原代码里sum初始化为1是错误的——当枚举到空子集（i=0）时，sum会保留1并加到总和里，导致结果比预期多1（比如你的例子会输出10而不是9）。如果要保留枚举子集的思路，应该从i=1开始循环（只枚举非空子集），或者把sum初始化为全1（比如0xffffffff）再处理空集的情况。

高效实现的Java代码 #

public class Main {
    static int subsetBitwiseAndSum(int[] set) {
        int total = 0;
        int bitCount = 32; // 假设处理32位整数
        for (int pos = 0; pos < bitCount; pos++) {
            int mask = 1 << pos;
            int count = 0;
            // 统计当前位为1的元素个数
            for (int num : set) {
                if ((num & mask) != 0) {
                    count++;
                }
            }
            if (count == 0) {
                continue; // 没有元素该位为1，贡献为0
            }
            // 计算该位的总贡献：(2^count - 1) * 位权重
            long validSubsets = (1L << count) - 1;
            total += validSubsets * mask;
        }
        return total;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        System.out.println(subsetBitwiseAndSum(arr)); // 输出9，符合预期
    }
}

复杂度对比 #

• 原方法：O(n×2ⁿ)，仅适用于n≤20的场景。
• 新方法：O(n×32)=O(n)，可以处理n非常大的数组（比如n=10^5）。

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