天天看點
傳回

bitset的使用

bitset 類簡化了位集的處理，有些程式要使用二進制位的有序集來儲存一組項或條件的标志位，可以考慮使用bitset。

需要的檔案：

#include <bitset>

Using std::bitset

l         bitset 對象的定義和初始化

定義bitset時，要明确bitset有多少位：

bitset<32> bitvec     // 32位二進制，初始化為0，0~31

用unsigned 值初始化bitset 對象：

當用unsigned 值初始化bitset 對象時，該值将轉化為二進制的位模式。如果bitset類型長度大于 unsigned 值的二進制位數，則其餘的高階位将置為0；如果bitset 類型長度小于unsigned 值的二進制位數，則隻使用unsigned值中的低階位，超過bitset類型長度的高階位将被丢棄。

bitset<16> bit ( 0xFFFF )              // 0~15位都置1

bitset<32> bit ( 0xFFFF )              // 0~15位置1，16~31位置0

用 string 對象初始化bitset對象

string strval ( “1100” )

bitset<32> bit ( strval )

注意：從string對象讀入位集的順序是從右向左。即反向轉化：string對象最右邊的字元用來初始化bitset對象的低階位（即下标為0的位）。

bit 的位模式中第2和3位置為1，其餘位置都為0。如果string對象的字元個數小于bitset類型的長度，則高階位将置為0。

       不一定要把整個string對象都作為bitset的初始值，可以隻用某個子串作為初始值：

string str ( “111111111100000000011011” )

bitset<32> bit ( str , 5 , 4 )

構造函數

bitset<n> b;

 b有n位，每位都為0.參數n可以為一個表達式.

如bitset<5> b0;則"b0"為"00000";

bitset<n> b(unsigned long u);

 b有n位,并用u指派;如果u超過n位,則頂端被截除

如:bitset<5>b0(5);則"b0"為"00101";

bitset<n> b(string s);

 b是string對象s中含有的位串的副本

string bitval ( "10011" );

bitset<5> b0 ( bitval);

則"b0"為"10011";

bitset<n> b(s, pos);

 b是s中從位置pos開始位的副本,前面的多餘位自動填充0;

string bitval ("01011010");

bitset<10> b0 ( bitval, 3 );

則"b0" 為 "0000011010";

bitset<n> b(s, pos, num);

 b是s中從位置pos開始的num個位的副本,如果num<n,則前面的空位自動填充0;

string bitval ("11110011011");

bitset<6> b0 ( bitval, 3, 6 );

則"b0" 為 "100110";

bitset如何初始化、如何轉化為double類型的小數、如何進行交叉（可以嘗試用string作為中間量，因為bitset可以用string初始化的，但是這樣的構造和傳遞會消耗很多的時間——我讨厭這種不必要的消耗！）

假如說我希望計算的精度足夠高，将bitset取為64位，那麼什麼類型的數才能輸出？如果不需要輸出，那麼在取精度的時候，如何将一個64位的bitset轉化為double類型的小數？（可能需要自己程式設計實作了）

如何将一個double類型的數字轉化為bitset，也就是二進制編碼，友善我們做交叉、變異。

(說得簡單點，以上兩個就是解碼和編碼的問題)——文字很亂，整理一下！

如何實作兩個bitset的合并？小數部分、整數部分，如果能夠合并，那寫程式又會友善多了！比如：兩個32位的bitset合并成一個64位的bitset！（是不是又要利用string進行轉換呢？如何轉換？）

代碼說明：将bitset的某一位置為1

bitset<32> bits;
for (int i =0;i<5;i++)
bits.set(i);//i為需要被置為1的位數
cout<<bits<<endl;

bitset的函數用法

頭檔案：#include<bitset>

常用的成員函數：

b.any() b中是否存在置為1的二進制位？

b.none() b中不存在置為1的二進制位嗎？

b.count() b中置為1的二進制位的個數

b.size() b中二進制位數的個數

b[pos] 通路b中在pos處二進制位

b.test(pos) b中在pos處的二進制位置為1麼？

b.set() 把b中所有二進制位都置為1

b.set(pos) 把b中在pos處的二進制位置為1

b.reset( ) 把b中所有二進制位都置為0

b.reset( pos ) 把b中在pos處的二進制位置置為0

b.flip( ) 把b中所有二進制位逐位取反

b.flip( pos ) 把b中在pos處的二進制位取反

b.to_ulong( ) 把b中同樣的二進制位傳回一個unsigned

os << b 把b中的位集輸出到os流

注意事項

你看得出來下面的代碼為什麼輸出7和9嗎？

#include<iostream> 
#include<bitset> 
using namespace std; 
void main() 
{ 
    bitset<4> bit(1111); 
    cout<<bit.to_ulong()<<endl; 
    bitset<4> ait(1001); 
    cout<<ait.to_ulong()<<endl; 
}

原因很簡單：bitset調用的構造函數，1111為十進制，換成二進制為0x10001010111，最後4位為0111，輸出就是7；如果你想規定bitset裡面的每一位，那麼最好用string類型：bitset<4> bits("1111"); 這樣輸出就是15了

字元串合并以及輸出的問題，要搞定，還真麻煩......為了偷懶，在多個類型之間轉來轉去的......不過寫起來真的很簡單，哈哈！有現成的方法就用呗！不管效率了......

#include <iostream>
#include <string>
#include <iostream>
#include "afxwin.h"
using namespace std;
int main(){
    CString s1 = "abcd";
    CString s2 = "xyzw";
    CString s3 = s1+s2;
    cout<<(LPCTSTR)s1<<endl<<(LPCTSTR)s3<<endl;
    string s4 = (LPCTSTR)s3;
    cout<<s4<<endl;
    return 0;
}

下面是2個bitset合并的代碼例子

#include <bitset>
#include <iostream>
#include <string>
#include <iostream>
#include "afxwin.h"
using namespace std;
int main(){
    bitset<4> bits1("1111");
    bitset<4> bits2("0000");
    int i = bits1.size()+bits2.size();
//  bitset<i> bits3;   //不能使用動态參數作為模闆參數，能不能想辦法解決？
    bitset<128> bits3;
    int j=0;
    for (j=0;j<bits1.size();j++)
    {
        if (bits1[j]==1)
            bits3.set(j);
    }
    for (j=bits1.size();j<bits1.size()+bits2.size();j++)
    {
        if (bits2[j-bits1.size()]==1)
        {
            bits3.set(j);
        }
    }
    cout<<bits3<<endl<<bits3.to_ulong()<<endl;
    return 0;
}
           
<span style="font-family: Arial; font-size: 13.63636302947998px;">bitset能夠達到的最大長度</span>
           
#include <bitset>
#include <vector>
#include <iostream>
#include <string>
#include <iostream>
#include "afxwin.h"
using namespace std;
int main(){
    bitset<1000000> bits;// 一百萬差不多到頂了，如果再加一個0，到達一千萬，就會崩潰。為什麼？
    cout<<bits[0];
    return 0;
}

想使用動态的bitset嗎？

dynamic_bitset可以滿足我的需求！這實在太棒了！boost萬歲！ps：不知道會造成多大的效率影響？和固定長度的代碼比較起來，雖然固定一點、浪費一點空間，但是如果更快的話，也是值得了。另外：dynamic_bitset不能在vc6下通過編譯......

bit_vector

這個“位向量組”在SGI STL中實作，VC6中沒有。從名字和功能介紹上就可以看出來：這是一個可以像操作vector一樣友善的容器，可以push_back每一位。效率有待實驗，我是在一本書上偶然看到這個庫的。

然而，令我失望的是：在ubuntu和VC6下，都沒有bit_vector，必須安裝SGI 版本的stl才行呢。

結論：對于這方面，看樣子還是湊合着用吧！（實作簡單的bitset，空間方面嘛，稍微浪費一點也就是了。）

參考文獻：

http://www.programbbs.com/doc/3012.htm 可以借鑒這篇文章中，傳統的C方式操作位。不過在本文中，不是重點（C的方式很醜陋呢......）

http://dev.csdn.net/article/70/70814.shtm位向量的應用

來個笑話：世界上有10種人，一種人懂二進制，一種不懂。

二進制位運算就5種：與、或、異或、左移、右移。（還有一個位求反~）

bitset的使用

左移：m<<n，表示把m左移n位，左邊丢棄，右邊補0；

右移：m>>n，表示把m右移n位，這裡要稍微注意一下。如果是無符号數，則右邊丢棄，左邊補0；若是有符号數，則補位根據符号來定，正補0，負補1。

如：00001010 >> 2 =00000010                             

        10001010 >> 2 =11100010

題目描述：

請實作一個函數，輸入一個整數，輸出該數二進制中1的個數。例如把9表示成二進制為1001，有2個1，則輸入9，函數輸出2。

  1. #include <stdio.h>  
  2. //1.處理無符号數  
  3. int CountBit(int n)  
  4. {  
  5.     int count = 0;  
  6.     while (n)  
  7.     {  
  8.         if (n & 1)  
  9.             count++;  
  10.         n = n >> 1;  
  11.     }  
  12.     return count;  
  13. }  
  14. //2.處理有符号數，不過循環次數需要控制，可參考注釋部分  
  15. int CountBit2(int n)  
  16. {  
  17.     int count = 0;  
  18.     unsigned int flag = 1;  
  19.     while (flag)  
  20.     {  
  21.         if (n & flag)  
  22.             count++;  
  23.         flag = flag << 1;  
  24.         }  
  25.     return count;  
  26. }  
  27. //3.減去1後與原資料與運算，每次減少一個1。  
  28. int CountBit3(int n)  
  29. {  
  30.     int count = 0;  
  31.     while (n)  
  32.     {  
  33.         //count++;  
  34.         n = (n - 1) & n;  
  35.         count++;  
  36.     }  
  37.     return count;  
  38. }  
  39. int main(int argc, char *argv[])  
  40. {  
  41. //  printf("%d\n", CountBit(3));  
  42. //  printf("%d\n", CountBit2(7));  
  43.     printf("%d\n", CountBit3(7));  
  44.     return 0;  
  45. }  

bitset

C++語言的一個類庫，用來友善地管理一系列的bit位而不用自己來寫代碼。

初始化：bitset<N> va(M);

N表示初始化位數，M表示初始值。如：bitset<10> a(5),列印出來會得到：0000000101

bitset操作例子：

1）将某位設定為0或1

bitset<10> a(5);

a[0] = 0 ;  // cout結果為：0000000100（将第0位設為0）

a |= 1UL << 2;   //cout結果為：0000000000  （将第2位設為0）

2）函數set（）:将某位設定為1

a.set()   // 将全部位數都設定為1，cout結果為：1111111111；

a.set(3)   //将第三位設為1

使用下标：a[2].set()   //将第2位設為1；

3）判斷是否為1

any（）：至少一位為1，傳回true；全為0，傳回false；

none（）；全為0，傳回true；否則傳回false；

4）函數count（）：傳回1的個數

如a = 0000000101

a.count() //傳回2

5）函數test（）：測試是否為1

a = 0000000101

a.test(2);   //測試第2位是否為1；

6）set()、reset（）

不加參數，set（）表示全部設定為1；reset（）表示全部設定為0；

加參數即使用下标，具體設定某一位。

7）函數flip（）：取反（即将0->1,1->0)

不加參數：a.flip()，全部取反；

加參數即使用下标，具體對某一位取反。

***************華麗的分割線******************

剛剛碰到一個為運算，需要用到位或“|”來将某位指派為1，結果發現位或運算了解錯了。汗，在此将c中位運算做個總結，如下： 

位運算是指按二進制進行的運算。在系統軟體中，常常需要處理二進制位的問題。C語言提供了6個位操作

運算符。這些運算符隻能用于整型操作數，即隻能用于帶符号或無符号的char,short,int與long類型。

C語言提供的位運算符清單：

運算符 含義 描述

& 按位與 如果兩個相應的二進制位都為1，則該位的結果值為1，否則為0

| 按位或 兩個相應的二進制位中隻要有一個為1，該位的結果值為1

^ 按位異或 若參加運算的兩個二進制位值相同則為0，否則為1

~ 取反 ~是一進制運算符，用來對一個二進制數按位取反，即将0變1，将1變0

<< 左移 用來将一個數的各二進制位全部左移N位，右補0

>> 右移 将一個數的各二進制位右移N位，移到右端的低位被舍棄，對于無符号數，高位補0

1、“按位與”運算符（&）

    按位與是指：參加運算的兩個資料，按二進制位進行“與”運算。如果兩個相應的二進制位都為１，

則該位的結果值為1；否則為0。這裡的1可以了解為邏輯中的true,0可以了解為邏輯中的false。按位與其

實與邏輯上“與”的運算規則一緻。邏輯上的“與”，要求運算數全真，結果才為真。若，

A=true,B=true,則A∩B=true 例如：3&5 3的二進制編碼是11(2)。（為了區分十進制和其他進制，本文規

定，凡是非十進制的資料均在資料後面加上括号，括号中注明其進制，二進制則标記為2）記憶體儲存資料

的基本機關是位元組（Byte），一個位元組由8個位（bit)所組成。位是用以描述電腦資料量的最小機關。二

進制系統中，每個0或1就是一個位。将11（2）補足成一個位元組，則是00000011（2）。5的二進制編碼是

101（2），将其補足成一個位元組，則是00000101（2）

按位與運算：

 00000011(2)

&00000101(2)

 00000001(2)

由此可知3&5=1

c語言代碼：

#include <stdio.h>

main()

{

 int a=3;

 int b = 5;

 printf("%d",a&b);

}

按位與的用途：

（1）清零

若想對一個存儲單元清零，即使其全部二進制位為0，隻要找一個二進制數，其中各個位符合一下條件：

原來的數中為1的位，新數中相應位為0。然後使二者進行&運算，即可達到清零目的。

例：原數為43，即00101011（2），另找一個數，設它為148，即10010100（2），将兩者按位與運算：

 00101011（2）

&10010100（2）

 00000000（2）

c語言源代碼：

#include <stdio.h>

main()

{

 int a=43;

 int b = 148;

 printf("%d",a&b);

}

（2）取一個數中某些指定位

若有一個整數a(2byte),想要取其中的低位元組，隻需要将a與8個1按位與即可。

a 00101100 10101100

b 00000000 11111111

c 00000000 10101100

（3）保留指定位

與一個數進行“按位與”運算，此數在該位取1.

例如：有一數84，即01010100（2），想把其中從左邊算起的第3，4，5，7，8位保留下來，運算如下：

 01010100(2)

&00111011(2)

 00010000(2)

即：a=84,b=59

    c=a&b=16

c語言源代碼：

#include <stdio.h>

main()

{

 int a=84;

 int b = 59;

 printf("%d",a&b);

}

2、“按位或”運算符（|）

兩個相應的二進制位中隻要有一個為1，該位的結果值為1。借用邏輯學中或運算的話來說就是，一真為真。

例如：60（8）|17（8）,将八進制60與八進制17進行按位或運算。

 00110000

|00001111

 00111111 

c語言源代碼：

#include <stdio.h>

main()

{

 int a=060;

 int b = 017;

 printf("%d",a|b);

}

應用：按位或運算常用來對一個資料的某些位定值為1。例如：如果想使一個數a的低4位改為1，則隻需要

将a與17（8）進行按位或運算即可。

3、“異或”運算符（^）

他的規則是：若參加運算的兩個二進制位值相同則為0，否則為1

即0∧0=0，0∧1=1，1∧0=1， 1∧1=0

    例：   00111001

        ∧ 00101010

           00010011 

c語言源代碼：

#include <stdio.h>

main()

{

 int a=071;

 int b = 052;

 printf("%d",a^b);

}

應用：

（1）使特定位翻轉

設有數01111010（2），想使其低4位翻轉，即1變0，0變1.可以将其與00001111（2）進行“異或”運算，

即：

 01111010

^00001111

 01110101

運算結果的低４位正好是原數低４位的翻轉。可見，要使哪幾位翻轉就将與其進行∧運算的該幾位置為１

即可。

(２)與0相“異或”，保留原值

例如：012^00=012

        00001010

       ^00000000

        00001010

因為原數中的1與0進行異或運算得1，0^0得0，故保留原數。

(３) 交換兩個值，不用臨時變量

例如：ａ＝３，即11（2）；ｂ＝４，即100（2）。

想将ａ和ｂ的值互換，可以用以下指派語句實作：

    ａ＝a∧b;

    ｂ＝b∧a;

    ａ＝a∧b;

ａ＝011(2)

    （∧）ｂ＝100(2)

ａ＝111(2)（a∧b的結果，a已變成７）

    （∧）ｂ＝100(2)

ｂ＝011(2)（b∧a的結果，b已變成３）

    （∧）ａ＝111(2)

ａ＝100（2）（a∧b的結果，a已變成４）

等效于以下兩步：

    ① 執行前兩個指派語句：“ａ＝ａ∧ｂ；”和“ｂ＝ｂ∧ａ；”相當于b=b∧(a∧b)。

    ② 再執行第三個指派語句： ａ＝ａ∧ｂ。由于a的值等于（ａ∧ｂ），b的值等于（ｂ∧ａ∧ｂ），

是以，相當于a=ａ∧ｂ∧ｂ∧ａ∧ｂ，即a的值等于ａ∧ａ∧ｂ∧ｂ∧ｂ，等于ｂ。

c語言源代碼：

#include <stdio.h>

main()

{

 int a=3;

 int b = 4;

 a=a^b;

 b=b^a;

 a=a^b;

 printf("a=%d b=%d",a,b);

}

4、“取反”運算符（~）

他是一進制運算符，用于求整數的二進制反碼，即分别将操作數各二進制位上的1變為0，0變為1。

例如：~77(8)

源代碼：

#include <stdio.h>

main()

{

 int a=077;

 printf("%d",~a);

}

5、左移運算符（<<）

左移運算符是用來将一個數的各二進制位左移若幹位，移動的位數由右操作數指定（右操作數必須是非負

值），其右邊空出的位用0填補，高位左移溢出則舍棄該高位。

例如：将a的二進制數左移2位，右邊空出的位補0，左邊溢出的位舍棄。若a=15,即00001111（2），左移2

位得00111100（2）。

源代碼：

#include <stdio.h>

main()

{

 int a=15;

 printf("%d",a<<2);

}

左移1位相當于該數乘以2，左移2位相當于該數乘以2*2＝4,15＜＜2=60，即乘了４。但此結論隻适用于該

數左移時被溢出舍棄的高位中不包含1的情況。

    假設以一個位元組（８位）存一個整數，若ａ為無符号整型變量，則ａ＝64時，左移一位時溢出的是0

，而左移2位時，溢出的高位中包含1。

6、右移運算符（>>）

右移運算符是用來将一個數的各二進制位右移若幹位，移動的位數由右操作數指定（右操作數必須是非負

值），移到右端的低位被舍棄，對于無符号數，高位補0。對于有符号數，某些機器将對左邊空出的部分

用符号位填補（即“算術移位”），而另一些機器則對左邊空出的部分用0填補（即“邏輯移位”）。注

意：對無符号數,右移時左邊高位移入0；對于有符号的值,如果原來符号位為0(該數為正),則左邊也是移

入0。如果符号位原來為1(即負數),則左邊移入0還是1,要取決于所用的計算機系統。有的系統移入0,有的

系統移入1。移入0的稱為“邏輯移位”,即簡單移位；移入1的稱為“算術移位”。 

例： a的值是八進制數113755： 

   a:1001011111101101 （用二進制形式表示）

   a>>1: 0100101111110110 (邏輯右移時)

   a>>1: 1100101111110110 (算術右移時)

   在有些系統中,a>>1得八進制數045766,而在另一些系統上可能得到的是145766。Turbo C和其他一些C

編譯采用的是算術右移,即對有符号數右移時,如果符号位原來為1，左面移入高位的是1。

源代碼：

#include <stdio.h>

main()

{

 int a=0113755;

 printf("%d",a>>1);

}

7、位運算指派運算符

位運算符與指派運算符可以組成複合指派運算符。

   例如: &=, |=, >>=, <<=, ∧=

   例：  a & = b相當于 a = a & b

         a << =2相當于a = a << 2

雜談 STL bitset
上一篇: Redis 資料結構-Bitmap 和 HyperLogLogs相關文章文章将從以下方面介紹前言Redis 操作 BitmapBitmap 原理HyperLogLogHyperLogLog 原理
下一篇: java redis實作bitmap簽到功能場景需求設計思路示例代碼運作結果

繼續閱讀