Let's Understand Bitshift Operations

Introduction

While coding in some programming languages, we sometimes might stumble upon these little operators called bitshift. Most of us understand that we use these operators to shift bits to either the left or the right, but why do we do it? What do we gain from shifting bits? This is what I'm going to try to explain in this post.

A quick example

This is what bitshift operations look like in some programming languages. Here, we can see a different ammount of bits being shifted to different directions.

Let's take a look at what happens inside our processor whenever we shift our bits.

The mathematics of it

Before we take a look at our computer, let's understand the mathematics behind it:

Conventionally, we use the decimal numeric system to count. That means we have 10 different digits that represent the numbers we use to count:

With this system, we can use up to the digit 9 to count whatever we want to count. But what if we cant to represent a number bigger than 9? What we usually use is the positional notation of the numbers, we add a column to the left of our digits that'll represent the number of 10s we have:

1 0 ~> here, we have 1 tens and 0 ones
1 1
1 2 ~> here, we have 1 tens and 2 ones
1 3
1 4
1 5
1 6 ~> here, we have 1 tens and 6 ones
1 7
1 8
1 9 ~> here, we have 1 tens and 9 ones

This goes on forever, and we keep adding columns to the left. And this is what we call positional notation, because each of these positions have different meanings and responsibilities.

Keeping all we just saw in mind, let's remember how we see multiplication by 10, in base 10:

4 4 x 10 = 4 4 0
2 9 x 10 = 2 9 0
1 9 8 x 10 = 1 9 8 0

we all know the answer to those, right? We just add a 0 to the right. But if we look at it another way, it's almost like we are taking our numbers and shifting them to the left one time. By shifting them to the left, we get an 'empty' position and fill it with a 0.

And the same logic goes for multiplying by 100, 1000, 10000 and so on. And as for division, we just have to think of the opposite operation.

Now, all of this positional notation also works for the binary numerical system, which is what computers actually use to make operations. In base 2, instead of multiplying by 10 to make the shifts, we just have to multiply our numbers by 2.

And again, the same logic applies for division

Inside the processor

After learning what is the mathematics behind shifting numbers left and right, let's take a look at some example code:

In this snippet, no matter which of the operations you choose to use in your program, the variable result will hold the same final value. That's because shifting one bit to the left is equivalent to multiplying our number by 2.

So if these operations get me to the same result, why use bitshit instead of multiplications? Why make our lives "harder" by using an operator we are not used to? To answer those questions, let's go back to the 90s.

If we look at the way old processors used to work, most of them had no native multiplication and division instructions. The processors would simply perform a series of additions and subtractions until we got to the result of the multiplications and divisions we wanted. On the other hand, a lot of processors had native bitshift operations. At the end of the day, bitshift operations were a lot faster than multiplication/division, and that's why programmers used them. Here's a quick example of how a native shift instruction looks like in Assembly:

Conclusions

To finish it off, let's recap:

Bitshift operations were used mostly because they performed a lot better than multiplication and division inside old processors;
In modern days, using modern processors, we don't really need to use bitshift operations unless we are 100% sure that there's performance gain in doing so;
The implementation of a bitshift operation and a multiplication/division operation in x86 Assembly is, virtually, the same.

It is important for us to know what these things are and what they do, and to also know when not to use them.

At the end of the day, we want our code to be simple and readable.