Bitwise Operations Tutorial
Introduction
Before you begin, you should have an understanding of what binary is and how it works. If not, then I recommend first reading over the binary tutorial prior to this article.
You no doubt already know what operators are. It should be one of the first things you learned when you began programming. If you don't, I can tell that you have already used them before. The plus and minus signs, multiplication and division symbols, those are operators. It's a symbol that can affect the value of the data it acts upon or be used for comparitive testing conditions, such as the greater than/less than signs. These are what are known as binary operations, which means they invole two arguments or elements. The minus sign can act as what's known as a unary operator; an operation having only a single element. A good example would be when the minus sign is prefixed to a number to show negation. How all these operators work depends on the data types they involve. For byte and integers, basic arithmitic operations work as you'd expect. For strings, '+' will most often concatenate the two in most languages. And an operator doesn't have to be a symbol or character. In C-based languages, ++ will increment the element's value by one. There are many others, but you should now get the point.
So then what about bitwise operators? Whereas the previously mentioned operators work at the byte level, these work at the bit level. As you should already be aware, a byte is made up of 8 individual bits. With the special set of operations, we can manipulate those bits for several advantages.
Bitwise AND '&'
DarkBasic users should use && for bitwise OR.
Let me start off by saying if you came here with reference to DarkBasic then the operator symbol you use is actually two ampersands '&&', but for nearly every other language that would result in the logical AND operator and not the bitwise operator.
When using the bitwise AND on two equal length elements(same number of bytes), the result is a logical AND performed on the individual bits
themselves. If you were to take the logical AND of 37 and 42 it would simply return true, because both 37 AND 42 are deemed
true(because they are not 0). But the bitwise AND would result in 32. Take a look at numbers' binary representation below:
| 37 | 1 | 0 | 0 | 1 | 0 | 1 |
| 42 | 1 | 0 | 1 | 0 | 1 | 0 |
| 32 | 1 | 0 | 0 | 0 | 0 | 0 |
Remember that a 1 means on or true, and 0 means off or false. When the logical AND is performed on the bits at each place, both bits must be true in order to return true. In this case, only the 6th bit is true in both numbers and thus resulting in 32.
Bitwise OR '|'
DarkBasic users should use || for bitwise OR.
Bitwise OR works much in the same way as AND, only instead of both bits having to be true, either one or the other only needs to be
true in order for the resulting bit to also be true. Given the same numbers we used for the AND example above, the result this time
is 47 as can be seen below.
| 37 | 1 | 0 | 0 | 1 | 0 | 1 |
| 42 | 1 | 0 | 1 | 0 | 1 | 0 |
| 47 | 1 | 0 | 1 | 1 | 1 | 1 |
Bitwise XOR '^'
DarkBasic users should use ~~ for bitwise XOR.
This is what is known as exclusive OR, which means either this is true or that is true but not both. What does this mean
in our binary example below? If either bit is 1 then the result is 1, unless both bits are 1 in which case the result is 0.
| 37 | 1 | 0 | 0 | 1 | 0 | 1 |
| 42 | 1 | 0 | 1 | 0 | 1 | 0 |
| 15 | 0 | 0 | 1 | 1 | 1 | 1 |
One of the simplest forms of data encryption is using a xor cypher. If you have a document you don't want anyone to read, simply XOR all the bytes by a key. The key can be any random number you want. The text will be unreadable and look like a bunch of random characters instead. To decrypt the message, simply xor the data again using the same key. Be warned, however, this is not a very secure method of encryption, but it is an example of a practical use of the XOR operator.
Bit Shifting '<<' '>>'
As the name suggests, it's shifting the bits to the right or left. An easy way to remember which symbol does which shift, look
at them as arrows pointing in the direction the bits will shift. Less than sign will shift to the left and the greater than sign will
shift to the right.
To start with something simple, look at the binary representation of 1. Shifting it to the left by 2 will move all the bits over two
places, resulting in the number 4.
| 1 | 0 | 0 | 0 | 1 |
| 1 << 2 = 4 | ||||
| 4 | 0 | 1 | 0 | 0 |
| 8 | 1 | 0 | 0 | 0 |
| 8 >> 2 = 2 | ||||
| 2 | 0 | 0 | 1 | 0 |
Bit Masking
Bit masking is just as it sounds, masking the bits to only see the ones you want. A good example to consider is the mouse. For this example, I'll only use 4 bits to represent the buttons on a mouse. Think of each bit as a mouse button. The first bit being the left mouse button, the second bit being the right, third is the middle button, and say the fourth is some other mouse button if you so happen to have a fancier mouse than I.
Each bit represents one of two states, on or off, just like a button...a mouse button! If you have a value representing your mouse buttons, you can store the state of several buttons into a single variable.
Left mouse button clicked:
Right mouse button clicked:
Middle mouse button clicked:
Depending on if the returned value is either 1, 2, or 4, you can tell which button was clicked. What if the value was 3?
That means the first two bits are on and therefore both left and right mouse buttons were clicked. Perhaps we're only concerned
about the right mouse button and don't care about the others. We can use a bit mask to check for a single button and ignore the
rest.
Assume that 'v' represents our mouse data and has returned a value of 3.
v & 0010 = 2
| 3 | 0 | 0 | 1 | 1 |
| 2 | 0 | 0 | 1 | 0 |
| 2 | 0 | 0 | 1 | 0 |
The first set of binary represents 'v' and we can see which bits have been turned on. The next line of binary is our bit mask. We flip every bit on that we want to check for. The right mouse button is held in the second bit place and so that's what we want to check. The last line is the result after we do a bitwise AND between our value and mask. The result is anything other than 0 then we know that button was flipped on (the right mouse button was clicked).
You can do the same thing to check for multiple button clicks as well, simply change your mask to mimic what you're looking for. Or instead of masking, use the bitwise OR operator. Let's say M1 equals 1, M2 = 2, M3 = 4, M4 = 8. Each on represents a different mouse button. M1 | M2 would equal 3, representing that both buttons 1 and 2 were clicked. So your statement might look something like this: if v = M1 | M2 then both but only both buttons one and two are clicked.
Practical Example - Putting it all to use
In your typical 32-bit system, you have over 16.7 million possible colors that your computer can display. Where does that number come from? Well, the colors really only take up 24 bits (3 bytes), often leaving the 8 bits to hold an alpha level. Three primary colors, red, green, blue, each take up a single byte themselves. As each byte can contain 256 values, using all three colors together yields a possible 16.7 million colors, 2563 = 16,777,216.
Let's take a look at 4,294,606,631, which should appear orange in color. Colors used on the internet for websites are represented in hexadecimal. That particular color value in hex would appear as FFFA7F27. Without getting too far off track with hex, just know that every two characters represents a byte and that I'm only showing this in hex because I think it's easier to see 8 characters broken down than 32 characters. With 8 total characters, that gives us 4 bytes or 32 bits. In this case, they represent the byte values for the alpha, red, green, and blue color channels.
The first two characters are 'FF', which
in decimal form is 255. This is also the alpha channel and tells us that the color is completely solid and not transparent
at all. Red is 'FA', green is '7F', and blue is '27', in hexadcimal that is. Now let's take a look at those numbers in binary
form. Looking at the table below, we can see what the different color channels look like in binary.
|
|
||||||||||||||||
|
|
||||||||||||||||
If you put all those binary digits together (alpha, red, green, blue), you'll end up with the 4 byte value of:
11111111 11111010 01111111 00100111 = 4,294,606,631
Remember how we masked bits above in the mouse button example? Doing the same thing here, you can extract just the single
byte color value that you want.
Let's extract the green channel from our very large color value.
11111111 11111010 01111111 00100111 & 00000000 00000000 11111111 00000000 = 00000000 00000000 01111111 00000000
Take the color value, bitwise AND it with the mask, and you'll get a value of 32,512. But wait, we're not done yet.
Remember that each color component only uses a single byte and therefore it's real value can't be higher than 255. The
value we just retrieve comes from the 2nd byte of a 4 byte value, therefore the value of the different bits
is higher.
This is where the bit shifting comes into play. We're going to shift this byte over so that it becomes the first byte and
then it will have the proper value we seek. To shift over to the next lower byte, do a right shift of 8 bits:
32,512 >> 8 = 127
Creating the appropriate mask and shifting by the proper amount, you can use the same method to retrieve of the individual
color components. In the case of the blue value, no shifting is required because it already resides in the lowest byte. Red
would be shifted by 16 bits, and the alpha channel by 24 bits.
Another approach is to do the shifting first if you wanted, then you could use the same mask on each one.
C = 4,294,606,631
A = (C >> 24) & 255 = 255
R = (C >> 16) & 255 = 250
G = (C >> 8) & 255 = 127
B = (C >> 0) & 255 = 37
Remember, 255 looks like 11111111 in binary. Using the decimal form is just simpler to write. Hopefully, after seeing
how bitwise AND can do bit masking and using bit shifting to get smaller component values, you understand bitwise operations
better and how they play into fairly common tasks in terms of computer programming.