Last post we talked about binary on a basic level. If you are not comfortable with reading binary or counting in binary I recommend you check out that post before reading this one. Using bit shifting and bit masking judiciously opens the door for massive performance optimizations in low level hardware and high level systems alike. Read on to find out how.
There are two basic types of bit shifting. You can either shift left or right. Both act similarly to each other. Although the term bit shift sounds frightening, hopefully you will be able to see how you have used similar techniques in dealing with elementary arithmetic.
Left shift is probably the most common type of bit shifting. Check out the number two in binary.
To perform a ‘Left Bit Shift’ of one to this number you simply add a zero to the right. Which in turn shifts the number left by one place. Giving us this:
That syntax may look complicated, but you simply have the number you want to shift on the left. In our case that was ‘010.’ You then have the operation you want to perform on that number, which was a ‘Left Bit Shift’ represented by two less-than signs (<<). We use less-than signs to make it easier to understand which direction we want to shift. Less-than signs point left. Therefore we use them to represent a shift to the left. Finally, the right side of the equation shows how many places we want to shift the number left. Have a look at some more examples.
The clever ones of the bunch can probably already guess the math behind how this works. If you looked at the first example we started with the number 2. We shifted it left by one and ended up with the number 4. Well, in our second example we have the number 1 and we shift it left by two and also end up with the number 4. The formula for shifting a bit is as follows.
Before you lose it with all the ‘math – E’ symbols, stop and think – where have we seen this before? Again, harkening back to our third grade math class, you will realize we have been doing things like this with decimal numbers for a long time. What did you do when you wanted to add a zero to a decimal number? You would multiply by ten! Similarly if you wanted to add two zeros you would multiply by one hundred. So the above formula works with decimals just by changing the ‘2’ into a ’10’. In binary if you want to add a zero just multiply a number by two. If you want to add two zeros to the left just multiply it by 4.
Logical Right Shift
It is the exact opposite of the ‘Left Shift,’ so I won’t spend much time on it. Instead of inserting a zero to the right of the number it inserts a zero to the left of the number. In doing so, this shifts the number right. To refer back to the decimal system, think of it like you were dividing a number by ten. 100 becomes 10 and 10 becomes one. The syntax is very similar except we use three greater-than (again think of the direction the arrows are pointing to represent a right shift) symbols to represent the function. The formula is as follows.
Just a quick note: there is a second type of Right Shift called an ‘Arithmetic Right Shift.’ It serves a similar purpose to the logical right shift. The difference is that the logical shift doesn’t preserve a number’s sign where as the arithmetic right shift does preserve the sign.
The easiest way to think of bit masking is to think of it as a filter function. The good news is there are no formulas to it!
The idea is simple enough; it is the process of taking two numbers and performing a logical operation to them. If you are not familiar with logical operations, here is a quick refresher on the two most often used ones.
Why do we need these functions?
So why would you want to do that? These operations are extremely handy when it comes to handling large sets of boolean data. Take for example a power strip that has six outlets in it. Let’s say you wanted to represent the empty outlets with a ‘0’ and the full outlets with a ‘1.’ An empty power strip would then look like this:
Lets plug something in and notice how the state updates.
That was simple. You just place a ‘1’ on the outlet that has been filled. Well, it’s actually not that simple. Because remember that to us we are letting zero and one represent true and false, but to a computer it is still just a zero and a one. So in computer memory we had a value of ‘0’ that represented the initial empty state of our power strip. But now we have used one of the outlets which has resulted in setting our state to ’16’ or ‘010000’. So how do we set the value? We would keep track of the outlets counting from right to left, starting at 0. Which would look like this:
We now see that the the outlet at position 4 has been used. This is where bit shifting comes in. We need to set the value of the bit in the fourth place to one. Now that you understand how bit shifting works, we can come up with a general formula that will give us the number we need to represent a filled outlet position.
state = 1 << position
So if we apply that formula to our power strip we can see the following:
position = 4 state = 1 << 4 1 << 4 = 1 * 2^4 = 16 state = 16 = 010000
Very cool! Now lets see what happens when a second outlet is filled.
So our value has updated from 16 to 18. How should we handle this? If we follow the same strategy as before we will see that position 1 has been filled, and if we put that into our formula we end up getting 000010. That’s not what we need. This is where we mask that fool to get what we want. We can use the OR operation to keep our old values and add the new ones.
oldState = 010000 or 16 plugAdded = 000010 or 2 010000 OR 000010 ----------- newState = 010010 or 18
The general formula for that is as follows:
oldState OR plugAdded --------------- newState
It is important to note that although they work the same way in this instance, the OR operation is different from a simple addition. Awesome! We have updated our power-strip state and we know how to update it in the future when someone else plugs into it. Well, what if someone unplugs? Consider the following:
Our state was 18 and now it is 2. What general formula can we use to govern this transition? This one is a little more tricky. Essentially what is happening is the reverse of plugging something in. To plug something in is represented by all zeroes except in the position where the plug is being added; that position is being represented by a one. The reverse of that would be represented by all ones except at the position where the plug is being removed. That should be represented by a zero. So how do we achieve this? We will use a NOT operation, which is great for this because it simply reverses 1’s into 0’s and vice versa. Let’s take a look:
plugAdded = 010000 NOT 010000 ----------- plugRemoved = 101111
Resulting in the tongue-in-cheek formula:
NOT plugAdded ------------- plugRemoved
The final trick to update the state is to use the AND bit mask to the old state.
oldState = 010010 plugRemoved = 101111 010010 AND 101111 ----------- newState = 000010 ---------------------- General Formula for removing a plug oldState AND (NOT)plugAdded -------------------- newState
Whammy blammy, our power strip is now fully functional, thanks to our sweet bit masking and bit shifting skills! These techniques are used heavily in all sorts of AI as well as different graphical programming, and now you know how to use them!