Working with individual bits doesn’t just give you a way to pack lots of true or false values into a small space. This episode will show you how to isolate bits so you can work with them individually or in groups. Isolating bits like this is called masking.
The first thing to learn are the AND and OR truth tables. These tables list the output for each possible input combination. It is possible to consider AND and OR operations with more than two inputs but they need at least two inputs and that’s what these tables show.
AND Truth Table
0 AND 0 => 0
0 AND 1 => 0
1 AND 0 => 0
1 AND 1 => 1
OR Truth Table
0 AND 0 => 0
0 AND 1 => 1
1 AND 0 => 1
1 AND 1 => 1
If you think of the first input in these tables as your mask value, then you can see how whenever the mask value is 0 for AND operations, then it doesn’t matter what the other input is. The output will always be 0. And whenever the mask value is 1 for AND operations, then the output matches the second input.
For OR operations, the output matches the second value whenever the first mask value is 0. And whenever the mask value is 1, then the output will always be 1.
In this episode, I explain how to clear the most significant bit in a byte by using a mask. We need to perform an AND operation to clear one or more bits. If we have the binary value:
1100 1010 and we want to convert this to:
0100 1010 by clearing the bit on the left, then we need this mask:
0111 1111
The mask value in hexadecimal is then 7f.
And if we want to set the most significant bit again, then we need a different mask because this time, we will need to perform an OR operation. So continuing with this binary value:
0100 1010 and we want to convert to:
1100 1010 by setting the bit on the left, then we need this mask:
1000 0000
the mask value in hexadecimal is then 80.
Listen to the full episode or you can read the full transcript below.
Transcript
The previous episode on hexadecimal showed you how you can divide an eight-bit byte in half and then use a single hexadecimal digit to represent each half. So instead of a binary value 10001000, you would break that into two values that are each 1000 which is 8. So the whole binary value 10001000 becomes 88 in hexadecimal.
What if you wanted to isolate part of this value so you could work with just a portion. Maybe you only want the lower four bits. In other words, you want to turn 88 into 08 by clearing out all the upper four bits. This will let you work with just one hexadecimal digit. How would you do this?
Before we get to the how though, let me explain why with another example. Normally, I try to find examples that are simpler than the original topic I’m trying to explain. This is an exception because I have a real example from some code that I wrote a while ago which I think captures a really good reason for why masking is needed.
Let’s say that you need to transmit 4 byte integer values where the bytes have to be sent one by one. Now if you know that most of your values are small, then that means that the upper bytes will mostly be zeros. What if you could just not send those bytes if you don’t need to? If a large value comes along that’s using the bits in the upper bytes, then you go ahead and send them. But for the most part, you expect them to just occupy empty space. Maybe you could just send the bytes that are being used.
You would need some way to mark how many bytes have been sent and on the receiving side, how many bytes were sent. One way to do this would be to use one bit from each byte as a signal. Let’s use the most significant bit in each byte. If this bit is zero, then that’s all. If this bit is one, then there’s at least one more byte following.
Think of it like this. You have a group of people that can carry small messages for you. You can sometimes fit your entire message with one delivery person. When this happens, then before you send your delivery person, you just let him know that he has the entire message. But if your message is too big for one person to carry, then you give whatever the first person can carry along with instructions for the recipient that more will be arriving soon. You just repeat this by giving each messenger whatever can be carried and if there’s more, then the delivery person knows to tell the recipient that more is on the way. The last delivery person tells the recipient that the message is now complete.
What’s all this have to do with bits and bytes? In the message example, you need to be able to isolate just the parts of the overall message to send with each messenger. When sending a variable number of bytes, we need to isolate just seven of the eight bits to send because one bit is needed to determine if more bytes will be following. There are times like this in programming when you need to work with partial bytes. You need to be able to isolate the bits you want and ignore the rest. This is called masking.
If you’ve ever painted a room, you know that it’s a good idea to place tape over the areas you don’t want painted. This is called masking tape and it does the same thing by allowing you to ignore certain areas.
Masking bits is a little more involved because you can’t just put some tape over individual bits. Here’s how it works.
If you want to clear a bit or in other words, make sure it’s zero regardless of its initial value, then you can perform what’s called a bitwise AND operation with zero. This is because zero AND zero is zero and also because zero AND one is zero. And if you want to clear multiple bits, then just make sure that they all get ANDed with zero.
What if you want to leave a bit value unchanged? Then you just AND it with one. If it was originally zero, then zero AND one is zero. If it was originally one, then one AND one is one.
Notice that we’re not adding values here. We’re ANDing them. There’s a similar topic about logical operations in the Q&A Friday episode from 2015-Dec-18. Bitwise operations are similar but a little different. When you perform a bitwise AND operation with two values, the only way for you to get a one as the result is if both input values are also one. Notice how the bitwise operations usually work in terms of ones and zeros while the logical operations tend to work with true and false.
To fully list out the combinations for two inputs, there are only four possibilities, so I can list those here:
◦ 0 AND 0 is 0
◦ 0 AND 1 is 0
◦ 1 AND 0 is 0
◦ 1 AND 1 is 1
◦ You’re output will be one only when all the inputs are one.
◦ Notice how whenever the first value is zero, the output will always be a zero. This makes sense because if the first value is zero, then it doesn’t matter what the second value is because as long as just one of the input values is zero, then the output will be zero.
◦ And notice how when the first value is one, then the output depends on the second value. If the second value is zero, then the output is zero. And if the second value is one, then the output is one.
◦ This is why you can make sure that a value gets set to zero by ANDing it with zero. You can also make sure to leave the value unchanged by ANDing it with one.
◦ This table will be in the show notes if you want to view it in text form.
I’ll explain another masking operation and bring this all back around to the examples of how to work with 7 out of 8 bits for the variable number of bytes being sent and how to work with 4 out of 8 bits so you can isolate a single hexadecimal digit right after this message from our sponsor.
( Message from Sponsor )
What if you want to make sure that a particular bit is set or in other words if the bit becomes one? You can do this with another type of bitwise operation called an OR operation. An OR operation will produce a one output as long as at least one input is one. For two inputs, there are again just four possible results so I’ll list them all here:
◦ 0 OR 0 is 0
◦ 0 OR 1 is 1
◦ 1 OR 0 is 1
◦ 1 OR 1 is 1
◦ This looks a lot like the previous example of a bitwise AND operation. The only difference is that we have a lot more outputs of one here. It’s backwards from the other example.
◦ Here, if you want a value to be unchanged, then you can OR it with zero.
◦ And if you want a value to be set to one, then you can OR it with one.
◦ This will also be in the show notes if you find that easier to read.
When we want to send just seven out of eight bits, the first step is to isolate those seven bits by leaving them unchanged and clearing out the eighth bit.
Both bitwise operations AND and OR can leave values unchanged. But only AND can guarantee a bit gets cleared. So we want a mask value that will cause the most significant bit to be cleared while leaving all the other bits unchanged. The bit we want to be cleared needs to match up with a zero bit in the mask while all the other bits we want unchanged need to match up with ones.
Our mask for this will be 0111 1111. Or in hexadecimal, that’s 7f. If we perform a bitwise AND operation between the least significant byte in a four byte integer with the value 7f, then this will clear out the bit we don’t want.
We can actually just perform a bitwise AND operation between the entire integer and the value 7f because 7f will get promoted to a full integer value of 00 00 00 7f. All those extra zeros will just help us clear out all the bits in the integer except for the 7 least significant bits we’re interested in.
Then the only remaining issue is how to set the eighth bit that we just cleared if our integer is larger than what will fit in 7 bits.
How high can we count with 7 bits? We can count from 0 up to 127 with 7 bits. So if our original integer is less than or equal to 127, then we’re done because the extra eight bit is already cleared and we can send this byte and the receiver will know that no more bytes are coming.
But if the original value is greater than 127, then we need to set the eighth bit without changing the first seven. That’s the job of a bitwise OR. In this case, we need a new mask value because we want the bit to be set to match up with a one while the bits to remain unchanged will match up with zeros. We want a one in the eighth bit and all zeros in the other bits. That will be 1000 0000 which in hexadecimal will be 80. So by ORing the byte that we just isolated with the value 80, we can set that signal bit so the receiver will know to expect more bytes.
Alright, this is great for just the first byte and remember that for values less than or equal to 127, that’s all we need. But for values greater than 127, we’ll need to calculate the next byte to send. I’ll show you how to do that in the next episode. It’s needs a new technique which means a new episode.
But before we end, what about isolating the lower four bits in a byte so you can work with just a single hexadecimal digit? We want to somehow turn the value 88 into 08. You now know that you need a bitwise AND operation to clear bits. So it’s just a matter of calculating what mask to use. We want to clear the upper four bits so they all need to match up with zeros in the mask. And we want to leave the lower four bits unchanged so they need to match up with ones. Remember to choose mask values based on whether you’ll be doing an AND operation or an OR operation. Our mask value in this case will be 0000 1111 which in hexadecimal is 0f.
This means that by ANDing the value 88 with 0f, you end up with the value 08.
Now that you know this pattern, you’ll be able to calculate any mask value. Just remember to first ask yourself if you want to clear certain bits or set certain bits. If you’re clearing bits, then you’ll be ANDing and if you’re setting bits, then you’ll be ORing. then just match up the appropriate zero or one with the bit positions you need to work with and there’s your mask.
Congratulation, you now have a piece of virtual tape that can be placed over bits.