Bit Masks: The Key to Zeroing in on a Bit

The key to making our bit vector work is to gain the ability to access and modify individual bits of an integer. As a reminder, our goal with a bit vector is to do things like represent the set 0, 3, 4, 6 using a single integer such as 89. Again, the way this works is that 89 in binary is 01011001 and, therefore, has 1 bits at indexes 0, 3, 4, and 6 (with index 0 being the right-most bit and the indexes increasing going leftward). Although you and I can look at the binary number 01011001 and see which indexes contain 1 bits, we need a way to write code so that the computer can do this as well.

Here’s another way to think about this problem. I once read a true story about a child genius who, despite his genius—or more accurately, because of his genius—couldn’t learn to read. The problem was that when he saw a page of words, his mind took in all the letters and words simultaneously. As such, he could never focus on just a single word.

The same applies to our case. Even if we enter into our Python terminal the binary string 0b01011001, the computer will immediately spit out 89 because, like the genius, the computer is looking at the entire number as a whole. We need to somehow get the computer to identify a single bit within that number.

Now, a specialist did end up finding a way to teach the child prodigy to read, and the child eventually grew up and went on to become a highly successful and prolific educator himself. What was the specialist’s trick?

The specialist figured out that if they covered an entire book page except for one word, they could get the child to focus on that word alone. By blocking the child’s view of all the other distracting words, the child was able to take in one word at a time. To read the next word, they revealed the next word only after blocking the previous word.

And so, we’re going to use that same trick to get the computer to access individual bits.

The general approach for accessing individual bits of an integer is by using something called a mask (or bit mask). A mask is, in fact, an integer, but it’s an integer whose bits are cleverly set to allow us to focus on a specific part of another integer. Let’s take a look at an example using the integer 89. Again, in base 2, this is 01011001.

Suppose we want to check whether the bit at index 4 is a 0 bit or a 1 bit. You and I can see that it’s a 1 bit, but the computer sees the entire number of 89. Here’s how we get the computer to focus only on the bit at index 4.

We create a new integer—the mask—whose bits are all set to 0 except for the bit at index 4, which is set to 1. This is the integer 00010000. In decimal, this happens to be 16, but we don’t care about that. What we care about is that the only bit set to 1 is the bit at index 4, and that the rest are 0 bits. This integer, 00010000, is our mask.

Next, we AND our integer of 89 with this mask:

The result is a number whose bits are all 0 except for the bit at index 4. That is, wherever our mask contains a 0 bit, we “cover” the corresponding bit of the 89 since when we AND each of the 89’s other bits with the mask’s corresponding 0 bit, the resulting bit will always be 0.

However, our mask has a 1 bit at index 4. This will enable us to see what bit lies in the 89’s index 4 since when we AND the bit at the 89’s index 4 with the mask’s 1 bit, the result will always be the same as the 89’s index 4 bit. As you’ve learned, a key property of AND is that whenever we AND a 1 bit with another bit, the result is always that other bit.

Now, suppose we want to identify the index 4 bit of the integer 73. This bit is a 0. Therefore, when we AND the 73 with our same mask, 00010000, we get:

It comes out that when we AND any integer with a mask, if the resulting integer is 0 (which is a slew of 0 bits), we know that the bit we’re inspecting is a 0 bit. However, if the resulting integer is anything other than a 0, we know that the bit we’re inspecting is a 1 bit.

When we used the mask on the integer 89, the result was 00010000. In decimal, this happens to be 16, but the thing we care about is simply whether the result is 0 or not. Because it’s 16, and 16 is most certainly not 0, we know that the bit we’re inspecting is a 1 bit.

This is essentially the same approach the specialist used with the genius child. We’re using the mask’s 0 bits to block the computer’s view of the 89’s other bits so that it can focus solely on the bit at index 4, as shown here:

We leave an opening—by way of a 1 bit at index 4—to focus and see which bit lies at the 89’s index 4. Without the mask, all the other bits get in the way because the computer naturally sees all the bits together as a whole without being able to isolate a single bit. The mask, though, is what allows us to isolate a single bit.

In short, the 1 bit of the mask at index 4 serves as the opening for the computer to see what lies behind it. This is because when we AND a 1 bit with another bit, the result will always be that other bit. So, if the resulting integer is 0, we know that our bit in question is also 0. If the result is anything other than 0, then our bit in question must be a 1.

The following code creates and uses this mask:

The output of this code is 16, which means that there’s a 1 bit at index 4. If there were a 0 bit at index 4, the result would have been 0.

A Get-Bit Function

As we’ve seen, with a code expression like 0b00010000 & 89, we can use a mask to get the computer to reveal an individual bit at any index of an integer. Let’s now use this idea to write a function that checks a bit at a given index of a particular integer.

That is, we’ll create a function, get_bit, which will accept two parameters. The first parameter is our integer, and the second parameter is the index of the bit we want to inspect. Let’s start writing it:

This code is only half-baked, but the final line of code makes sense. The final line ANDs the mask and integer together and then returns False if the result is 0 or returns True if the result is any integer other than 0. But we haven’t yet figured out how to write code to produce the mask itself.

To solve this, we’ll once again use the power of bitwise operations. Specifically, we’ll use the shift operator to solve this task! I’ll present the code first, and then explain it:

To create our mask, we start with an integer 1. This is equivalent to 00000001, where the 1 bit is at index 0 of the integer. If we want the 1 bit of our mask to be at index 4 instead, all we have to do is simply shift the 1 bit four places to the left. This produces our desired mask of 00010000. In other words, we can take the integer 1 and left-shift it by whatever number index is. Cool!

Okay, we’re making progress. We’ve successfully written code to read individual bits from an integer. Next up, let’s figure out how to change bits of an integer, that is, flipping a bit from 0 to 1 or vice versa.

In bitwise manipulation jargon, the term for flipping a bit from 0 to 1 is called setting the bit. And the term for flipping a bit from 1 to 0 is called clearing a bit. Let’s now write the code for each of these operations.

A Set-Bit Function

Once again, we’re going to use a mask to help us achieve our task at hand. As with the mask we used to read a bit, our mask will be a series of zeroes except for the index whose bit we want to set. This index will contain the only 1 bit.

To set our desired bit (that is, to make the bit 1), we simply OR the mask with our integer. Let’s see how this works.

Suppose our integer is 89, which in binary is 01011001. To set its index 2 bit, we create a mask of zeroes with the index 2 bit set to 1, which is 00000100. We then OR the mask with the 01011001, which yields:

This result is the same as the 89, except that its bit at index 2 is now a 1 bit. I’ll call this bit the “setting bit.”

The trick here is based on one of the key properties of OR. Whenever we OR any bit with 1, the result will always be a 1. So, because we OR the setting bit with a 1, the bit will now be a 1 bit whether it was a 1 bit before or not.

At the same time, our mask ensures that we don’t modify any of the other bits. This works because the rest of our mask (other than the setting bit) consists of 0 bits. Another key property of OR is that whenever we OR 0 with another bit, the result will be that other bit. So, we leave all the other bits unchanged.

We can implement this as a function:

That is, we first create the mask, and then OR the integer with that mask.

Note that we’re not modifying the original integer since that isn’t something that Python does. Instead, we’re returning a new integer that is the result of ORing the original integer with our mask. The same goes for the methods that follow.

A Clear-Bit Function

If you can believe it, clearing a bit is even more fun than setting a bit. To clear a bit, we’re going to create a different type of mask than before. That is, previously, our masks were a bunch of zeroes with a single 1 bit. But now, we’ll do the opposite, as our mask will be a bunch of 1 bits, with only a single 0 bit.

Again, let’s work with the example integer 89. Suppose we want to clear the bit at index 3. To do this, we create a mask of 1 bits except for the bit at index 3, which is a 0 bit. Our mask, then, is 11110111.

We then AND the mask together with the 89, which gives us this:

This result is exactly what we want; it’s an integer that’s identical to 89 except that its bit at index 3 was flipped to 0. I’ll call this bit the “clearing bit.”

The reason this works is that we’re ANDing the clearing bit with 0. And as we’ve seen, whenever we AND any bit with 0, the result will always be 0.

At the same time, our mask ensures that we don’t change any other bits. We accomplish this by ANDing all the other bits with 1. We’ve seen that one of the key properties of AND is that when we AND 1 with any bit, the result will be that other bit, unchanged.

In sum, to clear a bit, we AND the clearing bit with 0, while ANDing all the other bits with 1 to leave them as they are.

The nerd inside of you is loving this, I know. But now let’s get to the fun part—creating the mask.

Our goal is to create a mask that consists of 1 bits except for a 0 bit at the desired index. Now, it can be tricky to kick things off by setting an integer that contains only 1 bits because it’s not always clear as to what Python integer we should use. Sure, the integer 255 is a series of eight 1 bits, but if the size of a computer’s integers is, say, 32 bits, there will be 24 0 bits on the left-most side of the integer. And we don’t want that, since we need all of our bits (save for one) to be 1. Furthermore, many computers use 64-bit integers, so we can’t always know with certainty what integer we should use to initialize our mask.

However, this is where the NOT operation is our friend.

Suppose we want to clear the bit at index 4. This means that we want a mask along the lines of 11110111. To accomplish this, we’ll start by creating the opposite mask, 00001000, which we’ve already seen how to do earlier. (That is, we’ll take the integer 1 and shift it leftward four places.) Then, to produce our desired mask, we simply NOT the mask to invert its bits! Thus, 00001000 becomes 11110111, which is precisely the mask we want.

This approach works no matter the number of bits in an integer. Whether there are 10 0 bits trailing on the left-hand side of our initial mask, or 20 such trailing 0 bits, all these bits will now be flipped to 1 bits.

In code, we can create a function that executes this strategy:

That is, to create our mask, we first shift a 1 bit leftward and then NOT the result with the ~ operator. We then return the result of ANDing this mask with our integer.

A Toggle Bit Function

We’re on a roll, so let’s create another classic bit vector function. To toggle a bit is to flip it to the opposite of what it currently is. So, if the bit is currently a 0, toggling it will set it to 1. Likewise, if the bit is currently a 1, toggling it will clear it to 0. I’m going to call the bit we’re interested in toggling the “toggle bit.”

Technically, we could accomplish this by using an if statement in conjunction with our get_bit, set_bit, and clear_bit functions. That is, we can use get_bit to check whether the toggle bit is a 0 or 1. If it’s a 0, we’ll run the integer through the set_bit function, and if the toggle bit is a 1, we’ll run the integer through the clear_bit function.

While this approach will certainly do the trick, there is a much more concise—and nerdier—method.

To toggle a bit, we first create a mask of zeroes, except for a 1 bit that lives at the index of our toggle bit. Then, we XOR the original integer with our mask. And that’s it! Let’s look at how this all plays out.

Suppose we want to toggle the bit at index 2 of the integer 89. To do this, we XOR the 89 with our mask as shown here:

Boom! The bit at index 2 gets toggled from a 0 to a 1.

Now, let’s toggle index 3 from the 89:

Here, the bit at index 3 gets toggled from a 1 to a 0.

The reason this all works is because of the key properties of XOR. That is, if the toggle bit is currently a 0, XORing it with 1 produces a 1 bit. On the other hand, if our toggle bit is a 1, XORing it with 1 produces a 0 bit.

And so, when we XOR our toggle bit with 1, the result will be the opposite of the toggle bit.

At the same time, we leave all the other bits unchanged by XORing all of them with 0. A 0 bit XORred with 0 produces 0, while a 1 bit XORred with 0 produces 1. And so, we can code up a toggle function, keeping it short and sweet, like this:

Now that we have a general approach for getting, setting, clearing, and toggling bits, we’re finally—at long last—ready to implement our own bit vector.

Code Implementation: Bit Vector

The code we wrote in the previous section is almost everything we need to implement our bit vector; there’s only one missing piece. As I mentioned earlier, a single integer can only hold 32 bits, and it can therefore only store a set of values that range from 0 to 31. To store additional values, we’ll need an array of integers.

Following is a Python implementation of a bit vector that uses an array of integers to store its values. The scheme goes like this: the first integer represents values in the range of 0 to 31. The second integer represents values in the range of 32 to 63. The third integer represents values in the range of 64 to 95, and so on. Each next integer within the array will store the next set of 32 values.

First, I’ll show you the code, and then we’ll walk through it line by line:

When creating a new bit vector, the user is expected to include as a parameter the number of expected values. That is, if we expect to store a set whose values range from 0 to 255, we’ll initialize the bit vector with code like this:

The underlying data structure behind the bit vector is the self.integers array, which is, you guessed it, an array of integers. When the bit vector is first initialized, the constructor creates that array and then fills it with the appropriate number of zeroes. If we determine that self.integers needs to hold five integers, this means the array will start out as: [0, 0, 0, 0, 0].

To compute how many 0s we need to fill our array, our constructor first makes the assumption that each integer contains 32 bits (each of which will be either a 0 or a 1). If our bit vector stores values within a range of 0 to 255, this will require 256 bits. Because each integer in our self.integers array can store 32 of these bits, we’ll need our array to hold eight integers in total since 256 // 32 = 8.

And so, the most important code of our constructor sets this all up with:

(Note that we could have also performed the same calculation with integers_length = range_of_bits >> 5 since shifting rightward by 5 is the equivalent of dividing by 32! But I used the regular division operator to make the code easier to understand.)

In any case, the range_of_bits // 32 calculation works perfectly if the range_of_bits is divisible by 32. But let’s say our scenario required 1,000 bits. If we divide 1,000 by 32, we get 31.25. This would mean that our data.integers array would have to hold 31.25 integers, but there isn’t such a thing as a quarter of an integer!

This means that, practically speaking, we’ll need 32 integers. To account for this, our code checks to see whether there’s a remainder in range_of_bits % 32, and if there is, we add an extra integer inside the self.integers array to be able to store those extra bits. And so, we have the following code:

Getting back again to the final line of our constructor, self.integers = [0] * integers_length is what fills the self.integers array with zeroes. So, if integers_length is 8, for example, the self.integers will end up being [0, 0, 0, 0, 0, 0, 0, 0]. This simple array is the heart of the bit vector.

The read_bit function is almost identical to how we wrote it earlier, except that before, we simply passed a single integer to read one of its bits. Now, however, we have to first identify which integer within self.integers we need to access. Once we grab the correct integer, we can read a bit from it.

The first half of the read_bit function goes like this:

To find the appropriate bit within the appropriate integer, we use division, getting both the quotient and the remainder. Because each integer contains 32 bits, we divide the index we’re reading from by 32. For example, if we want to inspect the bit corresponding to the value 64, we divide 64 by 32. This gives us a quotient of 2, and a remainder of 0. This means that the bit representing 64 can be found in the integer at index 2 (of self.integers), and specifically at zeroth bit index within that integer. That is, it’s the first bit of the third integer.

Similarly, if we desired to access the bit corresponding to the value 65, we once again divide this number by 32. This time, we get a quotient of 2 but a remainder of 1. This indicates that the 65 bit is found at index 2 (of self.integers), but this time the specific bit index within this integer is 1. In other words, the 65 bit is the second bit of the third integer.

So, our read_bit method calculates both an integer_index and a bit_index. The integer_index tells us the index of the integer within self.integers we need to inspect. The bit_index tells us which bit within that single integer we want to read.

The final two lines of read_bit work as our original read_bit method of a single integer did. It’s just that now we use the bit_index to compute the mask and then AND it with the desired integer from self.integers:

If the result is False, it means that the bit we’re reading is 0, and if the result is True, the bit is 1.

Let’s now jump into the set_bit, clear_bit, and toggle_bit methods. The methods begin by computing the integer_index and bit_index in the same way that the read_bit method did. Any time we modify a bit, we do so by updating the integer in which that bit lives. With the set_bit method, we can’t merely return a new integer as our original set_bit method did. Instead, we now modify the target integer (which is self.integers[integer_index]) with the following code:

The |= operator works much like the += operator. That is, just as x += 1 is equivalent to x = x + 1, similarly, x |= mask is equivalent to x = x | mask.

Along the same lines, the clear_bit method updates the target integer with self.integers[integer_index] &= mask, and the toggle_bit method updates the target integer using self.integers[integer_index] ^= mask.

I also included a values method in our BitVector class. This method returns an array containing the set of values that our bit vector represents. That is, if our bit vector’s self.integers is [89] in order to represent the set 0, 3, 4, 6, then values will return the array [0, 3, 4, 6].

And that’s it!

Using Our Bit Vector

Now that we have a working bit vector, let’s use it to serve as our set for the algorithms we looked at earlier: finding duplicates and counting sort.

In the following code, I’ve rewritten our finding duplicates algorithm by using a bit vector instead of a hash table or Boolean array:

I set the bit vector to hold values in the range of 0 through 1023 in this example, assuming that our array will only hold values in that range. Obviously, if you know that array will hold a different range of values, you’d adjust this accordingly.

We can also now rewrite our counting sort algorithm using a bit vector:

Interestingly, when I benchmark these snippets, they run a little slower than the Boolean array and hash table implementations. However, the advantage of bit vectors is the space savings they offer.

Let’s see how much space bit vectors save us.