Addition
Talk0this wiki
The typical processor can perform the addition of two numbers. We use the + sign to show addition of the first number to the second number:
first + second
Addition is commutative, which means that first + second is equal to second + first, so the order of the two values is never important.
Addition of two integers might overflow the width of the answer. You can check for unsigned overflow using a carry flag, or for signed overflow using a signed overflow flag.
Contents |
Binary addition 
Edit
This is how to add two binary digits.
first + second => answer
- 0 + 0 => 00, carry the 0
- 0 + 1 => 01, carry the 0
- 1 + 0 => 01, carry the 0
- 1 + 1 => 10, carry the 1
The answer has two digits. We carry the more significant digit to the next place. This is how to add two bits with a carry.
carry + first + second => answer
- 0 + 0 + 0 => 00, carry the 0
- 0 + 0 + 1 => 01, carry the 0
- 0 + 1 + 0 => 01, carry the 0
- 0 + 1 + 1 => 10, carry the 1
- 1 + 0 + 0 => 01, carry the 0
- 1 + 0 + 1 => 10, carry the 1
- 1 + 1 + 0 => 10, carry the 1
- 1 + 1 + 1 => 11, carry the 1
Addition of unsigned integers Edit
To add a pair of unsigned integers, we work from right to left, from the least significant bit to the most significant bit. We add the bits in each place and we carry.
To compute 27 + 13 => 40 like an 8-bit processor, we write 27 as %00011011 and 13 as %00001101, then we add.
(carry) 00011111
(first) 00011011 27
(second) + 00001101 + 13
========== ====
00101000 40
0 => carry flag
The last carry bit does not fit in the 8-bit answer, but the processor might put the last carry bit in a carry flag.
Unsigned overflow Edit
When the sum of a pair of unsigned integers is too large to fit in the answer, then the answer overflows.
For example, an 8-bit processor can handle unsigned integers from 0 to 255. If an 8-bit processor computes 211 + 104, then the answer will not be the correct 315.
(carry) 11000000
(first) 11010011 211
(second) + 01101000 + 104
========== =====
00111011 59
1 => carry flag
The processor is in this example yielded 59, which is 315 modulo 256.
If the processor put the last carry bit in a carry flag, then we can use the flag to check for unsigned overflow. The carry flag is set to one if we have unsigned overflow, or clear to zero otherwise.
Extended addition Edit
We can use the carry flag to extend the addition to wider integers, if the processor has an "add with carry" instruction.
For example, an 8-bit processor can do 24-bit addition using a chain of three 8-bit additions. We work from right to left, from the least significant byte to the most significant byte. First we add the two least significant bytes. Then we add the two middle bytes with the carry flag. Last we add the two most significant bytes with the carry flag.
We use this way to compute 10730671 + 1673742 => 12404413.
(carry) 000000111<--101110000<--000001110
(first) 10100011 10111100 10101111 10730671
(second) + 00011001 + 10001010 + 00001110 + 1673742
========== ========== ========== =========
10111101 01000110 10111101 12404413
0 => carry flag
Addition of signed integers Edit
To add a pair of twos-complement signed integers, we use the same procedure as for unsigned integers. Thus we use the same instructions of the processor for signed addition as for unsigned addition.
To compute -45 + 104 => 59 like an 8-bit processor, we write -45 as %11010011 and 104 as %00001101, then we add. The computation is the same as for unsigned 211 + 104.
(carry) 11000000 unsigned signed
(first) 11010011 211 -45
(second) + 01101000 + 104 + 104
========== ===== =====
00111011 59 59
1 => carry flag
0 => signed overflow flag
Signed overflow is not the same as unsigned overflow. 59 is the wrong unsigned answer but the correct signed answer, so we have unsigned overflow but not signed overflow. The processor might have a signed overflow flag. We use the carry flag to detect unsigned overflow, but we use the signed overflow flag to detect signed overflow.
To compute -6046545 + 1673742 => -4372803 like an 8-bit processor, we use extended addition of 24-bit signed integers. The computation is the same as for unsigned 10730671 + 1673742.
(carry) 000000111<--101110000<--000001110
(first) 10100011 10111100 10101111 -6046545
(second) + 00011001 + 10001010 + 00001110 + 1673742
========== ========== ========== =========
10111101 01000110 10111101 -4372803
0 => carry flag
0 => unsigned overflow flag
Signed overflow Edit
There are two ways for addition to cause signed overflow.
- We add two positive numbers and get a negative number.
- We add two negative numbers and get a positive number or get zero.
To detect signed overflow, the processor must look at the last two carry bits.
These are the eight possible cases. (Pretend that zero is also "positive".)
(carry) 00 (carry) 00
(first) 0nnn positive (first) 0nnn positive
(second) + 0nnn positive (second) + 1nnn negative
=============== ===============
0nnn positive 1nnn negative
0 => carry 0 => carry
0 => signed overflow 0 => signed overflow
(carry) 00 (carry) 10
(first) 1nnn negative (first) 1nnn negative
(second) + 0nnn positive (second) + 1nnn negative
=============== ===============
1nnn negative 0nnn positive
0 => carry 1 => carry
0 => signed overflow 1 => signed overflow
(carry) 01 (carry) 11
(first) 0nnn positive (first) 0nnn positive
(second) + 0nnn positive (second) + 1nnn negative
=============== ===============
1nnn negative 0nnn positive
0 => carry 1 => carry
1 => signed overflow 0 => signed overflow
(carry) 11 (carry) 11
(first) 1nnn negative (first) 1nnn negative
(second) + 0nnn positive (second) + 1nnn negative
=============== ===============
0nnn positive 1nnn negative
1 => carry 1 => carry
0 => signed overflow 0 => signed overflow
Notice that when the last two carry bits are equal, then signed overflow never happens; but when the last two carry bits are not equal, then signed overflow always happens. This is the rule that processors must follow to set or clear the signed overflow flag.
If you read the documentation for a processor, and the documentation describes a flag that checks the equality of the last two carry bits, then you know that this flag is a signed overflow flag.
Floating-point addition Edit
Many ROM hacks have no floating-point numbers. You might find floating-point numbers in modern computers, and in ROM-hacking tools for modern computers.
Addition of floating-point numbers tends to go well. One of the possible problems is subtractive cancellation, which happens when you add two numbers but the sum is close to zero. Then the sum may have more error than usual.
This is some example from a modern computer.
> -0.000000000005431 + 0.000000000005432 => 1.0000000000005e-15 > -1.000000000005431 + 1.000000000005432 => 1.11022302462516e-15
The correct answer for both sums is exactly 1.0e-15. Now 1.0000000000005e-15 is close but 1.11022302462516e-15 is wrong by more than 11%.
Addition by processor Edit
You can help ROM Hack City by adding a section for your processor, or by making the section more complete and accurate.
6502 and 65816 Edit
|
TODO... Move most everything to the clc and adc pages. Keep here only a brief summary. --Kernigh 15:33, 28 August 2009 (UTC) |
The two instructions to learn are
- clc to clear the accumulator.
- adc to add the operand and the carry flag to the accumulator.
This is the full list of clc and adc instructions.
;; 6502 and 65c02 and 65816 clc adc #$nn ; 8-bit immediate value adc $nn ; direct page adc $nn,x adc $nnnn ; 16-bit address adc $nnnn,x adc $nnnn,y adc ($nn,x) ; indirect 16-bit address from direct page adc ($nn),y ;; only 65c02 and 65816 adc ($nn) ; indirect 16-bit address from direct page ;; only 65816 adc #$nnnn ; 16-bit immediate value adc $nn,s ; stack adc ($nn,s),y ; indirect 16-bit address from stack adc $nnnnnn ; 24-bit long address adc $nnnnnn,x adc [$nn] ; indirect 24-bit long address from direct page adc [$nn],y
To compute left + right, you need to load left in the accumulator, clear the carry flag with clc, then add right with adc. The answer will be in the accumulator, but you can sta the answer elsewhere.
;; left + right => sum lda left ; A = left clc adc right ; A += right sta sum ; sum = A
To sum more than two values, you can apply clc and adc in a chain.
;; term1 + term2 + term3 + term4 => sum lda term1 clc adc term2 clc adc term3 clc adc term4 sta sum
One of the 65816 mistakes is to forget clc before adc. You always need clc before adc, unless
- you are performing extended addition, or otherwise need to add the carry flag.
- you care not if the sum is off by one.
- you know that the carry flag is already clear (but if you edit the code, you might need to insert the clc).
If you have adc without clc, then a good idea is to provide a comment that explains why.
lda term adc #3 ; add a small amount, 3 or 4
One use for extended addition is to add two 16-bit integers. You add the low bytes, then carry, then add the high bytes. The low bytes and high bytes can be anywhere in memory, big-endian, little-endian, or in separate tables. This example uses the little-endian byte order, which is the same order that the 6502 uses for 16-bit addresses. In little-endian byte order, the low byte is at some address, while the high byte is at address + 1.
;; left + right => sum, using 16-bit extended addition lda left clc adc right sta sum lda left + 1 ;; carry adc right + 1 sta sum + 1
If you have the 65816, then you can use the 16-bit accumulator, which is easier than coding the extended addition.
;; left + right => sum, using 16-bit mode of 65816 rep #$20 ; switch to 16-bit A lda left clc adc right sta sum sep #$20 ; return to 8-bit A
