You can do more with bits than just turning them on or off. This episode will show you how to shift bits left or right for either really quick multiplication or division or to maneuver them into place.
If you start out with the value 0x5a and want to first isolate the 5 digit, the previous episode explains how to use masking to accomplish this. After masking, you have 0x50 which is not quite the value 5 that you might need. If you want to convert 0x50 into 0x05, then you’re going to have to shift it to the right.
Shifting either left or right is based on binary digits not hexadecimal digits. Because each hexadecimal digit is composed of four binary digits, then to shift a hexadecimal value by one of its own digits, you’ll need to shift the underlying bits by four positions.
Let me show you this in binary with the value 0x50:
0101 0000 shifting this to the right four times gives:
0010 1000 this is after a single shift
0001 0100 this is after two shifts
0000 1010 this is after three right shifts
0000 0101 and finally after four right shifts.
Notice how as the digits shifted to the right, we filled in the vacated positions on the left with zeros. The same thing happens if we shift to the left except that now the vacated positions will be on the right.
Maybe you want to swap hexadecimal digits and turn 0x5a into 0xa5. The example just now shows how to move 0x50 into 0x05. We didn’t actually need to mask out the other digit though. Because when shifting, you know that vacated spots get filled in with zeros but it’s also possible for digits to fall off the other side. Let me show you what happens if we shift 0x5a to the left this time by four shifts.
0101 1010 this is 0x5a before any shifts
1011 0100 this is after the first shift to the left
0110 1000 this is another shift to the left and the first one has dropped
1101 0000 this is the third left shift
1010 0000 after four left shifts, the “a” is now in the left digit and the “5” is gone.
Listen to the full episode or read the full transcript below.
Transcript
The previous episode showed you how you could isolate, set, and clear bits either individually or in a group. If you have a byte with the value 5a in hexadecimal, you know how to isolate each half now and with appropriate masks, you can easily turn this into either 50 or 0a. But what if you wanted to work with just that 5 part? In it’s current position, even after masking, it’s not 5 it’s 50. I’ll show you how you can shift this so it is just 5.
We going to use some operations called shift left and shift right to accomplish this. These are bitwise operations and allow you to shift bits a certain number of positions. Remember that in hexadecimal each digit actually represents 4 binary digits. So to shift the value 50 so it becomes 05, it’ll need to be shifted to the right by 4 positions.
There’s actually a lot more to these operations than might first seem likely. the first thing to note is that each language can define the details of these shift operations as they see fit. The basic operations will be the same but the edge cases could be different between languages.
For example in C++, if you try to shift either left or right by more positions than your type has available, then you may not get the results you expect. This is getting into undefined territory so make sure that when you shift bits, that your shift amounts make sense. Another good way to cause problems is to try shifting by a negative number of locations. Your compiler might generate code that behaves differently than another compiler in these situations.
Another aspect to be aware of when shifting to the right in C++ has to do with negative values. I’m not talking about trying to shift by a negative amount. That already doesn’t make any sense. I’m talking about what happens when you have a negative number and try to shift it to the right. Most implementations that I’ve seen will divide the initial negative number by a power of two. Don’t worry, I’ll explain this more in just a moment. So if you start out with the value -8 and shift this to the right by 1 position, you’ll end up with -4. Just be aware that working with negative numbers like this is technically up to your C++ implementation to define.
And if you look at how shifting is done in C#, it’s actually much more defined.
Before we get into this though, let me explain more about that division and I’ll also show you how you can use shifting to perform multiplication. Let’s do the multiplication first since it’s the easiest. Actually, now’s a good time to take a short break for this message from our sponsor.
( Message from Sponsor )
I’m going to explain shifting in terms of decimal first since we’re all familiar with that. Imagine for a moment that computers understood decimal numbers directly and that a byte consisted not of 8 binary values of zero and one but of 8 decimal digits from 0 through nine. We could count all the way from 0 through 99,999,999. If I’m losing you here, just pretend that 8 digits is the highest anybody can count and that there is no number greater than 8 digits. so the number 100 million or anything greater would not exist.
Alright, lets start with the value 1. We need something other than all zeros or shifting in any direction just has no effect. This applies to computers too. If we take the value 1 and shift it to the left by a single location, what value should we put into the position that the 1 used to occupy? We’ll fill in vacated positions with 0. So shifting the value 1 to the left and then filling in the empty location with a zero gives us the value 10. If we shift it again, this time, we’re shifting the 1 over a location and we’re shifting the 0 over a single location too. then we fill in the empty spot that the 0 used to occupy with another 0. This gives us the value 100 now. Each time we shift left, the value is multiplied by 10. We all learned this in grade school, if you want to multiply by ten, just add a zero on the right. That’s a roundabout way of describing a left shift operation. Or maybe you consider my explanation the more roundabout way and consider it simpler to just think of adding a zero. Whatever works for you.
The end result is that each time you shift a value to the left, you end up putting a new zero on the right. If you shift the value 12 to the left one position, then you just place a single zero on the right and you have 120.
Now what about shifting to the right? Most grade school teachers never went this far in their explanation. Shifting to the right without getting into fractional values means that the right digit is going to fall of the edge. It actually doesn’t matter which way a number is shifted, something’s going to fall off the side being shifted towards. It wasn’t obvious when we shifted 12 to the left to get 120. But what if we have the value 12,345,678 and try shifting that to the left? Since all 8 of our digits are being used, the 1 digit will get cut off. This doesn’t happen in real life because we don’t have a fixed set of digits and our numbers can just keep getting as big as they need.
Shifting the value 12 to the right by one position will cause the 2 digit to fall of and we’re left with just 1. Again, this doesn’t happen in real life because we can start using decimal places and can start growing numbers as small as we want in the other direction. In the real world, shifting 12 to the right by one position will result in 1.2.
Remember that computers don’t have decimal places and don’t have unlimited digits. When programming and shifting, you have to expect digits will fall off the edge. I think I got a bit sidetracked there. Let’s start with 120 and shift that to the right by one position. the 0 digit will fall of the edge and we’ll have 12. this divided the value by 10.
If you can understand what I just described about shifting decimal numbers to the left dropping the leftmost digits while adding zeros on the right vs. shifting decimal numbers to the right and dropping the rightmost digits while adding zeros on the left, then you already understand shifting in binary too.
In many ways, shifting binary is a lot easier. You only have zeros and ones to worry about. Let’s imagine a very small computer that can only work with just 4 bits. If we start with the value 0011 and shift it to the left one, we get 0110. shifting it to the left again gives us 1100. One more time to the left gives us 1000. This caused a 1 digit to fall of the edge and now we only have one bit that has a value of 1. If we did this left shift again, then the realist would be 0000 because now all the 1 digits fell of the edge. Once we’re at all zeros, shifting left or right makes no difference anymore. Let’s go back to the starting value of 0011 and this time shift it to the right. A digit falls off the edge this time too and we have 0001. Shifting that result to the left will not bring back the 1 digit that fell off. It’s gone forever. So shifting 0001 to the left just gives us 0010.
The last thing I want to mention today is how shifting in binary also causes multiplication or division. Just like in decimal if you want to multiply by ten, you add a zero. This works in binary with a slight change. Remember binary is base two. So if you want to multiply by 2 in binary, you just add a zero. And to divide by 2, you just remove the digit on the right. As long as the digit that gets removed is a zero, then you have a nice even division by 2. If it wasn’t a zero, then you have almost divided by 2.
The same thing happens in decimal. If we start with the value 10 and you want to divide by 10, just remove the zero and you have 1. That’s a perfect division by ten. But if you started with 12 and just removed the 2 digit, then your answer will be in the general area but not exact.
In binary, the value 100 is four. Removing the rightmost zero or shifting it to the right depending on how you want to look at it give you the result of 10 which is 2. That’s a perfect division by 2. But if you start out with the value 101 which is 5 and do the same thing, you still end up with 10 which is 2. Now 5 divided by 2 should be 2 and a half but we can’t easily express that without doing something entirely different.