c++ - 数组中每个无序对的成对和的异或

Question

问题描述:给定一个长度为 N 的数组 arr[]，任务是找到数组中每个可能的无序对的成对和的异或。
我使用 this 中描述的方法解决了这个问题邮政。
我的代码:

int xorAllSum(int a[], int n)
{
    int curr, prev = 0;
    int ans = 0;
    for (int k = 0; k < 32; k++) {
        int o = 0, z = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] & (1 << k)) {
                o++;
            }
            else {
                z++;
            }
        }

        curr = o * z + prev;
        if (curr & 1) {
            ans = ans | (1 << k);
        }
        prev = o * (o - 1) / 2;
    }
    return ans;
}

代码描述:我正在找出每一位，我们的答案是否会设置该位。因此，要为每个位位置执行此操作，我找到在该位置具有设置位的所有数字的计数(在代码中由 'o' 表示)以及在该位置具有未设置位的数字的计数(用“z”表示)。
现在，如果我们将这些数字配对(将设置位和未设置位的数字放在一起，那么我们将在它们的总和中得到一个设置位(因为我们需要对所有对和进行异或)。
包括“prev”的因素以说明结转位。现在我们知道，只有在我们进行 XOR 运算时设置位的数量是“奇数”时，答案才会在当前位置有一个设置位。
但我没有得到正确的输出。谁能帮帮我吗
测试用例 :

n = 3, a[] = {1, 2, 3} => (1 + 2) ^ (1 + 3) ^ (2 + 3)

=> 3 ^ 4 ^ 5 = 2
=> 输出:2

n = 6
a[] = {1 2 10 11 18 20}
输出:50

n = 8
a[] = {10 26 38 44 51 70 59 20}
输出:182

约束条件:2 <= n <= 10^8
另外，这里我们需要考虑 UNORDERED PAIRS 而不是 Ordered Pairs 来回答
PS:我知道之前有人问过同样的问题，但我无法在评论中用这么多细节来解释我的问题，所以我创建了一个新帖子。我是新来的，所以请原谅我并给我你的反馈:)

Answer 1

我怀疑这个想法在post you referred to缺少重要的细节，如果它可以在声明的复杂性下工作。 (如果作者希望进一步澄清他们的方法，我很乐意更好地理解和纠正。)
这是我对至少一位作者 intention 的理解对于 O(n * log n * w)解决方案，其中 w是最大总和中的位数，以及与蛮力进行随机比较以表明其有效的 JavaScript 代码(可轻松转换为 C 或 Python)。
这个想法是一次检查每个位的贡献。由于在任何一次迭代中，我们只对 k 是否存在感兴趣。和中的第 th 位被设置，我们可以删除数字的所有部分，包括高位，取它们每个模 2^(k + 1) .
现在，总和必须具有 k第 1 位设置在区间中，[2^k, 2^(k + 1)) (即 k 位最高时)和 [2^(k+1) + 2^k, 2^(k+2) − 2] (当我们同时设置了 k th 和 (k+1) th 位时)。所以在每一位的迭代中，我们对输入列表进行排序(模2^(k + 1))，对于每个左被加数，我们递减一个指向两个区间中每个区间末尾的指针，并二分搜索相关的起始索引。

// 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.");