Chapter 5 - Arithmetic and Logic

In this chapter we will be using only one program, which will enable us to observe the various arithmetic and logical operations of the 1802 computer. Before we get into the details of Program 5.1 and these operations, let's quickly review grammar school arithmetic (adding and subtracting) and some of the logical operations a computer can do.

When you were in grammar school, you added two numbers (say 43 + 25) one digit at a time, starting from the right: 3+5=8; 4+2=6; result = 68. Now you know that 3+5=8, but when you were first learning how to add, you had to memorize a big addition table. Exactly the same kind of process goes on when your computer adds, except that its table is for binary numbers, not decimal, and looks like this:

 + | 0  1 
 0 | 0  1
 1 | 1 10

Your ELF II, however, does not let you look at the binary numbers directly, so it helps to imagine that the addition table that the computer has memorized is actually for hexadecimal, not binary. It turns out to have the same results. I will not reproduce the hex addition table here.

Subtraction works by the same principles as addition, as you will recall from way back when. But if you try to subtract a larger number from a smaller number, things get a little tricky. I think the best way to introduce you to most of these problems is by seeing what the computer actually does.

If you want your computer to multiply or divide, you are almost out of luck. The 1802 and most other 8 bit microprocessors can only multiply or divide by two. The operation is called a shift. If you shift a number left by one bit position, you have doubled it (i.e. multiplied it by 2). Similarly, shifting a number right one bit position divides the number by two. More on this later.

There are three logical operations which most microprocessors can do with a single instruction. They operate on the individual bits (remember, one bit is a single true-false answer) in the computer words (or bytes). I will give you the tables now, so you can compare these operations to the instructions later.

AND| 0  1 
 0 | 0  0
 1 | 0  1

OR | 0  1 
 0 | 0  1
 1 | 1  1

XOR| 0  1 
 0 | 0  1
 0 | 1  0

Now key in Program 5.1. As you can see, it requires three inputs; an opcode, which is executed at location 0029, and two data bytes, one stored in location 0060 (via R6) and one stored in location 0061 (same address register, but incremented). It does its operation, then puts the result back into location 0060 to display it. If the result is zero, the program also turns Q on. So that you will know which input is expected, the display will show "00" when it is waiting for an opcode, "01" when waiting for the first operand, and "02" when waiting for the second operand. After it performs the operation, the result also becomes the first operand of the next time through the loop, so you only have to key in the second operand for each successive time through. Of course, any time you want to put a new opcode or first operand, you can reset the computer and run the program again. Look over the program and be sure you understand it. Notice that it contains only instructions you have met in Chapters 3 and 4.

        ..  PROGRAM 5.1 -- TEST ALU OPS
        ..
0000 90         GHI 0     .. SET UP R6
0001 B6         PHI 6
0002 F829       LDI DOIT  .. FOR INPUT OF OPCODE
0004 A6         PLO 6
0005 E0         SEX 0     .. (X=0 ALREADY)
0006 6400       OUT 4,00  .. ANNOUNCE US READY
0008 E6         SEX 6     .. NOW X=6
0009 3F09       BN4 *     .. WAIT FOR IT
000B 6C         INP 4     .. OK, GET IT
000C 64         OUT 4     .. AND ECHO TO DISPLAY
000D 370D       B4 *      .. WAIT FOR RELEASE
000F F860       LDI #60   .. NOW GET READY FOR
0011 A6         PLO 6     .. FIRST OPERAND
0012 E0         SEX 0     .. SAY SO
0013 6401       OUT 4,01
0015 3F15       BN4 *
0017 E6         SEX 6     .. TAKE IT IN AND ECHO
0018 6C         INP 4     .. (TO 0060)
0019 64         OUT 4     .. (ALSO INCREMENT R6)
001A 371A       B4 *
001C E0         SEX 0     .. DITTO SECOND OPERAND
001D 6402       OUT 4,02
001F E6         SEX 6
0020 3F20 LOOP: BN4 *     .. WAIT FOR IT
0022 6C         INP 4     .. GET IT (NOTE: X=6)
0023 64         OUT 4     .. ECHO IT
0024 3724       B4 *      .. WAIT FOR RELEASE
0026 26         DEC 6     .. BACK UP R6 TO 0060
0027 26         DEC 6
0028 46         LDA 6     .. GET 1ST OPERAND TO D
0029 C4   DOIT: NOP       .. DO OPERATION
002A C4         NOP       .. (SPARE)
002B 26         DEC 6     .. BACK TO 0060
002C 56         STR 6     .. OUTPUT RESULT
002D 64         OUT 4     .. (X=6 STILL)
002E 7A         REQ       .. TURN OFF Q
002F CA0020     LBNZ LOOP .. THEN IF ZERO,
0032 7B         SEQ       .. TURN IT ON AGAIN
0033 3020       BR LOOP   .. REPEAT IN ANY CASE

When you first run this program, try entering "C4", "11", "22", then "33". Notice that after the first time through, the only display is the "11" alternating with your input. If you run it again, entering "00" instead of "11", you will notice that Q comes on and stays on. The program loads the first operand into D, executes the NOP you keyed in, then displays the contents of D (which has not changed).

Restart the program, but this time enter an opcode of "F0" (LDX). Now what data is displayed? Be sure you understand what you are seeing for the NOP and the LDX entered into this program before proceeding any further. It is essential to have a good feeling for the prior contents of D (the accumulator) and the byte in memory that the address register pointed to by X points to; the NOP shows you the former, LDX shows you the latter. The ALU (Arithmetic and Logical Unit) instructions combine these two data bytes to give some result; if you do not know what the operation starts with, you will not know how it got its answer. Notice however, that the first time through they are your inputs; after that they are the previously displayed result and the next input, respectively.

Now you should be ready to try a new opcode. Start with "F1", followed by "33", then "55". What was the result? Does repeating the operation with the same second operand (i.e. push the "I" key again) change the result? Try giving it "01". Can you figure out how to get a result of "FF"? Can you figure out which operation this opcode does (ADD, AND, OR, or XOR)? (Hint: try giving it 00,00; 00,01; 01,00; and 01,01 and then compare the results to the four tables I gave you).

Try the same experiments with the opcode "F2". Can you figure out how to get a result of "FF"? Have you figured out which operation this is?

There is one more logical operation you have not yet tested. Try opcode "F3". Notice that repeated operations with the same datum in the second operand is not the same as for AND and OR. Do you see a pattern?

It might help you to understand how these instructions are used if you consider them in the following way:

AND forces to zero those bits in the accumulator which are zeros in the second operand.

OR forces to one those bits in the accumulator which are ones in the second operand.

XOR complements (sets zeros to ones, ones to zeros) those bits in the accumulator which correspond to ones in the second operand, leaving the other bits in the accumulator unchanged.

Also, XOR forces to zero those bits in the accumulator which match the corresponding bits of the second operand, and forces to one those bits which do not match.

We have met before (in the branches and the I/O instructions) a family of opcodes with "positive" and "negative" versions, distinguished by a single bit. The ALU opcodes are something like them, but the bit distinguishes the Immediate addressing mode (two byte instruction, with the operand being the second byte) from the "R(X)" or register indirect addressing mode (the datum is in memory, an address register points to it; in the 1802 ALU operations that address register is selected by X). Consider the difference between LDX (F0) and LDI (F8). Try LDI in Program 5.1. What datum is displayed as a result? Where in memory did it come from? (Hint: look at "the second byte of the instruction"). When you have a good feeling for the difference, you are ready to try "F9". Does the bit pattern of the opcode give you a clue at to what to expect? Was your guess right?

Try also "FA" and "FB".

Now you are ready to try the opcode "F4". For the first two operands, use something like "12" and "34". Obviously the result is the sum of these. Then enter a larger number like "58". Is the result what you expected? Remember your computer adds in binary (or hexadecimal), not the familiar decimal. Look at the sum in binary:

 01000110       46
+01011000      +58
 10011110       9E

Notice that 6+8 (which is 0110 + 1000) is 14, but 14 decimal is 1110 binary, which is E in hexadecimal. Do you understand why 4+5=9? Notice here that the second bit sum from the left is 1+1, which our table tells us is 10 (in binary). So the sum is 0 with a carry into the next digit to the left. Before you enter it, try to anticipate what adding "27" will result in. Start your paper sum with the rightmost bit, which is 0+1=1. The next bit sum is 1+1; what digit do you write down? What carry? The third digit is trickier: 1+1+carry=? Our addition table does not show what to do with three ones, but your recollection from grammar school should remind you that 1+1+1=3 which is 11 in binary. In other words, write 1, carry 1. Finish the sum, then try entering the number. Did the computer get the same result you did? If not, do you know what you did wrong? (Notice that I assume the computer's answer is the correct one. You can depend on the fact that any mistakes are yours, not the computer's. Computers these days, and your ELF II in particular, are more reliable than the cars we depend on every day.)

How much do you think you need to add to hex C5 to get FF? You can figure this out by looking for results of one in the addition table; notice that this happens for 0+1 and 1+0, so if the first operand has a zero, add one; if it has a one, add zero. Do you believe that C5+3A=FF? Try it. Do you think you can guess what FF+01 is? Try it. What happened to the carry out of the left bit of the sum? We will come back to that carry later. For now let us assume it vanishes (which is all you can see anyway).

If you add 01+02 you get 03, which is reasonable since 1+2=3. We think of subtracting A-B as "the number which added to B results in A." In other words, 1+2=3 is the same as 3-2=1. What number do you add to 1 to get 0? In high school algebra we called these "negative numbers": 1+(-1)=0. Now you already know what your computer will add to 01 to get 00. Obviously, hex FF is equal to -1. It is a strange sort of mathematics where 255=(-1). Can you guess what is -2? Does it seem obvious that -2 must be one less than -1? Try adding FE+02. Notice also that (-1)+(-1) = FF+FF = FE. Aside from the peculiarity that -2=254, negative numbers seem to do all the things we want them to. What is -4 (try adding -2 to itself)? Or -8? Can you figure out -9?

Negative numbers are simply the positive numbers subtracted from 256, which we observe to be indistinguishable from zero. You saw how to decide how much to add to a number to get hex FF; you add a number with each bit complemented (replace ones with zeros, zeros with ones). If A+B=-1, then A+(B+1)=0. Given A, you know how to find B; add one to that and you have computed -A. Let's try an example: What is the negative of (hex) 64?

 01100100       64
 10011011       complement
       +1
 10011100       -64 = 9C

Add 64 and 9C on your computer to prove that this is correct. Try a few other examples. A little later, when we let the computer subtract, you will see that it does it the same way we did.

I slipped you a ringer in the above description of ADD. The last sentence describes something you cannot see. Let's remedy that situation. At the end of Chapter 3, I mentioned that there was a set of conditional branches and skips that tested the DF register, but we could not see how they worked yet. Now you can. Change the opcode in location 002F of Program 5.1 from CA to CB. Then run it, giving it the ADD opcode with operands "11" and "22". Notice that Q stays off. Keep adding 22, and watch Q as the results go up. Notice what happens when you add FF+22=21. You see, there really is a carry out of the left bit of the sum. When that carry is one, the DF register is set to one; when the carry is zero (that is, there is no carry), DF is set to zero.

Do some addition in which the carry is zero, then restart the program so you can try another opcode, such as LDX, OR, AND, or XOR. Does the DF ever get set (as evidenced by Q coming on)? Now do an addition which sets DF to one, and repeat the experiment. Why does Q come on this time? Does this convince you that none of the other instructions we have met so far affect DF? Notice that not even Reset has any effect on it. To get a feel for the conditionals which test DF, change the opcode in 002F to C3 and run a few more sums through it. Try the short branch version by putting a NOP in 002F and a 33 in 0030. Try 3B. Can you think of how to change 002F-0031 to demonstrate the skip version of this test? (Hint: See what happens when you put LSZ in 002F and BR in 0030.)

Be sure Program 5.1 is correctly modified to reflect the status of DF on Q (for example, CF in 002F and 30 in 0030). There are three other opcodes in the 1802 which do addition. Let's explore them a little.

Try the opcode FC. What does it do? Can you figure out why it ignores the second operand you are entering? What does it use instead? How does that compare with the difference between LDX and LDI? By trying different first operands, convince yourself that the operation is the same, only that the second operand is the C4 in location 002A. You could even try modifying that byte to verify this, but be sure to put the NOP back afterwards.

The next one is a little more tricky. Do some addition which leaves DF=0, then enter the opcode "74" with small operands such as "11" and "22". Convince yourself that it still adds the same as ADD. Continue adding 22 until you get to the sum FF+22=21+carry. What result would you expect from the next addition if it were ADD instruction (F4)? If you are sure that 21+22=43, press "I" again and see if you know why you do not see 43. Try various other numbers. Do you see any relationship between the previous value of DF (as seen in Q) and the way this instruction adds? See if you can convince yourself that this instruction adds the two operands plus the value of DF (either 0 or 1). Try the immediate version of the same opcode (hex 7C). Do you understand it?

When I talked about negative numbers, I carefully introduced them before you knew about DF. As it turns out, DF is a little confusing when you think of your numbers as positive and negative. For example, if you add 3+5=8, the carry out is 0. If you add (-3)+(-5) = -8, the carry out is one. That does not mean the result is too big for your eight bits, only that there was a carry out. Well, it tells you a little more: (-3)+5=2 produces a carry=1; 3+(-5)=(-2) has a carry=0. If you know you are adding a positive and a negative number, the sum will have a carry out of zero if the result is negative. So what? That's not very helpful, yet.

We would like the computer to compute negative numbers for us, so we can do subtraction. A-B = A+(-B), so if we want to subtract some number from another, we need only find its negative and add. Remember the XOR? We can use it to find the negative of the number in the accumulator, by complementing every bit, after which it is easy to add one. Do you believe Program 5.2 will find the negative of whatever is in D? By then adding, this does an effective subtraction.

        ..  PROGRAM 5.2 -- SUBTRACT D FROM MEMORY
        ..
                XRI #FF   .. COMPLEMENT D
                ADI 1     .. ADD ONE
                ADD       .. ADD MEMORY (=SUBTRACT)

I did not include the object code for this program because I don't think you actually need to see it run. Especially because there is a single instruction in the 1802 which does the work of all three of these. Still using Program 5.1 (modified to reflect DF on Q as before), key in the opcode F5 with operands "01" and "03". What is 3-1? What does the computer say? Suppose you subtract the result from 3 again (hit "I" again); what do you get? Try subtracting 1-3. Notice DF; when subtracting positive numbers, DF=1 if the difference is also positive, and DF=0 if the difference is negative. If you consider all numbers positive (in the range 0-255) then 253-3=250 is positive, so DF=1; 237-241=(-4) is negative, so DF=0. Remember, it is only your opinion that matters in deciding whether a number is positive or negative. The number 237 equally well answers the questions "What is the 237th positive number?" and "What is the 19th negative number (as represented by counting down from 256)?" The computer does not know which of these two questions is answered by a hex ED.

As you might expect, the 1802 also has a subtract immediate. In Program 5.1 the immediate byte is hex C4. Try the opcode FD with various first operand values (such as C4,00 or FF,01, etc.). Notice that the second operand has no effect (Why?). In each case you should be satisfied that the first operand is subtracted from C4. Notice also that if you subtract the result from C4 again (by pressing "I" again), you get back your original datum. Notice the carry out each time (in Q).

As you probably guessed by now, any instruction which modifies DF has a version which adds the previous value of DF into the result. The purpose of this is so that you can do arithmetic on larger numbers than will fit in one byte. For example, to add two 16-bit numbers (say, one in RA that we'll call OP1, the other in memory pointed to by R8 which we'll call OP2), something like Program 5.3 would be used:

        ..  PROGRAM 5.3 -- ADD TWO 16-BIT NUMBERS
        ..
                SEX 8     .. R8 POINTS TO OP2
                GLO A     .. GET LOW BYTE OF OP1
                ADD       .. ADD LOW BYTE OF OP2
                PLO A     .. PUT SUM IN RA
                GHI A     .. GET HIGH BYTE OF OP1
                DEC 8     .. POINT TO OP2 
                ADC       .. ADD WITH CARRY
                PHI A     .. PUT RESULT IN RA

It should not be hard to imagine that this would also work for a subtract. In this case we are concerned about borrowing rather than carrying (remember your grammar school subtraction), but it turns out that the same mechanism works for both. Remember that subtraction consists of complementing the number to be subtracted, then adding one. Let's try a 16-bit example:

 0100000100110110    4136
-0001001010110100   -12B4

First we find the negative of hex 12B4. To do this, complement all the bits, then add 1:

 11101101  01001011    ED4B   complement of 12B4
                 +1      +1   add 1
 11101101  01001100    ED4C   is -12B4

Notice that I split the number into two bytes so you can see how the computer might compute it. You see, when the rightmost two bits were added, there was a carry into the next bit position to the left, but there was no carry out of the eighth bit across the byte boundary into the next byte (the ninth bit from the right). On the other hand, if I take the negative of hex 4000:

 01000000 00000000
 10111111 11111111
                +1
 11000000 00000000

Here the carry propagated; that is, each carry resulted in another carry, all the way across both bytes to the 14th bit; in particular the carry out of the low byte was 1, which had to be added into the high byte. Now if this 16-bit number is in one of the address registers and you instruct the computer to increment it, it will propagate the carry all the way across as it should. But the accumulator is only 8 bits, so the carry out of the low half is carried by DF into the high half.

Returning to our subtraction problem, we would like the computer to do the complement, add 1, and add all in the fewest machine instructions. Let's look at how this should work:

 01000001 00110110    4136
-00010010 10110100   -12B4

Do the right byte first:

 01000001 00110110
         +01001011
                +1
          10000000

Notice there is no carry out of this sum, so we do not want to use the same instruction to subtract the left byte, because the SD instruction adds that 1! Instead, we just want to add the complement of D to the memory byte:

 01000001 10000000
+11101101         
 00101110 10000000    2E80

Notice the carry out of the sum, indicating that the result is positive. What happens if there is a carry out of the low byte? Let's try subtracting zero from our result:

 00101110 10000000    2E80
-00000000 00000000   -0000

which is:

 00101110 10000000
+11111111 11111111
                +1
 00101110 10000000    2E80

Here we got the same answer (which we should expect), and the carry out is 1 (which we should expect since the result is not negative). The carry across the byte boundary is also 1, not 0. If we knew this ahead of time, we could use the SD instruction on the left byte as well as the right byte. It is better, however, to have an instruction which will add the DF register into the sum, just as the ADC does. The opcode for this instruction is 75 (or 7D for the immediate addressing mode). Try using it with a few numbers until you see exactly what this instruction does. Don't forget to notice what is in the DF register the first time through (you might start with an ADD which leaves DF in a known state before testing this instruction).

You should be aware that when DF=1, there is no borrow; when DF=0, the SDB effectively borrows from the next byte. If you are not convinced of this, try a few paper examples, or compare the meaning of DF after a subtraction (i.e. whether the result is positive or negative).

Sometimes it is more convenient to subtract the byte in memory from the accumulator. We would like to be able to do this without exchanging the two bytes, so by golly, there is a set of subtract instructions which goes the other way (but still leaves the result in the accumulator and DF). Convince yourself that you understand how the opcodes F7, FF, 77, and 7F work by trying them in Program 5.1. Notice that opcodes that start with "7x" add DF; and the ones whose second digit is greater than seven (78 to 7F) are immediate addressing mode.

What happens when you add a number to itself? You should know that this is the same as multiplying it times two. Look at an example in binary:

 01000011       43
+01000011      +43
 10000110       86

Notice that the bits are almost exactly the same, just shifted over one bit position to the left. For your convenience the 1802 has a special instruction which does this without requiring the memory location that an ADD needs. Try opcode FE in Program 5.1, giving it various first operands. Notice what happens to DF; do you believe it is exactly the same as if you added the number to itself? If not, try the ADD instruction with the same value as both first and second operand. What does the FE opcode do with the second operand? Convince yourself that this is not an immediate addressing mode instruction (try changing location 002A to something else like IDL or SEQ. If you change it to SEQ, you will need to look very carefully for a blink or else put NOPs in 002E and 0032.

What happens when you continue to repeat the shift opcode (by pushing "I" repeatedly)? As you probably guessed, there is a version of the shift that "adds" in the previous contents of DF. Try 7E in Program 5.1. How many times do you have to repeat the operation at any particular datum before you get the same value back? Do you understand why? Try thinking of the accumulator and carry (D and DF) as a 9-bit circular register:

[DF] <-- [D7] [D6] [D5] [D4] [D3] [D2] [D1] [D0] <--+
  |_________________________________________________|

As you might suppose in a nice symmetrical machine like the 1802, there is also a shift right to divide by two. Try opcodes F6 and 76 in Program 5.1. Be sure to watch DF (as reflected in Q). Do you understand what is happening? Look at a paper version, shifting hex 43 right:

 01000011       43
 00100001       21     (and DF=1)

Of course if a shift right with carry were executed next, you would get

 10010000       90     (DF=1)

What is next, if you continue? Try it.

Notice that if shifting left multiplies by two, shifting right divides by two. The bit shifted into DF can be thought of as a remainder; if a number is even, the remainder is zero when dividing by 2; if odd, the remainder is one. Also notice that dividing (shifting right) large numbers requires that you start with the leftmost byte instead of the rightmost byte as in adding and subtracting. If you recall your grammar school arithmetic, you will remember that long division works the same way.

By now you should have a thorough understanding of the arithmetic and logical instructions of the 1802. You already understand the register operations (from Chapter 4) and the branch and I/O instructions (from Chapter 3). All that remains are the control instructions, which are the rest of those with the left digit of "7x" and those with the left digit "Dx". These we cover in Chapter 6.

[ << Chapter 4 ] [ Index ] [ Chapter 6 >> ]

* (A Short Course In Programming is Copyright 1980 by Tom Pittman, and is reproduced in TinyELF's help book with the author's permission. Visit Tom's website.)