arrays - 数组中所有成对整数和的异或

Question

A例如，我们有一个数组[1, 2, 3]。我想找到数组中所有整数对的 SUM 的 XOR。
虽然这可以通过传递所有对很容易地完成O(n^2)（数组的大小在哪里n），但我想提高解决方案的时间复杂度？任何提高时间复杂度的答案都会很棒。
例如，对于上述示例数组 ，A答案将是(1+2)^(1+3)^(2+3) = 2。由于成对元素是(1,2), (1,3), (2,3)和3 ^ 4 ^ 5 = 2。

Answer 1

这是 O(nw) 时间内的解决方案的一个想法，其中 w 是机器字的大小（通常为 64 或其他常数）。最重要的是计算有多少对将设置一个特定的位，这个数字的奇偶性决定了该位是否会在结果中设置。目标是用 O(n) 时间而不是 O(n ² ) 计算。

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

找到结果的倒数第二位有点困难。我们可以做同样的技巧，计算有多少元素有和没有 1，然后取这些计数的乘积；但是我们还需要从两个数字都为 1 的总和中计算有多少 1 位被带入第二位。幸运的是，我们可以使用前一阶段的计数来计算它；它是公式 k*(k-1)/2 给出的对数，其中 k 是前一个位置为 1 位的对数。这可以在这个阶段添加到产品中，以确定第二个位置有多少个 1。

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

Answer 2

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

这个想法是一次检查每个位的贡献。由于我们只对k总和中的第 th 位是否在任何一次迭代中设置感兴趣，我们可以删除所有包含更高位的数字部分，并将它们取模2^(k + 1)。

现在，必须k设置第 th 位的总和位于区间[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.");