求C#中统计按位与结果为2的幂的数组无序对的最优解法

架构老林

2026-10-3

优化方案

核心思路

你原来的暴力解法时间复杂度为O(n²)，当n达到2e5时运算量高达4e10次，必然出现性能问题。结合题目给出的约束arr[i] ≤ 2^12（即最大取值为4095），我们可以通过频率统计的方法将复杂度降至O(4096² + n)，完全可以在毫秒级完成计算。
具体实现逻辑：

先统计数组中每个数字的出现次数，存入长度为4096的频率数组
枚举所有满足a ≤ b的数字组合，避免重复统计无序对
对每对数字判断按位与的结果是否为2的幂，符合条件就根据频率计算对应对数累加到结果中

实现代码

public static long CountPairs(List<int> arr)
{
    // arr[i]最大为4095，直接在栈上分配频率数组，无堆内存开销
    Span<int> freq = stackalloc int[4096];
    foreach (int num in arr)
    {
        freq[num]++;
    }

    long result = 0;

    // 枚举所有a<=b的组合，避免重复计数
    for (int a = 0; a < 4096; a++)
    {
        if (freq[a] == 0) continue;
        // 计算相同数字的组合数
        int andVal = a & a;
        if (IsPowerOfTwo(andVal))
        {
            result += (long)freq[a] * (freq[a] - 1) / 2;
        }
        // 计算和更大数字的组合数
        for (int b = a + 1; b < 4096; b++)
        {
            if (freq[b] == 0) continue;
            if (IsPowerOfTwo(a & b))
            {
                result += (long)freq[a] * freq[b];
            }
        }
    }

    return result;
}

// 无需额外缓存，直接判断性能足够
private static bool IsPowerOfTwo(int number)
{
    return number != 0 && (number & (number - 1)) == 0;
}