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