C ++中数组中所有对的XOR之和
在这个问题中，我们得到了n个整数的数组arr[]。我们的任务是创建一个程序来查找数组中所有对的XOR之和。
让我们举个例子来了解这个问题，
Input: arr[] = {5, 1, 4}
Output: 10
Explanation: the sum of all pairs:
5 ^ 1 = 4
1 ^ 4 = 5
5 ^ 4 = 1
sum = 4 + 5 + 1 = 10解决此问题的一种简单方法是运行嵌套循环并查找所有数字对。找到每对的XOR并将它们加到总和中。
算法
Initialise sum = 0
Step 1: for(i -> 0 to n). Do:
Step 1.1: for( j -> i to n ). Do:
Step 1.1.1: update sum. i.e. sum += arr[i] ^ arr[j].
Step 2: return sum.示例
该程序说明了我们解决方案的工作原理，
#include <iostream>
using namespace std;
int findXORSum(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
sum += (arr[i]^arr[j]);
return sum;
}
int main() {
int arr[] = { 5, 1, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Sum of XOR of all pairs in an array is "<<findXORSum(arr, n);
return 0;
}输出结果
Sum of XOR of all pairs in an array is 10
该算法的时间复杂度为O(n2)，并不是解决该问题的最有效方法。
解决该问题的有效方法是使用位操作技术。
在这里，我们将考虑数字的位和每个位置。并应用下面的公式求中间和，
(number of set bits) * (number of unset bits) * (2^(bit_position))
为了找到最终的和，我们将所有位的中间和相加。
我们的解决方案是使用64位整数值。对于这种方法，我们需要位数。
算法
Initialize sum = 0, setBits = 0, unsetBits = 0. Step 1: Loop for i -> 0 to 64. repeat steps 2, 3. Step 2: Reset setBits and unsetBits to 0. Step 3: For each element of the array find the value of setBits and unsetBits. At ith position. Step 4: update sum += (setBits * unsetBits * (2i))
示例
该程序说明了我们解决方案的工作原理，
#include <iostream>
#include <math.h>
using namespace std;
long findXORSum(int arr[], int n) {
long sum = 0;
int unsetBits = 0, setBits = 0;
for (int i = 0; i < 32; i++) {
unsetBits = 0; setBits = 0;
for (int j = 0; j < n; j++) {
if (arr[j] % 2 == 0)
unsetBits++;
else
setBits++;
arr[j] /= 2;
}
sum += ( unsetBits*setBits* (pow(2,i)) );
}
return sum;
}
int main() {
int arr[] = { 5, 1, 4, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Sum of XOR of all pairs in an array is "<<findXORSum(arr, n);
return 0;
}输出结果
Sum of XOR of all pairs in an array is 68