Click here to download the episode worksheet.
Welcome to the Geek Author series on Computer Organization and Design Fundamentals. I’m David Tarnoff, and in this series, we are working our way through the topics of Computer Organization, Computer Architecture, Digital Design, and Embedded System Design. If you’re interested in the inner workings of a computer, then you’re in the right place. The only background you’ll need for this series is an understanding of integer math, and if possible, a little experience with a programming language such as Java. And one more thing. This episode has direct consequences for our code. You can find coding examples on the episode worksheet, a link to which can be found on the transcript page at intermation.com.
This episode is all about clearing bits. Why would we want to clear a bit? In Episode 7.01 – Introduction to Bitwise Operations, we presented an example of creating a random even number by first generating a random number, then clearing the least significant bit. Let’s turn this example around, and see if we can tell whether a number is odd or even. In other words, what is its parity? How does clearing bits help us here? Well, if we can clear all the bits of an integer except for the least significant bit, then that last bit can act like a true or false flag identifying the number as odd or even.
Recall from Episode 7.01 that bitwise operations allow us to clear, set, or invert individual bits of an integer using a logic operation and a bit mask. We clear bits to zero using the bitwise-AND operation, set bits to one using the bitwise-OR, and invert bits using either the bitwise-inverse or bitwise-exclusive-OR. For three of these operations, the bitwise-AND, the bitwise-OR, and the bitwise-exclusive-OR, a bit mask is required. A bit mask is a binary value that has the same number of bits as the binary value we wish to modify with its pattern of ones and zeros set to define which bits of the original value are to be changed and which bits are to be left alone.
Getting back to our example where we wish to determine the parity of an integer, there are a couple of ways we can use software to determine whether an integer is odd or even without using bitwise operations. Remember that when we divide integers in software, any remainder generated is discarded. If we divide an odd integer by two, a remainder of one is discarded. Multiply the quotient that resulted from the division by two, and we get a value that is one less than the original value. Apply the same process to an even number, and the result equals the original value. So, the conditional statement if(((value / 2) * 2) != value) evaluates to true when the integer stored in value is odd. The same thing can be done using bit shifts. The conditional statement if(((value >> 1) << 1) != value) evaluates to true when the integer stored in value is odd.
Since it’s the remainder after a division by two that identifies an integer’s parity, we could also use the remainder or modulus operation. Most programming languages use the percent sign to perform the modulus operation. A line of code like value % 5 would return the integer remainder of value divided by 5. To determine the parity of an integer, we want to get the remainder after a division by 2. The conditional statement if((value % 2) == 1) evaluates to true when the integer stored in value is odd.
Bitwise operations can perform this operation quicker. If we get a one after clearing all of the bits of an integer except for the least significant bit, then we had an odd number to begin with. If the result equals zero, the only other possibility, then the integer we started with was even.
The bitwise-AND clears specific bits while leaving the other bits unchanged. The mask that is used will have ones in the bit positions that are to be left alone and zeros are in the bit positions that need to be cleared. It is the perfect operation for distinguishing odd and even numbers where we want to see how the least significant bit is set and ignore the remaining bits. The mask we want to use will have a one in the least significant bit position and zeros in all of the other positions.
How does it work? Well remember from Episode 7.01 that a bitwise operation performs a logical operation, either AND, OR, or exclusive-OR, on pairs of bits that share the same bit position within two binary numbers. The bits are paired up by matching their bit position, performing the logical operation, and then placing the outcome in the corresponding bit position of the result. In the case of the AND, if either of the bits that share a bit position equals zero, the result in that position is going to be zero. The only way to have a one in a specific position of the result is to have ones in the same bit position of both the original value and the bit mask. In other words, the positions where the bit mask contains ones are the positions where ones will be passed from the original value to the result.
Let’s do a couple of examples of checking for parity with just eight bits. The decimal integer 43 in eight-bit binary is 00101011. If we perform a bitwise-AND of this number with the binary mask 00000001, the first seven bits of the result from left to right are, 0 AND 0 is 0, 0 AND 0 is 0, 1 AND 0 is 0, 0 AND 0 is 0, 1 AND 0 is 0, 0 AND 0 is 0, and 1 AND 0 is 0. Only the least significant bit of the result is one, where both the decimal integer 43 and the bit mask have ones. In other words, 1 AND 1 is 1.
Doing this same operation with an even integer such as 84 would give us a different result. Eighty-four in eight-bit binary is 01010100. Notice that the last bit is zero identifying it as an even number. When we perform a bitwise-AND of 01010100 with the bit mask one, we get from left to right 0 AND 0 is 0, 1 AND 0 is 0, 0 AND 0 is 0, 1 AND 0 is 0, 0 AND 0 is 0, 1 AND 0 is 0, 0 AND 0 is 0, and finally, 0 AND 1 is 0. The final result equals zero, which means the least significant bit of the original integer was zero, which means 84 is even.
The bitwise-AND of any integer with the binary mask one will equal one if the integer was odd and zero if the integer was even. Since bitwise operations are one of the fastest operations that can be performed on a processor, it is the preferred method. In fact, on a typical processor, the bitwise-AND can be twice as fast as using a right shift followed by a left shift.
There are many other reasons to clear specific bits of an integer. For example, assume we want to separate the nibbles of an integer into separate variables. We might want to do this to create a function that prints these nibbles as different ASCII characters in order to display a value in hexadecimal.
To isolate the least significant nibble, we should clear all but the lower four bits by performing a bitwise-AND with the binary bit mask 00001111, which equals a hexadecimal 0xf. To get the next least significant nibble, shift the original value right by four bit positions, then perform another bitwise-AND with the hexadecimal 0xf. Subsequent nibbles can be deciphered using additional right shifts by four and bitwise-ANDs with hexadecimal 0xf.
As another example, let’s discuss the Internet Protocol version 4, or IPv4, method of addressing. An IPv4 address is a 32-bit number. It is usually displayed as four bytes or octets separated from one another with periods or “dots”. The address is divided into two parts: a subnet id and a host id. All of the computers that are connected to the same subnet will have the same subnet id. Each computer on the same subnet has a unique host id. The host id allows the computer to be identified among all of the computers on the subnet.
To determine which bits represent the subnet id and which represent the host id, a subnet mask is used. Let’s take for example the subnet mask 255.255.252.0. Converting each of these bytes of the mask to binary gives us 11111111.11111111.11111100.00000000. The bits that identify the subnet id of an IP address correspond to the positions with ones in the subnet mask. The positions with zeros in the subnet mask identify the host id. In the case of this subnet mask, the first 22 bits identify the subnet and the last ten bits identify the host id. If we take a sample IPv4 address, say 151.142.91.235, the first 22 bits of this IPv4 address identify it as a member of the subnet 151.142.88.0, or in binary, 10010111.10001110.01011000.00000000.
So how can we determine if another IPv4 address is a member of this subnet? Well, if we could clear the bits of the host id, then the result should equal 151.142.88.0. This sounds like the bitwise-AND. If we perform a bitwise-AND on an IPv4 address using the subnet mask 255.255.252.0, then the result must be 151.142.88.0 after the host id is cleared if it is a member of our subnet. Let’s do this for one address inside the subnet, 151.142.89.117, and one address outside the subnet, 151.142.85.47. First, we convert each address to its 32-bit binary value, and then clear the host id bits by performing a bitwise-AND with the subnet mask 255.255.252.0. First, 151.142.89.117 equals in binary 10010111.10001110.01011001.01110101. After the bitwise-AND clears the least significant ten bits, the binary result is 10010111.10001110.01011000.00000000, which equals 151.142.88.0. Since this equals the subnet address, 151.142.89.117 is contained in our subnet. The second address, 151.142.85.47, equals 10010111.10001110.01010101.00101111 in binary. After the bitwise-AND clears the least significant ten bits, the binary result is 10010111.10001110.01010100.00000000, which equals 151.142.84.0. Since this does not equal our subnet address, 151.142.85.47 is not contained in our subnet.
Note that we can also use the bitwise-AND to clear bits that we want to set to a new value. Remember our color example from Episode 7.01? In it we discussed modifying a single byte representing red, green, or blue within a twenty-four bit color. To modify blue, for example, we want to change the least significant eight bits of the color, bits seven down to zero. To do this, we first use the bitwise-AND to clear those bits by AND-ing it with a bit mask equal to a hexadecimal value 0xffff00. Once those bits are clear, we can set the bits to our new color. Setting bits is what we are discussing in our episode after the next episode. In our next episode, we’re going to dig deeper into how bitwise operations are done in software.
For episode transcripts, worksheets, links, or other podcast notes, please visit us at intermation.com where you will also find links to our Instagram, Twitter, Facebook, and Pinterest pages. Until the next episode, remember that while the scope of what makes a computer is immense, it’s all just ones and zeros.