Code along video
Learning objectives
In this code along, we meet the X-Toy instructions that operate on the individual bits of a 16-bit word: AND, XOR, left shift, and right shift. We will see that shifting a binary number is really multiplication or integer division by a power of two, and we will use a bit mask to compute the remainder of a division with a single AND.
Code along summary
Setup
We continue working in Visual X-TOY, the simulator that we met in the previous lesson, “Meet X-Toy”. There is nothing new to install. Each program below reads its inputs from address FF, so before running a program, add the input words to the Stdin panel on the right side of Visual X-TOY (or enter them when prompted), just as we did when we added two numbers. If you would like to follow along with your own files, create the following five files as we go: bitwise_and.toy, bitwise_xor.toy, shifts.toy, remainder_shifts.toy, and remainder_mask.toy.
Bitwise AND
So far, X-Toy has given us addition and subtraction. Which other operations should a machine with only 16 built-in instructions have? If we think of the computer as a collection of lights that are on (1) or off (0), then we want operations that are easy to wire up as an electrical engineer and that are lightning fast. Addition and subtraction qualify. The next operation might not look useful at first, but we will see an application of it before the end of this lesson.
Programming is inextricable from logic, and by now we are comfortable with taking the “and” of two statements: in Python, the block under if x and y: is entered only if both x and y evaluate to True. If we think of a 1 as true (a transistor in its on state) and a 0 as false, then we can apply the same idea to two binary numbers a and b, one position at a time. The bitwise AND of a and b is the binary number c whose i-th bit is 1 if and only if the i-th bits of both a and b are 1. In the slide’s notation, the instruction is AND Rd, Rs, Rt, which sets register Rd to Rs AND Rt.
| 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| b | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| c = a AND b | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
222E, b = 2868, and c = 2028.Wherever we see two zeros, the result is 0 because false and false is false. Wherever we see a 1 and a 0, the result is also 0, since an AND is true only when both statements are true. Only the columns containing two ones produce a 1.
In X-Toy, AND is opcode 3, so the word 3312 means “set R[3] to R[1] AND R[2]” (Visual X-TOY writes this as R[3] <- R[1] & R[2]). The following program reads two words, ANDs them, and prints the result. Save it as bitwise_and.toy.
10: 81FF read R[1] 11: 82FF read R[2] 12: 3312 R[3] <- R[1] & R[2] 13: 93FF write R[3] 14: 0000 halt
If we place 222E and 2868 on standard input and run the program, it prints the value of c from the table above, and the registers hold R[1] = 222E, R[2] = 2868, and R[3] = 2028.
2028
OR versus XOR
If we have an AND, then we should have an OR. Human languages use the word “or” in two different ways, and most of them do not have separate words for the two meanings. The “or” that we have used in Python is inclusive: x or y evaluates to True if either statement is true, including when both are true. But if someone asks whether you want to go to the beach or the mountains for your vacation, they mean that you can choose one of the two, but not both. This second meaning is the exclusive or, or XOR.
The bitwise XOR of a and b is the binary number c whose i-th bit is 1 if the i-th bit of either a or b (but not both!) is 1. The slide’s instruction is XOR Rd, Rs, Rt, which sets Rd to Rs XOR Rt. X-Toy’s instruction set includes XOR as opcode 4; it has no instruction for the inclusive OR.
| 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| b | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| c = a XOR b | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
0A46.Another way of thinking about XOR is that we flip the light on in c precisely when the lights in a and b are not equal. Two zeros are equal, so the light stays off; two ones are equal, so the light stays off; a 0 and a 1 in either order are unequal, so the light turns on. XOR is therefore a bitwise test for inequality, which is a big part of why it is worth building into the machine as a single fast operation.
To try XOR in Visual X-TOY, we only need to change one word of our previous program: the opcode 3 becomes 4. Save the following program as bitwise_xor.toy.
10: 81FF read R[1] 11: 82FF read R[2] 12: 4312 R[3] <- R[1] ^ R[2] 13: 93FF write R[3] 14: 0000 halt
With 222E and 2868 on standard input, the program prints 0A46, matching the table, and R[3] holds 0A46 when the machine halts.
0A46
Left shift and right shift
The last operation that we will introduce here is really two operations in one, and it might strike you as odd that it earns a spot among only 16 built-in instructions: shifting the digits of a number. We allow ourselves to shift in either direction.
The instruction LSHIFT Rd, Rs, Rt sets register Rd to Rs shifted to the left by Rt digits. If we shift the number below to the left by two digits, then the two zeros at the front fall off the left side and disappear, every other digit slides two positions to the left, and two zeros come in at the right. In general, shifting left by k digits fills in k zeros on the right side.
| 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Rs | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
Rd (left shift by 2) | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
222C left by two digits produces 88B0. The two leftmost digits fall off and disappear, and two zeros come in at the right.We can also shift the other way. The instruction RSHIFT Rd, Rs, Rt sets Rd to Rs shifted to the right by Rt digits. Shifting by two positions, everybody moves over two places to the right, and the final two digits fall off the end. It is like musical chairs: those two digits have nowhere to go.
| 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Rs | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
Rd (right shift by 2) | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
222C right by two digits produces 088B. The two rightmost digits fall off and disappear, and zeros come in at the left.In X-Toy, left shift is opcode 5 and right shift is opcode 6. The following program, which we save as shifts.toy, reads a word into R[1], loads the shift amount 2 into R[2], and then stores the left shift in R[3] and the right shift in R[4] before printing both.
10: 81FF read R[1] 11: 7202 R[2] <- 0002 12: 5312 R[3] <- R[1] << R[2] 13: 6412 R[4] <- R[1] >> R[2] 14: 93FF write R[3] 15: 94FF write R[4] 16: 0000 halt
With 222C on standard input, the program prints the two words from the tables above, and when it halts we can read R[1] = 222C, R[2] = 0002, R[3] = 88B0, and R[4] = 088B off the simulator.
88B0 088B
| Opcode | Slide notation | Example word | Visual X-TOY pseudocode |
|---|---|---|---|
3 | AND Rd, Rs, Rt | 3312 | R[3] <- R[1] & R[2] |
4 | XOR Rd, Rs, Rt | 4312 | R[3] <- R[1] ^ R[2] |
5 | LSHIFT Rd, Rs, Rt | 5312 | R[3] <- R[1] << R[2] |
6 | RSHIFT Rd, Rs, Rt | 6412 | R[4] <- R[1] >> R[2] |
What shifts really do
STOP: What does it mean arithmetically to shift a binary number left by k digits? What about shifting it right by k digits?
The left shift is the easier direction to see. Pretend for a moment that the numbers in our left shift table are not binary numbers but base 10 numbers that happen to contain a lot of ones and zeros. Going from the first number to the second, all we did was add two zeros to the end, so we multiplied by 100. The only thing that changes in binary is the base. Because our base is 2, adding one zero corresponds to multiplication by 2, adding two zeros corresponds to multiplication by 4, and adding k zeros corresponds to multiplication by 2k. So an operation that looks like it is just moving bits around is really a multiplication: our left shift by 2 was a multiplication by 4.
The right shift is a little trickier. In base 10, chopping the last two digits off a number divides it by 100, except that one of those digits could be something other than zero, in which case we have a remainder, and that remainder disappears. In base 2, chopping off two digits performs a division by 4, and chopping off k digits divides by 2k. This is a special type of division that we have worked with for a long time: integer division, where we ignore the remainder.
| Operation | Arithmetic meaning | Python equivalent |
|---|---|---|
| Left shift by k digits | Multiplication by 2k | x * 2**k |
| Right shift by k digits | Integer division by 2k (remainder discarded) | x // 2**k |
We can check this with shifts.toy. If we instead place 0013 (that is, 19) on standard input, then the program prints 004C, which is 76 = 19 · 4, and 0004, which is 19 // 4 (the remainder of 3 has fallen off the end).
004C 0004
So we have very fast operations that can do a little bit of logic for us and that can also perform certain multiplications. If we want to multiply by 3, or 17, or 42, which are not powers of two, then we will need to be more clever. You might start thinking about how we could do that.
Capturing a remainder with a bit mask
A right shift performs an integer division in which the remainder disappears. But throughout this course, we have often cared about the remainder of an integer division. How could we capture it?
| 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
A22C in hexadecimal).Exercise: Consider the 16-digit binary number a shown above. What is the remainder when we divide a by 8 (that is,a % 8)? Then, how could we computea % 8in general using left shifts and right shifts?
We don’t need to convert a to base 10 to answer the first question. If this were a base 10 number and we divided it by 1000, then the remainder would be its last three digits. Nothing is different here except that we have changed the base: 8 = 23, so the remainder of a divided by 8 is hiding in its last three digits, 100. These digits occupy the ones place, the twos place, and the fours place, so a % 8 is 4.
To compute this remainder with shifts, we should not right shift a by three digits, since that would divide by 8 and lose exactly the digits 100 that we want to keep. Instead, we want to get rid of everything else. We first left shift a by 13 digits, which pushes the first 13 digits off the left end, and then we right shift everything back by 13 digits, leaving a bunch of zeros followed by 100.
| 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| left shift 13 digits | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| right shift 13 digits (slide) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
a % 8 as shown on the slide.Here is that idea as an X-Toy program, which we save as remainder_shifts.toy. It loads the shift amount 13 (000D) into R[2], shifts left, and then shifts the result back to the right.
10: 81FF read R[1] 11: 720D R[2] <- 000D 12: 5312 R[3] <- R[1] << R[2] 13: 6332 R[3] <- R[3] >> R[2] 14: 93FF write R[3] 15: 0000 halt
With 0013 (19) on standard input, the program prints 0003, and 19 % 8 is indeed 3. But if we run it on our number a = A22C, something surprising happens: X-Toy prints FFFC instead of 0004.
FFFC
Note: Our slides say that zeros come in at the left during a right shift, and that is true whenever the leftmost bit of the number being shifted is 0, as in all of our shift examples except this one. When the leftmost bit is 1, X-Toy’s right shift copies that 1 into the vacated positions instead. After the left shift by 13, the leftmost bit is the 1 from100, so ones flood in from the left and we obtainFFFC. We will see why X-Toy behaves this way when we discuss negative numbers in the next lesson. For now, it gives us one more reason to prefer the approach that comes next.
STOP: The two-shift approach requires two operations. Do you see a faster way to computea % 8?
People have built careers, going back decades, on finding faster ways to perform a task with simple operations. In this case, we can compute a % 8 with a single AND of a with a special number called a bit mask, a number that doesn’t represent anything we care about for longer than one operation. Our bit mask consists of 13 zeros followed by three ones.
| 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| mask | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
a AND mask = a % 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
0007 switches off the first 13 bits and keeps the last three bits of a, producing 0004.When we AND a digit with 1, we keep that digit as it was: if it was on, it stays on, and if it was off, it stays off. So if we AND a number with all ones, we get the number back. When we AND with a mask that starts with 13 zeros, the first 13 lights are automatically switched off, because we are ANDing them with false values, and the final three digits are whatever they were in a. Save the following program as remainder_mask.toy.
10: 81FF read R[1] 11: 7207 R[2] <- 0007 12: 3312 R[3] <- R[1] & R[2] 13: 93FF write R[3] 14: 0000 halt
With A22C on standard input, the program prints 0004, and when it halts, R[1] = A22C, R[2] = 0007, and R[3] = 0004. Simple, but cool: even though AND probably didn’t seem relevant to arithmetic when we first met it, a single AND with the right mask gives us the remainder after dividing by any power of two.
0004
Looking ahead
Every number that we have worked with in X-Toy so far has been nonnegative. In the next lesson, we will ask how a machine whose words are just 16 lights can represent negative numbers, which will also explain why X-Toy’s right shift copied ones into our remainder computation.