Chapter 12
Saving Space: Every Bit Helps

Over the past several chapters, you’ve discovered a number of Monte Carlo algorithms. In the chapter that follows this one, you’re going to look at your first Monte Carlo data structure called the Bloom filter. The Bloom filter, though, is based on another data structure called a bit vector, which in turn is based on yet another data structure called a Boolean array. In this chapter, I’ll introduce you to both the Boolean array and the bit vector.

Both Boolean arrays and bit vectors, though similar, offer different types of performance boosts. In particular, Boolean arrays optimize for time, while bit vectors optimize for space. In either case, the respective benefits of each of these data structures are pretty astounding.

Along the way, we’ll take a look at bit manipulation, which refers to a set of techniques that enable us to access the individual bits of an integer. Bit manipulation is a foundational computer science concept that has many useful and amazing capabilities, as you’ll soon see.