資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學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.
示例
程式演示了我們解決方案的工作原理：
#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+ 次瀏覽
廣告