Bit Vectors

Suppose we want to maintain a set of the integers 0, 3, 4, 6. So far, we’ve seen two possible ways of doing this.

We have the hash table approach:

And we also have the Boolean array approach:

But there’s a third approach. What I’m about to show you is one of my favorite tricks in all of computer science. I’ll introduce it by revealing one layer at a time.

To start, let’s take the previous Boolean array and swap out each False for a 0, and each True for a 1:

Recall that with base 2, we can represent any integer using only 0’s and 1’s. (If you’re rusty with base 2, check out the discussion of binary numbers in .) With this in mind, we can use base 2 to represent the Boolean array [1, 0, 0, 1, 1, 0, 1, 0] using a simple binary number:

We can represent the set of 0, 3, 4, 6 with the single base 2 number 10011010.

To make things more convenient, we’re going to reverse the direction of the way we use bit indexes. That is, with an array, the left-most place is the 0th index. However, if we’re using a binary number to represent our data, since the right-most place of any number is the smallest place, it’ll be more intuitive if we use the right-most place to be the 0th index. And so, the right-most bit will represent index 0, and the indexes will increase as we move leftward.

Here’s a visual of how we’re using a binary number to represent our set:

As you can see, because we want to store a 0 from our set, we take the right-most index (the 0th index) and make its digit a 1. The same goes for all the other numbers in our set. So, the binary number 01011001 represents our set of integers 0, 3, 4, 6.

In Python, we don’t generally interact with integers in binary form. Instead, we work with them as decimal (base 10) numbers. Accordingly, instead of working with the binary number 01011001, we’d work with its decimal equivalent, which is the integer 89.

Do you know what this means?

It means that we can store the entire set 0, 3, 4, 6 using a single Python integer. Yes, the integer 89 is all we need to represent our set! This has profound implications for how much memory we can save. Our Boolean array had to hold at least seven Boolean values in memory. Likewise, our hash table takes up space with an entire underlying array designed to hold multiple values. But now, we can store the same set inside a single integer.

Let’s take a look at another example, this time working backward. If we were told that the integer 1435 represented a set of numbers, we could figure out which numbers are in the set by converting 1435 to base 2.

Luckily, we don’t have to do this by hand. Python comes with a bin function that accepts an integer and converts it to binary:

This ’0b10110011011’ is called a binary string—it’s a Python string object. The starting characters "0b" are not part of the binary number and can be ignored. It’s there to indicate that the digits that follow it represent a binary number.

We can see that the decimal number 1435 in base 2 is 10110011011. Armed with this binary number, we can now see which integers are in our set, as shown in the following figure:

The single integer 1435 represents the entire set 0, 1, 3, 4, 7, 8, 10. This is an incredibly compact way to store a set of 7 values!

This data structure is called a bit vector. It goes by other names, too, including bit array, bit set, bit string, and bit map. I call it a bit vector since that sounds the coolest.

In the example, our bit vector is nothing more than a single integer, even though we’re treating it as a bona fide data structure. More commonly, though, a bit vector consists of an array of integers, as I’ll explain in the next section.

Before moving on, though, here’s another useful tip: in Python, you can use the expression 0b to convert a number from binary to decimal. That is, if you type 0b10110011011 in your Python terminal, you’ll get a result of 1435. So, the bin keyword converts a number from decimal to binary, and 0b converts a number from binary to decimal. Try it for yourself!

Bits and Bytes

While bit vectors are cool, there’s a catch with storing an entire bit vector inside a single integer: some sets are simply too large to be stored within one integer. Here’s why.

As noted in the previous chapter, most computers store their data as binary numbers. This means that although our Python code may deal with integers in base 10, the computer stores these numbers in base 2.

The smallest unit of measurement of computer space is the bit—short for binary digit—which represents a single 0 or 1. A number larger than 0 or 1 is represented using multiple bits. For example, the binary number 10000000 (which in decimal happens to be 128) takes up 8 bits because there are 8 digits in the binary number. Now, generally speaking, a computer reserves 32 bits in memory to store any integer.

What this means for us is that if we want to use a single integer as a bit vector to store a set of numbers, we’ll only have a maximum of 32 bits available to us. And so, a single integer can only represent a range of numbers from 0 through 31. Accordingly, we’d have no way to include a 32 or 33, for example, in our set.

To avoid confusion, note that the Python bin command only shows a binary number starting from its left-most 1. That is, the command bin(2) spits out 0b10, which is the binary number 10. In truth, though, the integer 2 contains 32 bits. That is, there are another thirty zeroes to the left of the 1 in memory. It’s just that Python doesn’t bother to show us that for the sake of brevity.

Array-Based Bit Vectors

We have a problem on our hands. How can we use a bit vector to store a set that has numbers that lie in a range larger than 0 to 31? The answer is that we can use an array of integers to serve as our bit vector, as shown in the following illustration:

Here, the bit vector [48, 3, 12] represents the set 4, 5, 32, 33, 66, 67. That is, we use the first integer in the bit vector array (which is 48 in this example) to store values from the range 0 through 31. The second integer, though, works with an offset of 32, meaning that we use its 32 bits to represent values from the range of 32 through 63, rather than 0 through 31. The third integer represents the next range of 32 values, namely, 64 through 95. And so on.

Although the size of our bit vector has grown, this approach still provides incredible space savings. For example, the array of the following three integers

stores this entire set of 18 numbers:

In fact, a bit vector of three integers can be used to store up to 96 different values in a set—if every bit were set to 1. Each additional integer we add to the bit vector can store an additional 32 values since, again, each integer contains 32 bits.

Accessing Individual Bits

We’re almost ready to create our own Python implementation of a bit vector. However, there’s one teeny, tiny, itty-bitty, little catch.

That is, Python, as well as most coding languages, doesn’t give us an easy way to access the different bits within an integer. We are essentially utilizing an integer to store a list of set values, but an integer is not actually a list. It’s just an integer! Even though you and I can figure out that the decimal integer 2148077570, when converted to binary, is the number 10000000000010010001000000000010, how can we write code that figures out which bit indexes contain 1 bits?

By contrast, Python arrays allow us to easily look up or change a value at any given index with simple commands like array[5] and array[5] = 1. But Python doesn’t give us such commands for integers. There’s no Python function like 44.get_bit_at_index_5 or 44[5].

You may be thinking that we can use the aforementioned bin command to convert an integer into a binary string, such as 0b10000000000010010001000000000010. We can then use a loop to iterate over the string and identify the 1 bits and count which index each one is located at. However, iterating over a string is relatively slow and will neutralize the speed that a bit vector is supposed to offer.

Furthermore, this loop approach only helps for inspecting bits. But we’re still at a loss as to how we can modify an individual bit. Our bit vector will need to do this since we have to set bits to 1 to represent the different values in our set.

So, how do we quickly read and modify the individual bits of an integer? Well, I have some good news and some bad news and some good news. (Yes, you read that correctly.)