查找数组的异或

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

考虑一个特定的位(比如第 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 位计数可能会更快，因为这可以最大限度地减少内存读取。(事实上，这就是我代码的第一个版本的工作方式)。但是我将代码更改为上述代码，因为它更简单并且具有相同的复杂性。

Answer 2

这里有一个建议：

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)。