C++数组中所有对的异或和

在这个问题中，我们给定一个包含n个整数的数组arr[]。我们的任务是创建一个程序来查找数组中所有对的异或和。

让我们来看一个例子来理解这个问题：

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

解决这个问题的一个简单方法是运行嵌套循环并找到所有数字对。找到每一对的异或，并将它们添加到总和中。

算法

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.

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

程序演示了我们解决方案的工作原理：

 在线演示

#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

更新于：2020年8月17日

2K+ 次浏览

启动你的职业生涯

完成课程获得认证

开始学习
广告