c++ bitset使用

A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1,true or false, ...).

bitset是一个特殊的容器专门用来存储bit

The class is very similar to a regular array, but optimizing for space allocation: each element occupies only one bit (which is eight times less than the smallest elemental type in C++: char).

Each element (each bit) can be accessed individually: for example, for a given bitset named mybitset, the expression mybitset[3] accesses its fourth bit, just like a regular array accesses its elements.

Because no such small elemental type exists in most C++ environments, the individual elements are accessed as special references which mimic模拟 bool elements:

class bitset::reference {
  friend class bitset;
  reference();                                 // no public constructor
public:
  ~reference();
  operator bool () const;                      // convert to bool
  reference& operator= ( bool x );             // assign from bool
  reference& operator= ( const reference& x ); // assign from bit
  reference& flip();                           // flip bit value
  bool operator~() const;                      // return inverse value
}

Apart from 除了overriding several operators and to provide direct access to the bits, bitsets have the feature of being able to be constructed from and converted to both integer values and binary strings (see constructor,bitset::to_ulong and bitset::to_string). They can also be directly inserted and extracted from streams in binary format.

Bitsets have a fixed size. For a similar container class that also optimizes for space allocation and allows for dynamic resizing, see the bool specialization of vector (vector<bool>).

In their implementation in the C++ Standard Template Library, bitsets take a single template parameter:

template < size_t N > class bitset;

Where the template parameter has the following meaning:

N: Number of bits to contain (size_t is an integral type).

构造函数使用：

int main ()
{
  bitset<10> first;                   // empty bitset

  bitset<10> second (120ul);          // initialize from unsigned long

  bitset<10> third (string("01011")); // initialize from string

  return 0;
}

bitset的定义和初始化

表3-6列出了bitset的构造函数。类似于vector，bitset类是一种类模板；而与vector不一样的是bitset类型对象的区别仅在其长度而不在其类型。在定义bitset时，要明确bitset含有多少位，须在尖括号内给出它的长度值：

bitset<32> bitvec; //32位，全为0。

给出的长度值必须是常量表达式（2.7节）。正如这里给出的，长度值必须定义为整型字面值常量或是已用常量值初始化的整数类型的const对象。

这条语句把bitvec定义为含有32个位的bitset对象。和vector的元素一样，bitset中的位是没有命名的，程序员只能按位置来访问它们。位集合的位置编号从0开始，因此，bitvec的位序是从0到31。以0位开始的位串是低阶位（low-order bit），以31位结束的位串是高阶位(high-order bit)。

表3-6 初始化bitset对象的方法

bitset<n> b;	b有n位，每位都为0
bitset<n> b(u);	b是unsigned long型u的一个副本
bitset<n> b(s);	b是string对象s中含有的位串的副本
bitset<n> b(s, pos, n);	b是s中从位置pos开始的n个位的副本

头文件：

#include <bitset> 没有.h

using std::bitset;

bitset<10> third(string("01011")); //从string对象读入位集的顺序是从右向左： 11010 00000
cout<<third; 输出结果是： 11010 00000 cout bitset是从高位到地位。

cout << third[2] << endl; 从地位开始的，输出0

cout<<thrid[0]<<endl; 输出1

1. 用unsigned值初始化bitset对象

当用unsigned long值作为bitset对象的初始值时，该值将转化为二进制的位模式。而bitset对象中的位集作为这种位模式的副本。如果bitset类型长度大于unsigned long值的二进制位数，则其余的高阶位置为0；如果bitet类型长度小于unsigned long值的二进制位数，则只使用unsigned值中的低阶位，超过bitet类型长度的高阶位将被丢弃。

在32位unsigned long的机器上，十六进制值0xffff表示为二进制位就是十六个1和十六个0（每个0xf可表示为1111）。可以用0xffff初始化bitset对象：

// bitvec1 is smaller than the initializer

bitset<16> bitvec1(0xffff);          // bits 0 ... 15 are set to 1

// bitvec2 same size as initializer

bitset<32> bitvec2(0xffff);          // bits 0 ... 15 are set to 1; 16 ... 31 are 0

// on a 32-bit machine, bits 0 to 31 initialized from 0xffff

bitset<128> bitvec3(0xffff);         // bits 32 through 127 initialized to zero

上面的三个例子中，0到15位都置为1。由于bitvec1位数少于unsigned long的位数，因此bitvec1的初始值的高阶位被丢弃。bitvec2和unsigned long长度相同，因此所有位正好放置了初始值。bitvec3长度大于32，31位以上的高阶位就被置为0。

2. 用string对象初始化bitset对象

当用string对象初始化bitset对象时，string对象直接表示为位模式。从string对象读入位集的顺序是从右向左：

string strval("1100");

bitset<32> bitvec4(strval);

bitvec4的位模式中第2和3的位置为1，其余位置都为0。如果string对象的字符个数小于bitset类型的长度，则高阶位将置为0。

string对象和bitset对象之间是反向转化的：string对象的最右边字符（即下标最大的那个字符）用来初始化bitset对象的低阶位（即下标为0的位）。当用string对象初始化bitset对象时，记住这一差别很重要。

不一定要把整个string对象都作为bitset对象的初始值。相反，可以只用某个子串作为初始值：

string str("1111111000000011001101");

bitset<32> bitvec5(str, 5, 4); // 4 bits starting at str[5], 1100

bitset<32> bitvec6(str, str.size() - 4);     // use last 4 characters

这里用str中从str[5]开始包含四个字符的子串来初始化bitvec5。照常，初始化bitset对象时总是从子串最右边结尾字符开始的，bitvec5的从0到3的二进制位置为1100，其他二进制位都置为0。如果省略第三个参数则意味着取从开始位置一直到string末尾的所有字符。本例中，取出str末尾的四位来对bitvec6的低四位进行初始化。bitvec6其余的位初始化为0。这些初始化过程的图示如下：

http://book.51cto.com/art/200809/88698.htm

构造函数
bitset<n> b;
b有n位，每位都为0.参数n可以为一个表达式.
如bitset<5> b0;则"b0"为"00000";
cout<<b0; 输出5个0

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 ( bitval4 );
则"b0"为"10011";

bitset<n> b(s, pos);
b是s中从位置pos开始位的副本,前面的多余位自动填充0;
string bitval ("01011010");
bitset<10> b0 ( bitval5, 3 );
则"b0" 为 "0000011010";

bitset<n> b(s, pos, num);
b是s中从位置pos开始的num个位的副本,如果num<n,则前面的空位自动填充0;
string bitval ("11110011011");
bitset<6> b0 ( bitval5, 3, 6 );
则"b0" 为 "100110";

os << b
把b中的位集输出到os流
os >>b
输入到b中,如"cin>>b",如果输入的不是0或1的字符,只取该字符前面的二进制位.
(如：

bitset<8> e;
cin>>e;
cout<<e<<endl;

输入11110000，输出11110000)

bool any( )
是否存在置为1的二进制位？和none()相反

bool none( )
是否不存在置为1的二进制位,即全部为0？和any()相反.

size_t count( )
二进制位为1的个数.

size_t size( )
二进制位的个数

flip()
把所有二进制位逐位取反

flip(size_t pos)
把在pos处的二进制位取反

bool operator[]( size_type _Pos )
获取在pos处的二进制位

set()
把所有二进制位都置为1

set(pos,bool val=true)
把在pos处的二进制位置为1。

pos:Order position of the bit whose value is modified.
Order positions are counted from the rightmost bit, which is order position 0.
If pos is equal or greater than the bitset size, an out_of_range exception is thrown.
size_t is an unsigned integral type.

注意pos，是从最右边开始数起。这一点千万有注意。

可以看到，set有2种原型，都返回当前的对象，demo：

// bitset::set
#include <iostream>       // std::cout
#include <bitset>         // std::bitset

int main ()
{
  std::bitset<4> foo;

  std::cout << foo.set() << '
';       // 1111
  std::cout << foo.set(2,0) << '
';    // 1011
  std::cout << foo.set(2) << '
';      // 1111

  return 0;
}

输出：

1111
1011
1111）

reset()
把所有二进制位都置为0

reset(pos)
把在pos处的二进制位置为0

test(size_t pos) （也是从右边开始）
在pos处的二进制位是否为1？

unsigned long to_ulong( )
用同样的二进制位返回一个unsigned long值
（

bitset<32> b(16);
cout<<b<<endl;
cout<<b.to_ulong()<<endl; 输出16

）

string to_string ()
返回对应的字符串.

详细请翻阅msdn.

http://www.cplusplus.com/reference/bitset/bitset/

Member functions

(constructor): Construct bitset (public member function )

applicable operators: Bitset operators (function )

Bit access

operator[]: Access bit (public member function )

count: Count bits set (public member function )

size: Return size (public member function )

test: Return bit value (public member function )

any: Test if any bit is set (public member function )

none: Test if no bit is set (public member function )

all: Test if all bits are set (public member function )

Bit operations

set: Set bits (public member function )

reset: Reset bits (public member function )

flip: Flip bits (public member function )

Bitset operations

to_string: Convert to string (public member function )

to_ulong: Convert to unsigned long integer (public member function )

to_ullong: Convert to unsigned long long (public member function )

Non-member function overloads

applicable operators: Bitset operators (function )

Non-member class specializations

hash<bitset>: Hash for bitset (class template specialization )

csdn上也有一篇写的很好,以下为链接
http://book.csdn.net/bookfiles/17/1001760.shtml

关于bitset最大size问题，我写了一个程序：

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

#define N 10000000
 
int main()
{
    bitset<N> b;
     
    cout<<b<<endl;
}

一运行就崩溃，F5调试时发现stack overflow。

原因：vc默认1M的栈空间，可以在工程-》设置-》链接栈分配保留当中修改，比如0x9000000就代表栈最大9M。

我们定义的局部变量b是分配在stack空间的。超过了1M大小，所以stack overflow，当然我们可以更改stack大小。有没有其他的办法呢？

解决办法1：把bitset<N> 放到全局变量或加上static。（原因不言自明）

解决办法2：new一个bitset。

关于bitset<N>和vector<bool>区别：http://blog.csdn.net/liushu1231/article/details/8844631