資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究給定集合的所有可能子集按位或的總和
問題陳述包括列印給定集合的所有可能子集的按位或的總和。
集合是相似型別資料的集合。任何集合的子集都是包含集合中某些元素或給定集合的所有元素的集合。任何集合的子集數量由 $\mathrm{2^{n}−1}$ 給出，其中 n 是給定集合中元素的數量。
例如，a={1,2,3,4,5} 是給定的集合。
{1}. {2,3}, {1,2,3,4} 等被稱為 a 的子集，因為它們包含 a 中存在的元素。我們將對給定集合的所有可能子集應用按位或運算子並對結果求和。
OR 運算子的語法
int a,b; int c= a || b;
運算子（‘||’）將返回 a 和 b 的 OR 的結果。
在這個問題中，我們將得到一個大小為 N 的陣列。我們需要找到陣列所有可能子集的 OR 並對它們求和。陣列所有子集的按位或之和將是我們需要的輸出。
讓我們用下面的例子來理解這個問題。
輸入
a[]={2, 4, 6}
輸出
36
解釋 - 我們在輸入中得到了大小為 3 的陣列。a 的子集數量將是 $\mathrm{2^{n}−1}$，即 $\mathrm{2^{3}−1=7}$。它們是 {2}, {4}, {6}, {2,4}, {2,6}, {4,6} 和 {2,4,6}。對每個子集應用 OR 運算
{2} =2
{4}=4
{6}=6
{2,4}=2 || 4=6
{2,6}= 2||6=6
{4,6}= 4||6=6
{2,4,6}= 2||4||6=6
以上是 a 的所有可能子集的 OR。所有結果的總和為 36，這是所需的輸出。
透過這種方式，我們需要計算大小為 n 的 a 的所有子集的 OR，它將等於 $\mathrm{2^{n}−1}$，並對每種情況取 OR。對每個子集應用按位或運算子後，每個子集的結果之和將是我們需要的答案。
讓我們看看解決問題的演算法。
演算法
由於任何給定大小為 n 的陣列的所有可能子集的數量可以是 $\mathrm{2^{n−1}}$。因此，為較大的 n 值生成給定陣列的所有可能子集，然後計算所有生成的子集的 OR 將花費很多執行時間，這將是解決問題的樸素方法。
相反，解決問題的有效方法可以採用陣列中所有元素的二進位制形式，並計算具有特定位為 1 的子集的數量，然後計算總和。
按位或運算子按以下方式工作
1 || 1 = 1
0 || 0 = 0
0 || 1 = 1
1 || 0 = 1
參考按位或運算子的屬性，我們可以得出結論，如果子集中任何一個元素的特定位為 1，則結果將包含該位為 1 或 0 等於 1。
我們將簡單地計算陣列中第 i 位為 0 的元素的數量，並將它們儲存在一個大小為 32 的陣列中，以獲取第 i 位為 0 的子集的數量。為此，我們將從 i=0 迭代到 i<31，然後在巢狀迴圈中迭代給定陣列以檢查陣列中每個元素的第 i 位。
我們可以透過計算特定元素和 1<<i 的按位 AND 來檢查陣列中每個元素的第 i 位。如果兩個位都是 1，則 AND 運算子返回 1，如果任何一個位為 0，則返回 0。
注意：<< 是左移運算子，它將特定數字的位左移。如果我們將 1 左移 i 位，則結果將是 1*2^i。
在計算陣列中第 i 位為 0 的元素數量後，我們可以使用公式 $\mathrm{2^{n−1}}$ 獲取我們可以使用這些元素形成的子集的數量，其中 n 將是陣列中第 i 位為 0 的元素的數量。
所有子集的按位或之和可以透過以下方式計算
$\mathrm{sum=((2^{n−1})−2^{numner\:of\:elements\:with\:ith\:bit\:0}−1)*2^{i}}$
這裡，n=給定陣列中的元素數量。
i=位數，其中 i 的範圍從 0 到 31。
如果子集中的任何元素的第 i 位為 1，則根據 OR 運算子的屬性，結果將具有該第 i 位為 1。從 0 到 31 的每個 i 的第 i 位為 1 的所有子集的總數乘以 2^i 將給出陣列所有子集的 OR 的結果總和。
因此，從所有子集的總數中減去每個元素第 i 位為 0 的子集的數量將給出第 i 位為 1 的子集的數量。
我們將使用上述演算法，這可能是解決問題的有效方法。
方法
在我們的方法中用 C++ 實現上述演算法的步驟
為了計算給定陣列的所有子集的按位或之和，我們將建立一個函式。
我們將建立一個大小為 32 的陣列來儲存具有特定位為 0 的元素的數量。
從 i=0 迭代到 i<32 以檢查陣列中每個元素的第 i 位。在巢狀 for 迴圈中迭代以使用 AND 運算子檢查每個元素的第 i 位。如果陣列中任何元素的第 i 位為 0，則對於每個第 i 位為 0 的元素，將建立的陣列中第 i 個索引處的值增加 1。
一旦我們得到了陣列中第 i 位為 0 的元素的數量，我們將在從 i=0 到 i<32 的 for 迴圈中再次迭代以計算所有可能子集的 OR 之和。
現在對於第 i 次迭代，我們將透過從陣列的所有子集的數量中減去第 i 位為 0 的子集的數量，並將結果乘以 2^i 來計算第 i 位為 1 的子集的數量，以獲得總和。我們可以使用 2^n−1 獲取第 i 位為 0 的子集的數量，其中 n 將是我們儲存在建立的陣列中的第 i 位為 0 的元素的數量。
給定陣列的所有子集的按位或總和可以透過在每次迭代後更新總和來獲得，以檢查最多 31 的每個第 i 位。
例子
//C++ code to find the sum of bitwise OR of all the subsets of the given array
#include<bits/stdc++.h>
using namespace std;
//function to calculate sum of bitwise OR of all subsets
int sum(int a[], int N){
int bits[32]={0}; //to store the number of elements with ith bit as 0
for(int i=0;i<32;i++){ //to check for every bit
for(int j=0;j<N;j++){ //to check elements with ith bit as 0
//checking ith bit of each element in the array using AND operator
//left shift 1 by i
if((a[j]&(1<<i))==0){
bits[i]++; //if ith bit is 0 of the element increase bits[i] by 1
}
}
}
int sum=0; //to store the sum of OR of all the subsets
for(int i=0;i<32;i++){ //to calculate the total sum
//number of subsets with a element with ith bit as 1 multiplied by 2^i
sum = sum + ((pow(2,N)-1)-(pow(2,bits[i])-1))*pow(2,i);
}
return sum; //return the sum
}
int main()
{
int a[]={2, 3, 7, 10, 4};
int N;
N=sizeof(a)/sizeof(a[0]); //calculating the size of the array
//calling the function
cout<<"The total sum of OR of all the subsets of a : "<<sum(a,N)<<endl;
int b[] = {5, 9, 25, 52, 32, 21, 15};
N=sizeof(b)/sizeof(b[0]);
cout<<"The total sum of OR of all the subsets of a : "<<sum(b,N)<<endl;
return 0;
}
輸出
The total sum of OR of all the subsets of a : 308 The total sum of OR of all the subsets of a : 6492
時間複雜度 - O(N)，其中 N 是給定陣列的大小。
空間複雜度 - O(1)，因為我們只建立了一個大小為 32 的陣列，使空間複雜度為 O(32)，等於 O(1)。我們正在使用恆定的空間來解決問題。
結論
本文涵蓋了計算給定陣列的所有可能子集的按位或的問題。我們在文章中提出了一個有效的技術，並在我們的方法中應用了該演算法，以在 C++ 中有效地解決問題，執行時間為 O(N)，並使用恆定空間，而不是查詢陣列的所有子集並確定 OR。
閱讀完這篇文章後，我希望您對問題和用於在 C++ 中解決問題的演算法有了更好的理解。
210 次檢視
