如何降低统计数组中XOR大于AND的数对的算法时间复杂度？

问题回顾 #

给定元素范围为1到2^{30、长度可达10}5的数组，需统计所有满足a XOR b > a AND b的数对（i,j）数量（i<=j）。原O(n²)算法无法处理大数据量，需优化。

条件等价转换 #

先拆解a XOR b和a AND b的二进制特性：

• a XOR b：对应二进制位不同时为1，相同时为0
• a AND b：对应二进制位都为1时为1，否则为0

比较两者大小的核心看最高有效位：

• 若a和b的最高有效位不同：假设a的最高位是k（1），b的最高位是m（1）且k>m。此时a XOR b的最高位是k（1），而a AND b的最高位最多是m，显然a XOR b > a AND b，条件成立。
• 若a和b的最高有效位相同：此时a AND b的最高位就是该位（两者该位都是1），而a XOR b的该位为0，其最高有效位必然低于该位，因此a AND b > a XOR b，条件不成立。

结论：数对满足条件当且仅当两个数的最高有效位不同。

优化算法思路 #

1. 统计每个最高有效位对应的数字个数：遍历数组，对每个数计算其最高有效位，记录到计数数组中。
2. 计算总对数：总共有n*(n+1)//2个（i<=j的数对总数）。
3. 计算同最高位的数对总数：对每个最高有效位的计数c，同组内的数对数量为c*(c+1)//2，求和得到所有同组对数。
4. 最终答案 = 总对数 - 同最高位对数之和。

时间复杂度为O(n)，完全适配1e5规模的数组。

优化后代码 #

def solve(array):
    n = len(array)
    # 最高有效位范围是0到30（因为2^30的最高位是第30位，从0开始计数）
    cnt = [0] * 31
    for num in array:
        # 计算当前数的最高有效位
        msb = num.bit_length() - 1
        cnt[msb] += 1
    total = n * (n + 1) // 2
    same = 0
    for c in cnt:
        if c > 0:
            same += c * (c + 1) // 2
    return total - same

示例验证 #

以数组[4,3,5,2]为例：

• 各数的最高有效位：
  • 4（100）→ 2
  • 3（11）→ 1
  • 5（101）→ 2
  • 2（10）→1
• cnt数组：cnt[1]=2，cnt[2]=2，其余为0
• 总对数：4*5//2=10
• 同组对数：(23//2)+(23//2)=3+3=6
• 答案：10-6=4，与示例结果一致。

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