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
|
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).