查找数组的异或

Question

我有一个长度为 n 的数组 A 和一个长度为 m 的数组 B。我必须找到以下值。

 long ans=0;
 for(int i:B)
    {
           xor=0;
           for(int j:A) xor+=j^i;
           ans+=xor
    }
print ans

时间复杂度为 O(N*M)。总之我必须找到这个值

(A1^B1+A2^B1+A3^B1+A4^B1+A5^B1.....) + (A1^B2+A2^B2 +A3^B2+A4^B2+A5^B2.....)+ (A1^B3+A2^B3+A3^B3+A4^B3+A5^B3.......)....... .等等
如何以更好的时间复杂度找到这个值？我认为 XOR 不是关联的 所以我们不能采取简单的方法吗？

Answer 1

这里有一个建议：

let zeroes = number of zeroes in A;
let ones = number of ones in A;
let sum = 0;

for every i in B:
    if i == 0:
        sum += ones
    else:
        sum += zeroes
print sum;

如果我没记错的话，这个算法应该是O(N+M)。

Answer 2

考虑一个特定的位（比如第 10 个）。假设数组的长度为 100，并且有 19 个元素的第 10 位设置为 A，还有 22 个元素的第 10 位设置为 B。集合 (A[i]^B[j] for i=1..N, for j=1..M) 中有多少元素的第 10 位已设置？好吧，它需要在 A[i] 中而不是在 B[j] 中设置位，反之亦然。所以有 19*(100-22) + (100-19)*22 个元素设置了第 10 位。这个计算表明我们可以有效地逐位求和。

更准确地说，假设您有 32 位整数。对于 0..31 中的每个 i，让我们计算 A 和 B 中设置了该位的元素的数量。假设我们在 A 中有 a[i] 个元素，在 B 中有 b[i] 个元素，第 i 个位被设置。

使用与上述相同的想法，这第 i 位的异或之和将为整体结果贡献 (a[i]*(len(B)-b[i]) + (len(A)-a[i])*b[i]) << i。

这为您提供了一个简单的 O((N+M)k) 解决方案（其中 k 是数组中任何 int 中的最大位数）。

这里有一些 Python 代码实现了这个想法，包括一些针对原始版本的随机测试：

def sum_xor(A, B):
    s = 0
    for i in xrange(32):
        ai = sum((a >> i) & 1 for a in A)
        bi = sum((b >> i) & 1 for b in B)
        s += (ai*(len(B)-bi) + (len(A)-ai)*bi) << i
    return s

def sum_xor_slow(A, B):
    s = 0
    for a in A:
        for b in B:
            s += a^b
    return s

import random

all_ok = True
for trials in xrange(100):
    A = [random.randrange(1<<32) for _ in xrange(random.randrange(100, 110))]
    B = [random.randrange(1<<32) for _ in xrange(random.randrange(100, 110))]
    x0 = sum_xor(A, B)
    x1 = sum_xor_slow(A, B)
    ok = x0 == x1
    all_ok = all_ok and ok
    print 'OK' if ok else 'FAIL', x0, x1
assert all_ok

实用说明：在 A 和 B 上迭代一次并在两个数组中同时累积 32 位计数可能会更快，因为这样可以最大限度地减少内存读取。（事实上，这就是我的代码的第一个版本的工作方式）。但是我把代码改成了上面的，因为这样简单很多，复杂度也一样。

查找数组的异或

Find Xor of an Array

algorithm

binary

numbers

bit-manipulation

bitmask