求解数组选元素与所有元素异或求和最大值的O(n)优化方法

核心思路 #

异或是按位独立的运算：两个数异或结果的每一位取值，仅和两个数对应二进制位的值有关，不会干扰其他位的计算，因此我们可以单独统计每个二进制位对最终总和的贡献，不用逐对计算异或结果。
具体逻辑：

• 先遍历一次数组，统计每个二进制位上，数组元素值为1的总个数cnt1，对应位为0的个数自然是N - cnt1
• 对于任意选中的元素x：
  • 如果x的第k位是0：那么x和数组元素异或后，该位得1的情况，刚好是和该位为1的元素运算的场景，总共有cnt1次，这一位对总和的贡献就是cnt1 * (1 << k)（1<<k就是2的k次方，即该位的位权）
  • 如果x的第k位是1：那么x和数组元素异或后，该位得1的情况，是和该位为0的元素运算的场景，总共有N - cnt1次，贡献为(N - cnt1) * (1 << k)
• 统计完所有位的1的计数后，再遍历一次数组，对每个元素按上面的规则快速算出对应的异或总和，记录最大值即可。

整个过程只需要两次遍历数组，二进制位的数量是固定常数（常规整型最多32位，长整型64位），因此整体时间复杂度是O(n)，远优于暴力法的O(n²)。

代码实现 #

def compute(N, A):
    # 统计32个二进制位上1的出现次数，覆盖常规整数取值范围
    bit_one_count = [0] * 32
    for num in A:
        for bit in range(32):
            if num & (1 << bit):
                bit_one_count[bit] += 1
    
    max_xor_sum = 0
    for selected in A:
        current_sum = 0
        for bit in range(32):
            bit_weight = 1 << bit
            if selected & bit_weight:
                # 当前选中数该位为1，和0异或得1
                current_sum += (N - bit_one_count[bit]) * bit_weight
            else:
                # 当前选中数该位为0，和1异或得1
                current_sum += bit_one_count[bit] * bit_weight
        max_xor_sum = max(max_xor_sum, current_sum)
    return max_xor_sum

示例验证 #

用题目给出的样例输入测试：

• N=3，A=[15(二进制1111), 11(二进制1011), 8(二进制1000)]
• 统计各位1的数量：
  • 第0位（位权1）：15、11该位为1，计数2
  • 第1位（位权2）：15、11该位为1，计数2
  • 第2位（位权4）：仅15该位为1，计数1
  • 第3位（位权8）：三个数该位均为1，计数3
  • 更高位全为0
• 计算选中15时的总和：15所有低4位都是1，因此每一位贡献为(3-对应位计数)*位权，总和为(3-2)*1 + (3-2)*2 + (3-1)*4 + (3-3)*8 = 1+2+8+0=11，和样例输出完全一致。

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