iT邦幫忙

0

【c++標準函式庫(STL)筆記】bitset 介紹

c++

今天學習c++裡面的bitset工具,
感覺蠻實用的,自己筆記一下

bitset簡介

特色: 只由0和1組成,方便的做位元運算
(若是int或long long最多也就32位與64位,bitset可以超過64位)

一、引入函式庫

要使用bitset,需要在程式開頭加入這兩行

#include <bitset>
using namespace std;

二、宣告

bitset的宣告方式如下:
(例如說宣告100個bit的bitset)

bitset<100> b;

宣告的同時初始化

  1. 直接以整數初始化
bitset<100> b = 1; //或bitset<100> b(1)
  1. 以長整數初始化
bitset<100> b(222UL);
  1. 以字串初始化
s = "100110101";
bitset<100> b(s);

三、位元運算

  1. AND 運算
b = b0 & b1;
  1. OR 運算
b = b0 | b1;
  1. XOR 運算
b = b0 ^ b1;
  1. index運算(從右往左數的位數)
b[0] = 1;
  1. 左移運算
b = b0 << 2;
  1. 右移運算
b = b0 >> 2;
  1. 每個位元反向
b = ~b0;

四、輸入與輸出(cin, cout)

  1. cin
bitset<8> b;
cin >> b; //假設輸入1010
cout << b << endl;

結果:
00001010

  1. cout
    顯示 b 之內容,長度為 b.size(),
    範例:
bitset<8> b(string("11011"));
cout << b << endl;

結果:
00011011

應用: 子集合和問題

意外發現bitset適合拿來解這樣子的一個經典問題,
給你一個集合(元素可重複),一個目標正整數target,
判斷是否有子集合的和 = target

範例程式:

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

/*
函數功能: 檢查陣列Set裡面(元素可重複)是否有子集合的和 = Sum
注意sum = 0 時答案為 True

解法說明:
bits是一個bit_vector,
其中從右往左數第i個位數,代表目前為止的Set的元素是否子集和= Sum
譬如說 Set = [2,2,3,5]
一開始bits = 1,
更新一輪之後就變成 1 | 101 = 101(二進位來看),
再更新一輪之後變成 10100 | 101 = 10101,
解讀為[2,2]可以湊出子集和 = 0, 2, 4

使用STL bitset便可以避免int或long long會溢位的問題
*/
bool isSubsetSum(vector<int> &Set, int Sum)
{
    bitset<1100> bits(1); //初始化bits = 1(bitset<>裡的數表示最多幾位數)
    for (int num : Set)
    {
        bits |= bits << num;
    }
    return bits[Sum]; //檢查從右往左數的第Sum位是不是1
}


int main()
{
    vector<int> arr = {2,2,3,5};
    int target = 9; //測試arr裡面是否有子集和 = target
    cout << (isSubsetSum(arr, target)?"YES":"NO") << endl;
}

參考資料

  1. cplusplus.com- bitset
  2. bitset 整理

尚未有邦友留言

立即登入留言