整数数组中所有两数之和的异或值

Question

我们有一个数组 A，例如 [1, 2, 3]。我想找到数组中所有整数对的和的异或值。
虽然可以通过遍历所有的整数对来轻松地在O(n^2)时间复杂度内解决这个问题（其中n是数组的大小），但我想改进解决方案的时间复杂度。任何改进时间复杂度的答案都很好。
例如，对于上面的示例数组A，答案将是(1+2)^(1+3)^(2+3) = 2。因为成对元素是 (1,2), (1,3), (2,3)，且3 ^ 4 ^ 5 = 2。

- hosein_bidaki

Answer 1

这是我对至少一个作者intention的理解，用O(n * log n * w)的解决方案，其中w是最大和中位数的位数。

思路是逐位检查每个位的贡献。由于我们只关心在任何一次迭代中是否设置了和的第k位，因此我们可以删除包括更高位的所有数字部分，将它们各自模为2^(k + 1)。

现在，必然会有kth位设置的总和位于区间[2 ^ k, 2 ^(k + 1))和[2^(k+1) + 2^k, 2^(k+2) − 2]中。因此，我们对输入列表（模为2^(k + 1)）进行排序，并为每个左边的加数减少指向两个区间末尾的指针，并二分搜索相关的起始索引。

以下是JavaScript代码，随机比较暴力方法以展示其工作原理（可轻松转换为C或Python）:

// https://stackoverflow.com/q/64082509
// Returns the lowest index of a value
// greater than or equal to the target
function lowerIdx(a, val, left, right){
  if (left >= right)
    return left;
  mid = left + ((right - left) >> 1);
  if (a[mid] < val)
    return lowerIdx(a, val, mid+1, right);
  else
    return lowerIdx(a, val, left, mid);
}

function bruteForce(A){
  let answer = 0;
  for (let i=1; i<A.length; i++)
    for (let j=0; j<i; j++)
      answer ^= A[i] + A[j];
  return answer;
}
  
function f(A, W){
  const n = A.length;
  const _A = new Array(n);
  let result = 0;

  for (let k=0; k<W; k++){
    for (let i=0; i<n; i++)
      _A[i] = A[i] % (1 << (k + 1));
    _A.sort((a, b) => a - b);

    let pairs_with_kth_bit = 0;
    let l1 = 1 << k;
    let r1 = 1 << (k + 1);
    let l2 = (1 << (k + 1)) + (1 << k);
    let r2 = (1 << (k + 2)) - 2;
    let ptr1 = n - 1;
    let ptr2 = n - 1;

    for (let i=0; i<n-1; i++){
      // Interval [2^k, 2^(k+1))
      while (ptr1 > i+1 && _A[i] + _A[ptr1] >= r1)
        ptr1 -= 1;
      const idx1 = lowerIdx(_A, l1-_A[i], i+1, ptr1);
      let sum = _A[i] + _A[idx1];
      if (sum >= l1 && sum < r1)
        pairs_with_kth_bit += ptr1 - idx1 + 1;

      // Interval [2^(k+1)+2^k, 2^(k+2)−2]
      while (ptr2 > i+1 && _A[i] + _A[ptr2] > r2)
        ptr2 -= 1;
      const idx2 = lowerIdx(_A, l2-_A[i], i+1, ptr2);
      sum = _A[i] + _A[idx2]
      if (sum >= l2 && sum <= r2)
        pairs_with_kth_bit += ptr2 - idx2 + 1;
    }

    if (pairs_with_kth_bit & 1)
      result |= 1 << k;
  }
  return result;
} 
 
var As = [
  [1, 2, 3], // 2
  [1, 2, 10, 11, 18, 20], // 50
  [10, 26, 38, 44, 51, 70, 59, 20] // 182
];

for (let A of As){
  console.log(JSON.stringify(A));
  console.log(`DP, brute force: ${ f(A, 10) }, ${ bruteForce(A) }`);
  console.log('');
}

var numTests = 500;

for (let i=0; i<numTests; i++){
  const W = 8;
  const A = [];
  const n = 12;
  for (let j=0; j<n; j++){
    const num = Math.floor(Math.random() * (1 << (W - 1)));
    A.push(num);
  }

  const fA = f(A, W);
  const brute = bruteForce(A);
  
  if (fA != brute){
    console.log('Mismatch:');
    console.log(A);
    console.log(fA, brute);
    console.log('');
  }
}

console.log("Done testing.");

- גלעד ברקן

Answer 2

这里有一个O(nw)时间复杂度的解决方案，其中w是机器字长的大小（通常为64或其他常数）。最重要的是计算具有特定位设置的对数，其奇偶性决定了结果中是否设置该位。目标是在O(n)时间内计数而不是O(n^2)。

找到结果的最右位最容易。计算有多少输入数字在最右位上为0（即有多少个偶数），以及有多少个为1（即有多少个奇数）。具有1的右位的和的对数等于这两个计数的乘积，因为一对必须有一个奇数和一个偶数才能使它的总和为奇数。当且仅当此乘积为奇数时，结果在最右位置上有一个1。

找到结果的第二个右边最多的位有点难。我们可以采用相同的技巧，计算有多少个元素在该位置上有或没有1，然后将这些计数乘起来；但是我们还需要计算从两个数字的第一位都为1的和中进入第二位的1位数有多少个。幸运的是，我们可以使用前一个阶段的计数来计算它；它是由公式k * (k-1)/2给出的对数的数量，其中k是在前一个位置上具有1位的数量。这可以添加到该阶段的乘积中，以确定第二位有多少个1位。

每个阶段需要O(n)时间来计算适当位置上具有0位或1位的元素的数量。通过重复此过程w次，我们可以在O(nw)时间内计算出所有w位结果。我会把实际实现留给你。

- kaya3

---

由于 w 是一个常数，这不会使其变成 O(n) 吗？尽管它会有相当大的比例常数，但数组的大小会渐近地支配单词的固定大小。 - pjs

@pjs 当然，实际上它的时间复杂度是O(n)，因为在真实机器上w是一个常数。我提到w因完整性而已，因为原则上它是问题规范中的参数（即使每个操作在两台机器上的时间相同，算法在8位机器上的8位整数上与在64位机器上的64位整数上的运行速度不同）。举个例子，Sean Erol Anderson的流行的“位操作技巧”网页也以字长来给出了一些算法的时间复杂度供比较。 - kaya3

但是，由于大O实际上是关于问题规模如何扩展而不是有多快的问题，所以w在洗涤中出现了 - 它在运行时间比例中被取消。 - pjs

从理论上讲，并不总是假定字长是一个常量，否则会产生荒谬之处，即固定的字长意味着您可以在O(1)时间内计数n，因为只有2^w个不同的整数，这是一个常量；或者计算跨多个O(1)字长的整数操作的运行时间的复杂性。因此，在字RAM模型中，w不是一个常量，这意味着时间复杂度有时以w表示，例如在查找融合树时为O(log_w n)。 - kaya3

FYI，我在这里的顶部段落中提到了这个答案。链接 - גלעד ברקן

一旦我们数出“有多少个1位从这些和中进入了第二位，其中这两个数字在第一位都是1”，那么我们如何告诉第二位和后面的位，有多少个1的进位到一个现在考虑进位前会产生0的和对和上，以及有多少个1的进位到一个现在考虑进位前已经在当前位是1的和对上？如果我们无法区分这一点，那么如何使用您的方法确定有多少个和在当前位设置了1呢？ - elena a