问题描述：给定一个长度为N的数组arr[]，任务是找到数组中每个可能的无序对的成对和的XOR。
我用这篇文章中描述的方法解决了这个问题。
我的代码：
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"表示(。
现在，如果我们将这些数字(具有设置位和未设置位的数字(配对，那么我们将在它们的和中得到一个设置位(因为我们需要得到所有对和的XOR(。
"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
此外，在这里，我们需要考虑答案的非有序对和非有序对
附言：我知道以前也有人问过同样的问题，但我无法在评论中详细解释我的问题，所以我创建了一个新帖子。我是新来的，所以请原谅我，并给我你的反馈：(
我怀疑你提到的帖子中的想法缺少了重要的细节，如果它能以所述的复杂性工作的话。(如果作者希望进一步澄清他们的方法，我很乐意更好地理解并更正。(
以下是我对至少一位作者对O(n * log n * w)解决方案的理解，其中w是最大和中的位数，以及与暴力进行随机比较的JavaScript代码，以表明它是有效的(易于翻译为C或Python(。
这个想法是一次检查一个比特的贡献。由于在任何一次迭代中，我们只关心和中的第k位是否被设置，因此我们可以删除包括高位的所有数字部分，将它们取模2^(k + 1)。
现在，必须设置第k位的和在区间中，[2^k, 2^(k + 1))(即当第k位最高时(和[2^(k+1) + 2^k, 2^(k+2) − 2](当我们同时设置了第k位和第(k+1)位时(。因此，在每个比特的迭代中，我们对输入列表(模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.");