資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中所有可能子集的異或和
在這個問題中，我們給定一個包含n個數字的陣列aar[]。我們的任務是建立一個程式來找到所有可能子集的異或和。
在這裡，我們將找到陣列的所有子集。然後，對於每個子集，我們將找到子集元素的異或，並將它們新增到sum變數中。
讓我們舉個例子來理解這個問題：
Input: arr[] = {5, 1, 4}
Output: 20
Explanation: XOR of all subsets:
{5} = 5
{1} = 1
{4} = 4
{5, 1} = 4
{5, 4} = 1
{1, 4} = 5
{5, 1, 4} = 0
Sum of XOR = 5 + 1 + 4 + 4 + 1 + 5 = 20解決這個問題的一個簡單方法是使用迴圈找到陣列的所有可能子集，然後對於每個子集找到所有元素的異或並更新sum。最後返回sum。
這並不是一個有效的方法，對於較大的值，時間複雜度將呈指數增長。
一種有效的方法是利用異或的特性。在這裡，我們將找到陣列所有元素的異或，並檢查位。如果第i位被設定，則使用(2^(n-1+i))更新sum。
示例
程式說明我們解決方案的工作原理：
#include <iostream>
#include <math.h>
using namespace std;
int subSetXORSum(int arr[], int n) {
int bitOR = 0;
for (int i=0; i < n; ++i)
bitOR |= arr[i];
return (bitOR * pow(2, n-1));
}
int main() {
int arr[] = {1, 5, 4};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Sum of XOR of all possible subsets is "<<subSetXORSum(arr, size);
}輸出
Sum of XOR of all possible subsets is 20
更新於：2020年8月17日
354 次瀏覽
廣告