C++ bitset——高端壓位卡常題必備STL

bitset儲存二進制數位，和bool數組差不多，不過有空間優化，bitset中一個元素隻占1bit，相當于一個char元素所占空間的八分之一。

bitset中的每個元素都像數組一樣單獨通路，下标從最右側以0開始

使用bitset需要像數組一樣提前确定大小

定義一個bitest

• 定義一個已知長度的全為0的bitset，n必須是常量表達式，例如const或者define定義過的的

  conest int n = 100;
  #define n 100
  bitset<n>b;
             

• 将一個十進制數x轉換成二進制存在n位的bitset中，n小于等于unsigned long的最大值，如果x轉換成2進制的長度len小于n，則高階位補0；如果len大于n，則隻保留低階位的前n位，比如100轉換成二進制是1100100，如果bitset隻定義了5位，則bitset為00100，如果bitset定義了10位，則bitset為0001100100

  int n;
  cin>>n;
  bitset<10>b(n);
             

• 将01字元串轉換成bitset，注意！必須是01串，不然會re，有三個參數(s, pos, len)，s即所需轉換的字元串，pos為s的開始位置，len需要轉換的長度，通常來說後兩個省略的時候就預設是從頭開始。如果s的長度大于n，則取s的前n位，如果s的長度小于n，則給高位補0，例如s = “111000”，n為5時，bitest為11100，n為8時，bitset為00111000

  string s;
  cin>>s;
  bitset<10>b(s);
  
  string s;
  int pos, len;
  cin>>s;
  cin>>pos>>len;
  bitset<10>b(s, pos, len);
             

bitset的函數們

再次重申一遍，因為bitset是儲存的二進制，是以下标是從最右側以0開始，往左依次增大

• b.set() 将b的所有位都置1
• b.set(pos) 将b的第pos+1位置置1
• b.reset() 将b的所有位都置0
• b.reset(pos) 将b的第pos+1位置置0
• b.flip() 将b全部位置都取反
• b.flip(pos) 将b的第pos + 1位取反
• b.count() 傳回1的個數
• b.size() 傳回b的大小
• b.any() 傳回是否有1
• b.to_ulong() 傳回它轉換為unsigned long的結果
• b.to_ullong() 傳回它轉換成unsigned long long的結果
• b.to_string() 傳回它轉換成string的結果

bitset的位運算們

bitset的位運算和普通的整數一樣，可以&、|、^、<<、>>、~

bitset<10>b("1110001100");
bitset<10>c;
b ^= 7;
b &= 10;
b |= 3;
b >>= 2;
b <<= 5;
c = ~b;