17.2. The bitset Type
In § 4.8 (p. 152) we covered the built-in operators that treat an integral operand as a collection of bits. The standard library defines the bitset class to make it easier to use bit operations and possible to deal with collections of bits that are larger than the longest integral type. The bitset class is defined in the bitset header.
17.2.1. Defining and Initializing bitsets
Table 17.2 (overleaf) lists the constructors for bitset. The bitset class is a class template that, like the array class, has a fixed size (§ 9.2.4, p. 336). When we define a bitset, we say how many bits the bitset will contain:
bitset<32> bitvec(1U); // 32 bits; low-order bit is 1, remaining bits are 0Table 17.2. Ways to Initialize a bitset
| Code | Description |
|---|---|
bitset<n> b; | b has n bits; each bit is 0. This constructor is a constexpr (§ 7.5.6, p. 299). |
bitset<n> b(u); | b is a copy of the n low-order bits of unsigned long long value u. If n is greater than the size of an unsigned long long, the high-order bits beyond those in the unsigned long long are set to zero. This constructor is a constexpr (§ 7.5.6, p. 299). |
bitset<n> b(s, pos, m, zero, one); | b is a copy of the m characters from the string s starting at position pos. s may contain only the characters zero and one; if s contains any other character, throws invalid_argument. The characters are stored in b as zero and one, respectively. pos defaults to 0, m defaults to string::npos, zero defaults to '0', and one defaults to '1'. |
bitset<n> b(cp, pos, m, zero, one); | Same as the previous constructor, but copies from the character array to which cp points. If m is not supplied, then cp must point to a C-style string. If m is supplied, there must be at least m characters that are zero or one starting at cp. |
INFO
- The constructors that take a
stringor character pointer areexplicit(§ 7.5.4, p. 296) - The ability to specify alternate characters for 0 and 1 was added in the new standard.
The size must be a constant expression (§ 2.4.4, p. 65). This statement defines bitvec as a bitset that holds 32 bits. Just as with the elements of a vector, the bits in a bitset are not named. Instead, we refer to them positionally. The bits are numbered starting at 0. Thus, bitvec has bits numbered 0 through 31. The bits starting at 0 are referred to as the low-order bits, and those ending at 31 are referred to as high-order bits.
Initializing a bitset from an unsigned Value
When we use an integral value as an initializer for a bitset, that value is converted to unsigned long long and is treated as a bit pattern. The bits in the bitset are a copy of that pattern. If the size of the bitset is greater than the number of bits in an unsigned long long, then the remaining high-order bits are set to zero. If the size of the bitset is less than that number of bits, then only the low-order bits from the given value are used; the high-order bits beyond the size of the bitset object are discarded:
// bitvec1 is smaller than the initializer; high-order bits from the initializer are discarded
bitset<13> bitvec1 (0xbeef); // bits are 1111011101111
// bitvec2 is larger than the initializer; high-order bits in bitvec2 are set to zero
bitset<20> bitvec2(0xbeef); // bits are 00001011111011101111
// on machines with 64-bit long long 0ULL is 64 bits of 0, so ~0ULL is 64 ones
bitset<128> bitvec3(~0ULL); // bits 0 ... 63 are one; 63 ... 127 are zeroInitializing a bitset from a string
We can initialize a bitset from either a string or a pointer to an element in a character array. In either case, the characters represent the bit pattern directly. As usual, when we use strings to represent numbers, the characters with the lowest indices in the string correspond to the high-order bits, and vice versa:
bitset<32> bitvec4("1100"); // bits 2 and 3 are 1, all others are 0If the string contains fewer characters than the size of the bitset, the high-order bits are set to zero.
INFO
The indexing conventions of strings and bitsets are inversely related: The character in the string with the highest subscript (the rightmost character) is used to initialize the low-order bit in the bitset (the bit with subscript 0). When you initialize a bitset from a string, it is essential to remember this difference.
We need not use the entire string as the initial value for the bitset. Instead, we can use a substring as the initializer:
string str("1111111000000011001101");
bitset<32> bitvec5(str, 5, 4); // four bits starting at str[5], 1100
bitset<32> bitvec6(str, str.size()-4); // use last four charactersHere bitvec5 is initialized by the substring in str starting at str[5] and continuing for four positions. As usual, the right-most character of the substring represents the lowest-order bit. Thus, bitvec5 is initialized with bit positions 3 through 0 set to 1100 and the remaining bits set to 0. The initializer for bitvec6 passes a string and a starting point, so bitvec6 is initialized from the characters in str starting four from the end of str. The remainder of the bits in bitvec6 are initialized to zero. We can view these initializations as
INFO
Exercises Section 17.2.1
Exercise 17.9: Explain the bit pattern each of the following bitset objects contains:
(a)bitset<64> bitvec(32);
(b)bitset<32> bv(1010101);
(c)string bstr; cin >> bstr; bitset<8>bv(bstr);
17.2.2. Operations on bitsets
The bitset operations (Table 17.3 (overleaf)) define various ways to test or set one or more bits. The bitset class also supports the bitwise operators that we covered in § 4.8 (p. 152). The operators have the same meaning when applied to bitset objects as the built-in operators have when applied to unsigned operands.
| Code | Description |
|---|---|
b.any() | Is any bit in b on? |
b.all() | Are all the bits in b on? |
b.none() | Are no bits in b on? |
b.count() | Number of bits in b that are on. |
b.size() | A constexpr function (§ 2.4.4, p. 65) that returns the number of bits in b. |
b.test(pos) | Returns true if bit at position pos is on, false otherwise. |
b.set(pos, v) b.set() | Sets the bit at position pos to the bool value v. v defaults to true. If no arguments, turns on all the bits in b. |
b.reset(pos) b.reset() | Turns off the bit at position pos or turns off all the bits in b. |
b.flip(pos) b.flip() | Changes the state of the bit at position pos or of every bit in b. |
b[pos] | Gives access to the bit in b at position pos; if b is const, then b[pos] returns a bool value true if the bit is on, false otherwise. |
b.to_ulong() b.to_ullong() | Returns an unsigned long or an unsigned long long with the same bits as in b. Throws overflow_error if the bit pattern in b won't fit in the indicated result type. |
b.to_string(zero, one) | Returns a string representing the bit pattern in b. zero and one default to '0' and '1' and are used to represent the bits 0 and 1 in b. |
os << b | Prints the bits in b as the characters 1 or 0 to the stream os. |
is >> b | Reads characters from is into b. Reading stops when the next character is not a 1 or 0 or when b.size() bits have been read. |
Several operations—count, size, all, any, and none—take no arguments and return information about the state of the entire bitset. Others—set, reset, and flip—change the state of the bitset. The members that change the bitset are overloaded. In each case, the version that takes no arguments applies the given operation to the entire set; the versions that take a position apply the operation to the given bit:
bitset<32> bitvec(1U); // 32 bits; low-order bit is 1, remaining bits are 0
bool is_set = bitvec.any(); // true, one bit is set
bool is_not_set = bitvec.none(); // false, one bit is set
bool all_set = bitvec.all(); // false, only one bit is set
size_t onBits = bitvec.count(); // returns 1
size_t sz = bitvec.size(); // returns 32
bitvec.flip(); // reverses the value of all the bits in bitvec
bitvec.reset(); // sets all the bits to 0
bitvec.set(); // sets all the bits to 1The any operation returns true if one or more bits of the bitset object are turned on—that is, are equal to 1. Conversely, none returns true if all the bits are zero. The new standard introduced the all operation, which returns true if all the bits are on. The count and size operations return a size_t (§ 3.5.2, p. 116) equal to the number of bits that are set, or the total number of bits in the object, respectively. The size function is a constexpr and so can be used where a constant expression is required (§ 2.4.4, p. 65).
The flip, set, reset, and test members let us read or write the bit at a given position:
bitvec.flip(0); // reverses the value of the first bit
bitvec.set(bitvec.size() - 1); // turns on the last bit
bitvec.set(0, 0); // turns off the first bit
bitvec.reset(i); // turns off the ith bit
bitvec.test(0); // returns false because the first bit is offThe subscript operator is overloaded on const. The const version returns a bool value true if the bit at the given index is on, false otherwise. The nonconst version returns a special type defined by bitset that lets us manipulate the bit value at the given index position:
bitvec[0] = 0; // turn off the bit at position 0
bitvec[31] = bitvec[0]; // set the last bit to the same value as the first bit
bitvec[0].flip(); // flip the value of the bit at position 0
~bitvec[0]; // equivalent operation; flips the bit at position 0
bool b = bitvec[0]; // convert the value of bitvec[0] to boolRetrieving the Value of a bitset
The to_ulong and to_ullong operations return a value that holds the same bit pattern as the bitset object. We can use these operations only if the size of the bitset is less than or equal to the corresponding size, unsigned long for to_ulong and unsigned long long for to_ullong:
unsigned long ulong = bitvec3.to_ulong();
cout << "ulong = " << ulong << endl;INFO
These operations throw an overflow_error exception (§ 5.6, p. 193) if the value in the bitset does not fit in the specified type.
bitset IO Operators
The input operator reads characters from the input stream into a temporary object of type string. It reads until it has read as many characters as the size of the corresponding bitset, or it encounters a character other than 1 or 0, or it encounters end-of-file or an input error. The bitset is then initialized from that temporary string (§ 17.2.1, p. 724). If fewer characters are read than the size of the bitset, the high-order bits are, as usual, set to 0.
The output operator prints the bit pattern in a bitset object:
bitset<16> bits;
cin >> bits; // read up to 16 1 or 0 characters from cin
cout << "bits: " << bits << endl; // print what we just readUsing bitsets
To illustrate using bitsets, we’ll reimplement the grading code from § 4.8 (p. 154) that used an unsigned long to represent the pass/fail quiz results for 30 students:
bool status;
// version using bitwise operators
unsigned long quizA = 0; // this value is used as a collection of bits
quizA |= 1UL << 27; // indicate student number 27 passed
status = quizA & (1UL << 27); // check how student number 27 did
quizA &= ~(1UL << 27); // student number 27 failed
// equivalent actions using the bitset library
bitset<30> quizB; // allocate one bit per student; all bits initialized to 0
quizB.set(27); // indicate student number 27 passed
status = quizB[27]; // check how student number 27 did
quizB.reset(27); // student number 27 failedINFO
Exercises Section 17.2.2
Exercise 17.10: Using the sequence 1, 2, 3, 5, 8, 13, 21, initialize a bitset that has a 1 bit in each position corresponding to a number in this sequence. Default initialize another bitset and write a small program to turn on each of the appropriate bits.
Exercise 17.11: Define a data structure that contains an integral object to track responses to a true/false quiz containing 10 questions. What changes, if any, would you need to make in your data structure if the quiz had 100 questions?
Exercise 17.12: Using the data structure from the previous question, write a function that takes a question number and a value to indicate a true/false answer and updates the quiz results accordingly.
Exercise 17.13: Write an integral object that contains the correct answers for the true/false quiz. Use it to generate grades on the quiz for the data structure from the previous two exercises.