Bit Manipulation

The good news is that there is a way to quickly access the individual bits that underlie an integer. And so, it is possible to implement a fast yet space-saving bit vector. Yay!

The bad news, though, is that it’s not that straightforward.

But I have some more good news: the nonstraightforward techniques unlock an entirely new skill set that is handy to know and also a lot of fun. These dandy techniques are generally referred to as bit manipulation. That is, we perform certain special operations to access and modify the individual bits of an integer.

Bitwise Operations

The key to bit manipulation is being able to perform bitwise operations, a special set of operations that deal with integers on the bit level. In the following sections, I’ll describe each one.

The AND Operation

Open your Python terminal and enter these commands:

You’ll find that you’ll get some peculiar results:

Though this may seem strange at first, it all makes sense when we get down to the bit level.

The & operator is the bitwise “AND” operator. (Yes, it’s typically written in all caps.) The AND operator takes two numbers, looks at them as binary numbers, and produces a third number whose bits are set to 1 only in digit places where the first two numbers both have 1 bits.

For example, in the following illustration, we AND the numbers 5 and 6, as shown. (Yes, “AND” can be a verb!)

The integers 5 and 6, which in binary are 00000101 and 00000110, respectively, only share a 1 in the third-to-right index. And so, when we AND the two numbers together, the third number’s bits are all set to 0 except at that index, where we place a 1 bit. This produces the binary number 00000100, which in decimal is the number 4. And that’s why 5 & 6 makes 4.

In sum, when we AND two numbers together, the resulting third number will only have 1 bits where both of the two original numbers also had 1 bits. This is why it’s called “AND”; we need the first number AND the second number to have a 1 bit at the same index.

Let’s look at another example. Here’s what happens when we AND 81 and 103:

Here, there are two indexes at which both 81 and 103 have a 1 bit. This yields a result of 01000001, which in decimal is 65.

Here’s one final example. When we AND 4 and 8, we get:

Because there isn’t a single index in which both 4 and 8 have a 1 bit, 4 & 8 yields 0.

The following are some key properties of the AND operation, which can all be logically derived from our discussion until this point:

• Whenever we AND a 0 bit with a second bit, the result will always be a 0 bit.

• Whenever we AND a 1 bit with a second bit, the result will be identical to that second bit. (That is, 1 & 0 is 0, and 1 & 1 is 1.)

• Whenever we AND two bits that are the same as each other, the result will be the same as those bits. (That is, 0 & 0 is 0, and 1 & 1 is 1.)

For each bitwise operation, I’ll spell out its key properties as I did for the AND operation. Many of these properties may seem obvious, but it will be important to keep them in mind for discussions further on in the chapter. Trust me.

The OR Operation

Another major bitwise operation is the OR operation. In Python, we execute this operation with the | character, for example, 81 | 103.

When we OR two numbers together, the resulting third number has 1 bits wherever either of the two original numbers had 1 bits. That is, it’s enough for only one of the two original numbers to have a 1 bit in order for the third number to have a 1 bit at that same index.

Here’s how this plays out for 81 | 103:

As you can see, the third number gets a 1 bit at any index where either of the two original numbers had a 1 bit. Of course, the third number also gets a 1 bit in a spot where both original numbers had a 1 bit.

This is why the operation is called “OR”: it’s enough for either the first number OR the second number to have a 1 bit at a particular index to show up again as a 1 bit in the third number.

The following are some key properties of the OR operation:

• Whenever we OR a 0 bit with a second bit, the result will be identical to that second bit. (That is, 0 | 0 is 0, and 0 | 1 is 1.)

• Whenever we OR a 1 bit with a second bit, the result will be a 1 bit. (That is, that first 1 bit alone will be enough to guarantee that the third number will have a 1 bit.)

• Whenever we OR two of the same bits, the result will be a bit that is the same as those bits. (That is, 0 | 0 is 0, and 1 | 1 is 1.)

• Whenever we OR two opposite bits, the result will be 1. (That is, 0 | 1 is 1, and 1 | 0 is 1.)

The XOR Operation

The XOR operation is an interesting operation. XOR stands for “Exclusive OR” and is pronounced by many as “ex-or.” (A minority of people pronounce it “zor,” which certainly sounds cool, but might get you some funny looks.) In Python, we execute XOR using the ^ operator, for example, 81 ^ 103.

When we XOR two numbers, we produce a third number that contains 1 bits at indexes only where just one of the two original numbers had 1 bits. That is, if both original numbers have 1 bits at the same index (and certainly if both original numbers had 0 bits at the same index), the third number will have a 0 bit at that index. So, XOR is a little like OR, except that it excludes indexes where both of the original numbers contain 1 bits. The following image illustrates the example 81 ^ 103:

Here, there are four indexes where one number has a 0 bit and the other has a 1 bit. Accordingly, these are the four indexes where the third number receives a 1 bit. Again, where the two numbers both have a 1 bit, such as the right-most index, the third number receives a 0 bit. This example yields the number 00110110, which is 54 in decimal.

Another way I like to think about the XOR operation is that it serves as a litmus test that produces 1 bits in each digit place wherever the two integers have opposite bits. In other words, it’s a great way to see precisely where two integers differ in terms of bits.

The following are some key properties of the XOR operation:

• Whenever we XOR two identical bits, the result will be a 0 bit.

• Whenever we XOR two opposite bits, the result will be a 1 bit.

• Whenever we XOR a 0 bit with a second bit, the result will be that second bit. (That is, 0 ^ 0 is 0, and 0 ^ 1 is 1.)

• Whenever we XOR a 1 bit with a second bit, the result will be the opposite of that second bit. (That is, 1 ^ 1 is 0, and 1 ^ 0 is 1.)

The NOT Operation

Unlike the previous three operations, which use two numbers to produce a third one, the NOT operation uses a single number to produce a second number. This operation, which in Python is executed using the ~ operator, is pretty simple. It produces a new number that is the complete inverse of the first number. That is, wherever the first number has a 0 bit, the new number has a 1 bit. Likewise, at each index where the first number has a 1 bit, the new number has a 0 bit. The image illustrates the example ~103:

So, ~103, in theory, should produce 152 since that’s the binary inverse of 103.

That being said, there’s a small catch. If we execute ~103 in Python, we get the surprising result of -104, and not the 152 we expected.

In truth, though, the numbers -104 and 152 can both be represented using the same bit pattern of 10011000. This is because Python uses a popular numeric system called two’s complement to represent negative numbers using base 2. (You can read more about two’s complement in an article located on the book’s web page.)

In any case, ~103 does indeed produce the bit pattern 10011000 as we expected it would. But 10011000 can translate into either -104 or 152, and Python policy is to always return the negative number when we use the ~ operator.

The Shift Operation

The fifth, and final, bitwise operation is known as shifting. Shifting operates on a single number, and we can shift bits either to the left or to the right. Let’s look at an example.

The number 73 in binary is 01001001. We can shift each bit one place to the left with the command 73 << 1, as shown in the following illustration:

Each bit, whether 1 or 0, moves leftward by one place. This produces the number 10010010, which in decimal is 146. Note that when we shift leftward, the right-most place gets filled in by a 0 bit. There’s no digit from the right that we can move into that spot, so we simply place a 0 there.

Now, we can shift by more than one place at a time. If we want to shift each bit leftward by two places, for example, we’d write 73 << 2. What this produces is shown in the .

This is the equivalent of executing 73 << 1 << 1. Note that here, the two right-most places get filled in with 0 bits.

What’s interesting is that shifting a number leftward by one place, in effect, doubles the number. This is always the case since each 1 bit doubles in value by shifting one place to the left. This makes sense because each digit place represents a number twice as large as the digit place to its right. So, when we shift 73 << 1, we get 146, as 146 is double 73.

When we shift a number leftward by two places, it’s the equivalent of multiplying the number by 4. When we shift it leftward by three places, we’re effectively multiplying the number by 8. To put this more generally, when we shift a number leftward by K places, we’re multiplying the number by 2^K.

We can also shift a number rightward. For example, we can shift 146 one place to the right with the command 146 >> 1, as shown here:

Note that the left-most place gets filled in with a 0. When we shift a number rightward by one place, we are basically halving the number. As is clear from this example, half of 146 is 73.

Now, let’s look at what happens when we shift the number 73 rightward by one place:

Here’s something noteworthy: the 73 had a 1 bit in the right-most index. When we shift that bit rightward, it falls into oblivion. So in truth, it doesn’t matter what the right-most bit is; whether it’s a 0 or a 1, it goes away.

Now, if the right-most bit of the original number was indeed a 0, the original number would have been 72. It turns out that shifting 73 >> 1 and 72 >> 1 both yield the same result of 36.

It emerges that when we shift a number rightward, we divide the number precisely in half only when the number is even. That is, with 146 >> 1 = 73, the number 73 is exactly half of 146. However, when the number we’re shifting is odd, we halve the number and then drop the remainder. That is, technically speaking, half of 73 is 36.5. However, when we shift 73 one place to the right, we end up with a rounded-down result of 36.

Rounding a number down to the nearest integer when dividing is commonly known as floor division. And so, we can say that shifting a number rightward by one place halves that number using floor division.

Using Bitwise Operations for Good

Well, that’s our motley crew of bitwise operations. At first glance, they can appear kind of random and not particularly useful. However, these bitwise operations can be incredibly useful. In fact, all math operations that a computer performs rely on these operations under the hood! Let’s look at one example.

Adding Binary Numbers

If we were to use pencil and paper to add two binary numbers together, such as 5 + 2, it would look like this:

This example is pretty simple in that we didn’t have to carry any numbers. If we had to carry numbers, as in the example of 5 + 1, it would look like this:

Carrying works the same way as with base 10. It’s just that whenever we add two 1 bits together, we have to carry that 1 bit to the next place to the left. (With base 10, we carry a 1 when the sum of two digits is greater than 9.)

Now, here’s the interesting thing. At the most primitive machine level, a computer does not have a + operation. Just as a computer at the machine level only deals with binary numbers (rather than decimal numbers), it likewise only deals with bitwise operations. This means that a math operation as simple as adding two numbers can only be done by a computer by using bitwise operations.

But how, exactly, do we use bitwise operations to add two numbers together?

This answer is more straightforward in cases where we don’t need to carry. Take a look again at the previous diagram showing the bit addition example of 5 + 2. No carrying is needed there, as there’s no index where both numbers have a 1 bit. Because of this, conveniently enough, we can perform the addition by simply XORing the 5 and 2. This may seem like a cool coincidence at first, but it makes sense after thinking about it a bit.

Take a good look at the 5 + 2 visual. The result is, in fact, the same as XORing the 5 and 2. The reason this works is that when we add two 0 bits together, we want to get 0. Indeed, XORing does this. Similarly, we need it to be that when we add a 0 bit and a 1 bit, we get a resulting 1 bit. XORing does this as well. Sweet!

The tricky part, though, is when we have a case where both numbers have a 1 bit at the same index. Our goal in that case is to have a result of 0 at that index, which XORing takes care of as well. However, we also need to take care of carrying a 1 to the next place over to the left, which XORing does not do automatically.

That is, if we simply XOR two numbers without performing any extra steps, the necessary carrying will not take place, and we’ll end up with an incorrect result. Let’s look at this visually for the case of 5 + 1. If all we do is XOR the 5 and 1 together, we end up with:

This would indicate that the sum of 5 and 1 is 4, which is clearly incorrect. However, although this result is incorrect, it’s headed in the right direction. The result of the XOR operation does, after all, make it so that three out of the four digits of our result are, in fact, correct, as shown in the .

Here, we get a result of 0100, while the true sum we want is 0110.

So, it turns out that XORing the two numbers gets us most of the way to the desired solution. It produces what I call the “sum-without-carry.” That is, it produces a sum that is accurate if we don’t have to carry any digits. And even if we do need to carry, the sum-without-carry is almost accurate. The only thing we’re missing is the carrying of numbers.

Luckily, we can perform the carrying with some additional bitwise operations.

Carrying

The general strategy for carrying goes like this. If we could, somehow, compute what I call the “carry number,” we could add it to the sum-without-carry to get the correct sum. Here’s what I mean.

In the previous example of 5 + 1, our sum-without-carry is 0100. This isn’t the correct sum, since we failed to carry a 1 bit over to the second-to-right-most digit place. Now, this 1 bit we failed to carry represents the binary number 0010. Put another way, a 1 bit in the second-to-right-most digit place represents the decimal number 2, which in binary is 0010.

And so, the number 0010—which I call the “carry number”—is what we’re missing from our total sum.

It follows that if we were to add the carry number to the sum-without-carry, we’d get the true sum. That’s what carrying is: we’re adding a carry number to the other numbers we’re working with. Indeed, when we add the carry number 0010 to the sum-without-carry of 0100, we get 0110. This, in decimal, is 6, which is the correct answer to 5 + 1.

For the computer to add the carry number to the sum-without-carry, though, the computer first needs to figure out what the carry number is. Fortunately, we can do this with a clever little trick.

This trick relies on the following observation: if we AND our two numbers, and then shift the result leftward by one place, the result will be the number we’re supposed to have carried, as shown in the .

This result of 0010 is indeed the carry number we’re looking for. Here’s the reason why ANDing with left shifting successfully computes the carry number:

A carry number is only produced when we add two 1 bits together. The AND operation does this; it produces a third number that shows us exactly where the original two numbers shared 1 bits. However, we need to, well, carry that 1 bit over to the next digit place to the left. We accomplish this, though, with the left shift!

Okay, here’s where we’re at so far:

We have the XOR technique that computes the sum without carrying. We now also have the AND-with-shift to produce the carry number. Next, we need to add the sum-without-carry and carry number together. In our example of 5 + 1, we can do this by XORing the sum-without-carry and carry number together. Here’s how this all comes together:

In the previous diagram, Step #1 computes the sum-without-carry (using XOR). Step #2 computes the carry number (using AND with left shift). Step #3 then “adds” the sum-without-carry and the carry number with another XOR command. This gives us the final, and accurate sum of 6!

You may be wondering how Step #3 successfully added the sum-without-carry and carry number, as earlier you saw that XORing isn’t itself the same as adding. Rather, XORing only computes the sum-without-carry!

In fact, you’re right. We happened to get lucky with the example of 5 + 1 since in Step #3, when we XORed 0100 and 0010, there was no carry number! And so, we get the correct answer because the sum-without-carry is indeed correct in cases where no carrying is needed.

In truth, there’s really a Step #4 to the process for adding binary numbers. Step #3 XORed our sum-without-carry with the carry number to produce a new sum-without-carry. Step #4 then uses AND with left-shift again to compute a new carry number as shown here:

In this example, Step #4 produces 0000, which means that there’s no carry number. (There’s only a carry number if there’s at least one 1 bit. This means that our algorithm is complete.

However, in cases when Step #4 does produce a carry number, we need to loop and keep repeating the same steps of XORing and also ANDing plus left-shifting. We do this until we end up with no carry number. Fortunately for us, we will reach such a point in all cases, at least eventually.

Here’s an example of what I mean. Suppose we want to add 7 + 1. If we did this by hand, we’d get:

As you can see, if we perform good old pencil-and-paper addition, we end up having to carry a 1 three times. Performing this computation will be a bit of a doozy. In this scenario, when we perform Step #4, we do end up with a carry number:

This means that we need to keep repeating the same process until we’re left without a carry number. Here’s what this looks like:

Because Step #4 ends with a carry number, Step #5 XORs the new sum-without-carry with the new carry number to produce yet another sum-without-carry. Step #6 then computes a new carry number that is to be added with the latest sum-without-carry.

Step #6 demonstrates that we still have to carry another number, so we loop again and perform Steps #7 and #8. Step #8 yields no carry number, and the binary addition is complete.

Whew!

Code Implementation: Adding Binary Numbers

Fortunately, the code for adding binary numbers is short and to the point:

We run a loop where, in each iteration, we first XOR the two numbers we’re adding to produce a sum_without_carry. We then AND the two numbers and shift one place leftward to produce a carry_number.

We then want to add the sum_without_carry to the carry_number, so we update the first_number to now be the sum_without_carry and the second_number to now be the carry_number and repeat the loop again.

The loop terminates once the second_number, which is equivalent to the carry_number (after the first round of the loop is complete), is 0. At that point, we return the first_number, which is equivalent to the sum_without_carry.

You’ve now seen how bitwise operators are a lot more useful than they look. Indeed, addition is not the only piece of arithmetic that a computer can execute using bitwise operators. Virtually all math that a computer does uses bitwise operators under the hood. Furthermore, computer scientists and mathematicians have discovered various other cool tricks that bitwise operators can pull off. There’s no room for us to discuss all of them here, but hopefully the process of adding two numbers gives you a taste of this.

Now, let’s go back to where we began and use bitwise manipulation to build our bit vector.