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

この問題を解決する簡単な方法の1つは、ネストされたループを実行して、数値のすべてのペアを見つけることです。各ペアの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