資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學給定集合所有可能子集的按位與之和
你如何理解問題“給定集合所有可能子集的按位與之和”？讓我們來解讀一下。
這個問題要求找到給定集合所有可能子集的按位與之和。
讓我們用一個例子來理解這個問題。假設我們有一個集合 {1, 2, 3}。這個集合的可能子集是什麼？
可能的子集是 {1}，{2}，{3}，{1,2}，{1,3}，{2,3} 和 {1,2,3}。現在讓我們計算每個子集的按位與。
這些子集的按位與可以按如下方式計算：
子集 |
按位與 |
註釋 |
|---|---|---|
{1} |
1 |
|
{2} |
2 |
|
{3} |
3 |
|
{1,2} |
0 |
1 的二進位制表示是 001，2 的二進位制表示是 010，所以兩者的與是 000 |
{1,3} |
1 |
1 的二進位制表示是 001，3 的二進位制表示是 011，所以兩者的與是 001 |
{2,3} |
2 |
2 的二進位制表示是 010，3 的二進位制表示是 011，所以兩者的與是 010 |
{1,2,3} |
00 |
1 的二進位制表示是 001，2 的二進位制表示是 010，3 的二進位制表示是 011，所以所有數的與是 000 |
這些按位與的和是 1+2+3+0+1+2+0 = 9。這個值 9 是集合 {1,2,3} 所有可能子集的按位與之和。
方法
現在，我們已經理解了問題要求我們做什麼。讓我們看看我們將用來解決這個問題的方法。
獲取集合的大小和元素作為使用者輸入
執行一個迴圈，該迴圈遍歷集合直到集合中的最大值
對於每次迭代，執行另一個迴圈，該迴圈遍歷集合的所有元素以計算具有設定位的整數個數和第一位置、第二位置等。
在這個迴圈中，我們還使用公式 subsets = (1LL << numbersWithBitSet) - 1 計算可能的子集數
現在結束迴圈，對於內迴圈的每次迭代，使用公式 total += bit * subsets 在變數中計算總和，其中`subsets`是可能的子集數，bits 是外迴圈中使用的迭代，其增加方式為 bit = bit << 1
仍然很困惑？讓我們用一個例子來理解它
假設我們有一個集合 ={1,2,3} = {001,010,011}
現在我們建立一個迴圈，該迴圈迭代所有集合元素。
對於迭代 1，bit = 1 = 001
現在我們有一個內迴圈來計算具有設定的第一位元素的個數。
要計算這個值，請使用 bit & i（這裡 i 是集合的元素）
001 & 001 = 1
001 & 010 = 0
001 & 011= 1
因此，我們得到 2 個第一位設定為 1 的數字。
可以使用第一位設定形成的子集總數 = 1 << 2 - 1 = 3，其中 2 是第一位設定為 1 的數字的計數
我們可以將所有按位與的和儲存在一個變數中 total = total + bits * subsets (010 * 3 = 6)
類似地，對於第二次迭代，我們將有值 3，而第三次迭代不會發生，因為位值超過集合中的最大值。
Total = 6+3 =9
C++ 程式碼實現
理論太多了？現在，讓我們直接進入程式碼。
以下是 C++ 程式碼實現，用於計算給定集合所有可能子集的按位與之和。
示例
#include <iostream>
#include <vector>
using namespace std;
void print_and_Subsets(const vector<int>& set) {
long long total = 0; // Use "long long" instead of "long" for 64-bit integers
for (int bit = 1; bit != 0; bit <<= 1) {
int numbersWithBitSet = 0;
for (int i : set) {
if ((i & bit) != 0) numbersWithBitSet++;
}
long long subsets = (1LL << numbersWithBitSet) - 1; // Use "1LL" instead of "1L" for 64-bit integers
total += bit * subsets;
}
cout << "Result: " << total << endl;
}
int main() {
int n = 5;
vector<int> set = {1, 2, 3, 4, 5};
print_and_Subsets(set);
return 0;
}
輸出
Result: 25
空間複雜度：O(N)
時間複雜度：O(N * log M)
結論
在本文中，我們介紹瞭如何使用位掩碼計算給定集合所有可能子集的按位與之和。希望您能夠更好地掌握這個概念。繼續學習！
126 次瀏覽
