Class bitset

Class bitset makes it easy to create and manipulate bit sets, which are useful for representing a set of bit flags. bitsets are fixed in size at compile time. Class bitset is an alternate tool for bit manipulation, discussed in Chapter 22. The declaration

bitset< size > b;

---

creates bitset b, in which every bit is initially 0. The statement

b.set( bitNumber );

sets bit bitNumber of bitset b "on." The expression b.set() sets all bits in b "on."

The statement

b.reset( bitNumber );

sets bit bitNumber of bitset b "off." The expression b.reset() sets all bits in b "off." The statement

b.flip( bitNumber );

"flips" bit bitNumber of bitset b (e.g., if the bit is on, flip sets it off). The expression b.flip() flips all bits in b. The statement

b[ bitNumber ];

returns a reference to the bit bitNumber of bitset b. Similarly,

b.at( bitNumber );

performs range checking on bitNumber first. Then, if bitNumber is in range, at returns a reference to the bit. Otherwise, at throws an out_of_range exception. The statement

b.test( bitNumber );

performs range checking on bitNumber first. Then, if bitNumber is in range, test returns TRue if the bit is on, false if the bit is off. Otherwise, test throws an out_of_range exception. The expression

b.size()

returns the number of bits in bitset b. The expression

b.count()

returns the number of bits that are set in bitset b. The expression

b.any()

returns TRue if any bit is set in bitset b. The expression

b.none()

returns true if none of the bits is set in bitset b. The expressions

b == b1
b != b1

compare the two bitsets for equality and inequality, respectively.

Each of the bitwise assignment operators &=, |= and ^= can be used to combine bitsets. For example,

b &= b1;

performs a bit-by-bit logical AND between bitsets b and b1. The result is stored in b. Bitwise logical OR and bitwise logical XOR are performed by

---

b |= b1;
b ^= b2;

The expression

b >>= n;

shifts the bits in bitset b right by n positions. The expression

b <<= n;

shifts the bits in bitset b left by n positions. The expressions

b.to_string()
b.to_ulong()

convert bitset b to a string and an unsigned long, respectively.

Sieve of Eratosthenes with bitset

Figure 23.40 revisits the Sieve of Eratosthenes for finding prime numbers that we discussed in Exercise 7.29. A bitset is used instead of an array to implement the algorithm. The program displays all the prime numbers from 2 to 1023, then allows the user to enter a number to determine whether that number is prime.

Figure 23.40. Class bitset and the Sieve of Eratosthenes.

(This item is displayed on pages 1185 - 1187 in the print version)

 1 // Fig. 23.40: Fig23_40.cpp
 2 // Using a bitset to demonstrate the Sieve of Eratosthenes.
 3 #include 
 4 using std::cin;
 5 using std::cout;
 6 using std::endl;
 7
 8 #include 
 9 using std::setw;
10
11 #include 
12 using std::sqrt; // sqrt prototype
13
14 #include  // bitset class definition
15
16 int main()
17 {
18 const int SIZE = 1024;
19 int value;
20 std::bitset< SIZE > sieve; // create bitset of 1024 bits
21 sieve.flip(); // flip all bits in bitset sieve 
22 sieve.reset( 0 ); // reset first bit (number 0) 
23 sieve.reset( 1 ); // reset second bit (number 1) 
24
25 // perform Sieve of Eratosthenes
26 int finalBit = sqrt( static_cast< double > ( sieve.size() ) ) + 1;
27
28 // determine all prime numbers from 2 to 1024
29 for ( int i = 2; i < finalBit; i++ )
30 {
31 if ( sieve.test( i ) ) // bit i is on
32 {
33 for ( int j = 2 * i; j < SIZE; j += i )
34 sieve.reset( j ); // set bit j off
35 } // end if
36 } // end for
37
38 cout << "The prime numbers in the range 2 to 1023 are:
";
39
40 // display prime numbers in range 2-1023
41 for ( int k = 2, counter = 1; k < SIZE; k++ )
42 {
43 if ( sieve.test( k ) ) // bit k is on
44 {
45 cout << setw( 5 ) << k;
46
47 if ( counter++ % 12 == 0 ) // counter is a multiple of 12
48 cout << '
';
49 } // end if
50 } // end for
51
52 cout << endl;
53
54 // get value from user to determine whether value is prime
55 cout << "
Enter a value from 2 to 1023 (-1 to end): ";
56 cin >> value;
57
58 // determine whether user input is prime
59 while ( value != -1 )
60 {
61 if ( sieve[ value ] ) // prime number
62 cout << value << " is a prime number
";
63 else // not a prime number
64 cout << value << " is not a prime number
";
65
66 cout << "
Enter a value from 2 to 1023 (-1 to end): ";
67 cin >> value;
68 } // end while
69
70 return 0;
71 } // end main

 

 The prime numbers in the range 2 to 1023 are:
 2 3 5 7 11 13 17 19 23 29 31 37
 41 43 47 53 59 61 67 71 73 79 83 89
 97 101 103 107 109 113 127 131 137 139 149 151
 157 163 167 173 179 181 191 193 197 199 211 223
 227 229 233 239 241 251 257 263 269 271 277 281
 283 293 307 311 313 317 331 337 347 349 353 359
 367 373 379 383 389 397 401 409 419 421 431 433
 439 443 449 457 461 463 467 479 487 491 499 503
 509 521 523 541 547 557 563 569 571 577 587 593
 599 601 607 613 617 619 631 641 643 647 653 659
 661 673 677 683 691 701 709 719 727 733 739 743
 751 757 761 769 773 787 797 809 811 821 823 827
 829 839 853 857 859 863 877 881 883 887 907 911
 919 929 937 941 947 953 967 971 977 983 991 997
 1009 1013 1019 1021

 Enter a value from 2 to 1023 (-1 to end): 389
 389 is a prime number

 Enter a value from 2 to 1023 (-1 to end): 88
 88 is not a prime number

 Enter a value from 2 to 1023 (-1 to end): -1

 

Line 20 creates a bitset of size bits (size is 1024 in this example). By default, all the bits in the bitset are set "off." Line 21 calls function flip to set all bits "on." Numbers 0 and 1 are not prime numbers, so lines 2223 call function reset to set bits 0 and 1 "off." Lines 2936 determine all the prime numbers from 2 to 1023. The integer finalBit (line 26) is used to determine when the algorithm is complete. The basic algorithm is that a number is prime if it has no divisors other than 1 and itself. Starting with the number 2, we can eliminate all multiples of that number. The number 2 is divisible only by 1 and itself, so it is prime. Therefore, we can eliminate 4, 6, 8 and so on. The number 3 is divisible only by 1 and itself. Therefore, we can eliminate all multiples of 3 (keep in mind that all even numbers have already been eliminated).