By Robert M (adapted by Duane Alan Hahn, a.k.a. Random Terrain)
As an Amazon Associate I earn from qualifying purchases.
In lesson 4, I introduced counting with bits using the binary number system. In this lesson I will cover binary arithmetic and conclude my description of negative numbers using two's complement notation.
Adding binary numbers is as easy as 1, 2, 3. In fact all you ever need to know is:
0+0 = 0
0+1 = 1
1+0 = 1
1+1 = 2
1+1+1 = 3
Adding 2 binary numbers uses the same method as adding decimal numbers. The only difference is that in decimal when you add each pair of digits, if the sum is greater than 9, you carry the 10 to the next column. In binary when the sum is greater than 1, then you carry the 2 to the next column. Except the 2 is in binary notation so its %10 instead of the decimal 2.
The best way to see this method is probably by example. Let's add 2 numbers in decimal, and then add the same numbers in binary.
Decimal:
34
+ 67
------------
||
|+-> 4+7 = 11 ------------------+
| | |
| | Carry the 10 |
| v |
+--> 3+6 + 1 = 10 -------------+|
| ||
| Carry the 10 ||
v ||
0+0 + 1 = 1 -------> 101 = Final answer.
^ ^
| |
+-+---- Note the leading zeros needed to finish the calculation.
Binary:
%0100010 (=34)
+%1000011 (=67)
--------
|||||||
||||||+- 0+1 = %01----------------------------+
|||||| | |
|||||| | No carry |
|||||| v |
|||||+-- 1+1 + 0 = %10 (=2) ----------------+|
||||| | ||
||||| +----+ Carry the 2 (=%10) ||
||||| v ||
||||+--- 0+0 + 1 = %01 --------------------+||
|||| | |||
|||| +----+ No Carry |||
|||| v |||
|||+---- 0+0 + 0 = %00 -------------------+|||
||| | ||||
||| +----+ No Carry ||||
||| v ||||
||+----- 0+0 + 0 = %00 ------------------+||||
|| | |||||
|| +----+ No Carry |||||
|| v |||||
|+------ 1+0 + 0 = %01 -----------------+|||||
| | ||||||
| +----+ No Carry ||||||
| v ||||||
+------- 0+1 + = = %01 ----------------+||||||
| |||||||
| vvvvvvv
+- No Carry %1100101 = 101 decimal = Final answer
Ta-da!
Unfortunately, I chose a poor example in that there is no case of 1 + 1 + 1 in the above example, so let's try another one.
Binary Addition Example 2:
%1101111 (=111 decimal, are you confused yet :P )
+%1111011 (=123 decimal)
--------
|||||||
||||||+- 1+1 = %10 (=2) ----------------------+
|||||| | |
|||||| | Carry the 2 (=%10) |
|||||| v |
|||||+-- 1+1 + 1 = %11 (=3) ----------------+|
||||| | ||
||||| +----+ Carry the 2 (=%10) ||
||||| v ||
||||+--- 1+0 + 1 = %10 --------------------+||
|||| | |||
|||| +----+ Carry the 2 (=%10) |||
|||| v |||
|||+---- 1+1 + 1 = %11 -------------------+|||
||| | ||||
||| +----+ Carry the 2 (=%10) ||||
||| v ||||
||+----- 0+1 + 1 = %10 ------------------+||||
|| | |||||
|| +----+ Carry the 2 |||||
|| v |||||
|+------ 1+1 + 1 = %11 -----------------+|||||
| | ||||||
| +----+ Carry the 2 ||||||
| v ||||||
+------- 1+1 + 1 = %11 ----------------+||||||
| |||||||
+-- Carry the 2 --+|||||||
||||||||
vvvvvvvv
%11101010 = 234 decimal = Final answer
|
v
Please note that the final carry forms a
new digit replacing what was a leading
zero in the numbers being added.
So much for addition, now let's look at subtraction.
You may be beginning to suspect, binary subtraction is very similar to decimal subtraction in the same way that binary addition is similar to decimal addition. If so, then you are correct. Binary subtraction follows the same basic rules as decimal subtraction. The difference is that when you don't have enough to perform the subtraction of 2 digits as in decimal, then you do not borrow 10. Rather you will borrow 2.
So:
0 - 0 = 0
1 - 0 = 1
0 - 1 = 1 borrow 2
1 - 1 = 0
1 - 0 - 1 = 0
1 - 1 - 1 = 0 borrow 2
|
v
This 3rd digit in the subtraction represents the borrow
from the previous step of the subtraction.
As I did for addition, let's try an example.
Decimal Example:
124
- 115
---
|||
||+--> 3 - 5 = 9 with borrow of 10 -------+
|| | |
|| +---- borrow ----+ |
|| v |
|+---> 2 - 1 - 1 = 0 --------------------+|
| | ||
| +---+ no borrow ||
| | ||
+----> 1 - 1 - 0 = 0 -------------------+||
| |||
+- no borrow vvv
009 = 9 final answer.
Same Subtraction Example in Binary:
%1111100 (= 124 decimal)
- %1110011 (= 115 decimal)
--------
|||||||
|||||||
||||||+---> 0 - 1 = 1 with borrow of 2 ---------+
|||||| | |
|||||| +------ borrow ------+ |
|||||| v |
|||||+----> 0 - 1 - 1 = 0 with borrow of 2 --------+|
||||| | ||
||||| +------ borrow ------+ ||
||||| v ||
||||+-----> 1 - 0 - 1 = 0 ------------------------+||
|||| | |||
|||| +---+ no borrow |||
|||| v |||
|||+------> 1 - 0 - 0 = 1 -----------------------+|||
||| | ||||
||| +---+ no borrow ||||
||| v ||||
||+-------> 1 - 1 - 0 = 0 ----------------------+||||
|| | |||||
|| +---+ no borrow |||||
|| v |||||
|+--------> 1 - 1 - 0 = 0 ---------------------+|||||
| | ||||||
| +---+ no borrow ||||||
| v ||||||
+---------> 1 - 1 - 0 = 0 --------------------+||||||
| |||||||
v vvvvvvv
no borrow %0001001 = 9 decimal = final answer
Ta-da!
So you see that binary subtraction closely parallels decimal subtraction.
There is a problem, however, that we have not yet addressed. If we subtract a larger number from a smaller one, the result will be negative. In lesson 4, I began discussion of the 2's complement format for binary negative numbers. In that discussion I said that a prime advantage of 2's complement was that addition and subtraction of numbers in 2's complement resulted in the correct answer in 2's complement format. Now, let's perform a subtraction with a negative result and see what happens. No new rules are required to perform the subtraction, just follow the same procedure as if the expected result will be positive.
Binary Subtraction Example 2:
%1110011 (= 115 decimal)
- %1111100 (= 124 decimal)
--------
|||||||
|||||||
||||||+---> 1 - 0 = 1 --------------------------+
|||||| | |
|||||| +---+ no borrow |
|||||| v |
|||||+----> 1 - 0 - 0 = 1 -------------------------+|
||||| | ||
||||| +---+ no borrow ||
||||| v ||
||||+-----> 0 - 1 - 0 = 1 with borrow of 2 -------+||
|||| | |||
|||| +------ borrow ------+ |||
|||| v |||
|||+------> 0 - 1 - 1 = 0 with borrow of 2 ------+|||
||| | ||||
||| +------ borrow ------+ ||||
||| v ||||
||+-------> 1 - 1 - 1 = 1 with borrow of 2 -----+||||
|| | |||||
|| +------ borrow ------+ |||||
|| v |||||
|+--------> 1 - 1 - 1 = 1 with borrow of 2 ----+|||||
| | ||||||
| +------ borrow ------+ ||||||
| v ||||||
+---------> 1 - 1 - 1 = 1 with borrow of 2 ---+||||||
| |||||||
Leading Zeros! +------ borrow ------+ |||||||
| v |||||||
+----------> 0 - 0 - 1 = 1 with borrow of 2 --+|||||||
| ||||||||
v vvvvvvvv
BORROW! %11110111 = -9 decimal = final answer
The answer above is indeed the expected answer of -9 represented in 2's complement binary notation. Don't worry if you are confused, it will all become clear shortly. The most important thing to note from the above example, is that at the end of our calculation there is still a borrow. Since all that remains to subtract are leading zeros, the final borrow can never be resolved. It will produce an infinite set of leading 1's to our final answer if we keep calculating forever. This is the first clue to understanding 2's complement. Negative numbers in two's complement have an infinite number of leading 1's as opposed to positive numbers which have infinite leading zeros.
From this we can deduce that for all 2's complement numbers the MSB indicates the sign of the number, exactly the same as sign magnitude notation (lesson 4). If the MSB is set, then the number is negative, if the MSB is clear, then the number is positive. The difference is that 2's complement has no representation for negative 0. %10000000 in 2's complement is not negative zero. Instead it is the largest negative number that the bits other than the sign bit can represent. So %10000000 has 7 zeros that 7 bits, 2^7 = 128, so %10000000 is -128 in 2's complement.
Given any positive binary number you can find its two's complement by inverting all the bits (change all 0's to 1, 1's to 0's) and then add 1.
For example:
55 = %01010101
|||||||| Invert all bits
vvvvvvvv
%10101010
+ 1 Add one
---------
%10101011 = -55
Likewise we can perform the same process in reverse to convert any negative number in two's complement format to its positive equivalent.
-55 = %10101011
- 1 Subtract 1
---------
%10101010
|||||||| Invert all bits.
vvvvvvvv
%01010101 = 55 Ta-da!
The Dreaded Overflow and Underflow!
In lesson 4, I mentioned underflow and overflow. Now I will attempt to explain what they are in detail. In lesson 1, we learned that all information in a computer is stored using bits. In lessons 2 and 3 we explored using enumerations and codes made of bits to store information like kinds of fruit. In lesson 4, we learned the standard method for counting in binary. A key point in all these lessons has been finding the number of bits needed to store the information in question. Up until now, in this lesson, I have assumed I had infinite bits to work with (leading zero's and one's were not shown but implied), but in a real computer the number of bits available is limited.
Therefore, the storage of each number used by your program must be restricted to a finite number of bits. Since the 650X family of processors are 8-bit processors (Each instruction works with 8 bit chunks of data at a time), we will assume you will be using multiples of 8 bits to store all your numbers. You don't have to use multiples of 8, it simply makes programming easier.
Earlier, I showed that the MSB of a 2's complement number is the indicator of the sign of the number. For an 8 bit number (a byte) this means that the magnitude of the number is restricted to 7 bits. There are 128 possible combinations for 7 bits. So for positive numbers we can represent values 0 through 127 with a single byte in two's complement. There is no negative zero, so for negative numbers 8 bits can represent the values -1 through -128. Therefore, 1 bytes can hold signed integers in the range from -128 to 127. Recall from lesson 4, a byte can hold UNSIGNED integers from 0 to 255.
Overflow and Underflow are terms meant to describe when an addition or subtraction results in an answer outside the range of values that can be represented by the number of bits being used. Overflow is when the result exceeds the maximum that the number of bits and the chosen format can represent. Underflow is when the result is less that the minimum value that the number of bits and format can represent. Specifically for 8 bits:
For signed 8-bit numbers:
IF A + B is > 127 then OVERFLOW has occurred.
IF A + B is < -128 then UNDERFLOW has occurred.
IF A - B is > 127 then OVERFLOW has occurred.
IF A - B is < -128 then UNDERFLOW has occurred.
For unsigned 8-bit numbers:
IF A + B is > 255 then OVERFLOW has occurred.
IF A - B is < 0 then UNDERFLOW has occurred.
The 650X processors include hardware support for detecting overflow and underflow during math operations. In your programs if overflow or underflow is possible, then you will need to check if it has happened and respond to correct the situation when it does. The details of code to handle overflow and underflow will have to wait for many lessons. For now just understand what it means.
Bonus Quiz: What are possible correct responses for a program to handle overflow or underflow?
Binary Multiplication and Division
Let's take some time to understand how multiplication and division are accomplished with binary numbers. All modern processors have built in support for multiplying and dividing integers, but the old 650X processors do not have specific opcodes (instructions) to multiply or divide 2 integers. That means you have to write code to perform a multiply or divide using the instructions that the processor does have. Luckily, the 650X processor family has build in support for adding and subtracting binary numbers. We will therefore use addition to implement multiplication, and subtraction to perform division.
Think for a moment about decimal multiplication. What does it mean to say 3 times 5?
One way to visualize multiplication is as an area of a rectangle, Area = width times height.
Example: Area = Width x height = 3 x 5 = ?
5
VVVVV
> OOOOO
3 > OOOOO
> OOOOO
|
v
The rectangle of O characters above represents the
area of a 3 by 5 rectangle. To calculate the area we
simply count the O's. There are 15 O's, which
is the same as 3 times 5 = 15!
Likewise, to multiply on a 650X processor, you will solve the problem by adding up the O's of an imaginary rectangle. Your program will Add 5 three times 5+5+5 = 15, or it could add 3 five times 3+3+3+3+3=15. Both ways you accomplish multiplication via repeated addition.
In a similar iterative fashion, division is accomplished via repeated subtraction.
Example: 15 divided by 5 = ?
15 / 5 = 15 - 5 = 10 - 5 = 5 - 5 = 0 -> Remainder = 0
in this case.
| | |
v v v
1 + 1 + 1 = 3 -> 15 / 5 = 3
Okay, that's enough for today's lesson. Please try the following exercises. Stay tuned for a big change of pace in lesson 6 - State Machines!
1.Perform the following binary additions of 2's complement numbers. Express the final result in 8 bits and indicate whether UNDERFLOW or OVERFLOW occurred.
2.Perform the following binary subtractions of 2's complement numbers. Express the final result in 8 bits and indicate whether UNDERFLOW or OVERFLOW occurred.
3.Convert the following 8-bit 2's complement numbers to their negative equivalent.
4.Convert the following 8-bit 2's complement numbers to their positive equivalent.
5.Provide a description of what would constitute OVERFLOW and UNDERFLOW for addition and subtraction involving 16-bit (word) 2's-complement numbers.
1.Perform the following binary additions of 2's complement numbers. Express the final result in 8 bits and indicate whether UNDERFLOW or OVERFLOW occurred.
a.%10010100 + %01101000 = ?
%10010100
+ %01101000
---------
%11111100 -> No overflow or underflow.
b.%00110100 + %01101111 = ?
11111 -> carry the 2.
%00110100
+ %01101111
---------
%10100011 -> Overflow occurred!
Adding 2 positive numbers
resulted in a negative.
c.%10011100 + %11111000 = ?
11111 -> carry the 2.
%10011100
+ %11111000
---------
%10010100 -> No Underflow.
d.%01010011 + %11011101 = ?
11 11111 -> Carry the 2.
%01010011
+ %11011101
---------
%00110001 -> No overflow or underflow.
2.Perform the following binary subtractions of 2's complement numbers. Express the final result in 8 bits and indicate whether UNDERFLOW or OVERFLOW occurred.
a.%10110100 - %01001000 = ?
%10110100
- %01001000
- 1 1 -> borrow 2
---------
%01001100 -> Underflow occurred!
(-) minus (+) should not equal a (+)
b.%00110100 - %01101011 = ?
%00110100
- %01101011
- 11 1 11 -> borrow 2
---------
%11001001 -> No overflow or underflow.
c.%10111100 - %11011010 = ?
%10111100
- %11011010
- 11 1 -> borrow 2
---------
%11100010 -> No overflow or underflow.
d.%00010111 - %11010111 = ?
%00010111
- %11010111
- 11 -> borrow 2
---------
%01000000 -> No overflow or underflow.
3.Convert the following 8-bit 2's complement numbers to their negative equivalent.
a.%00010010
%00010010
||||||||
vvvvvvvv
%11101101 -> invert all bits.
+ 1 -> add 1.
---------
%11101110
b.%11001101
%01000101 = %10111011
c.%11111111
%01111111 = %10000001
d.%10000000
%00000000
||||||||
vvvvvvvv
%11111111
+ 1
---------
%00000000 -> Pretty cool hey!
There is no negative zero
in two's complement!
4.Convert the following 8-bit 2's complement numbers to their positive equivalent.
a.%10110110
%10110110
||||||||
vvvvvvvv
%01001001
+ 1
---------
%01001010
b.%11001101
%11001101 = %00110011
c.%11111111
%11111111 = %00000001
d.%10000000
%10000000 = %10000000 -> Note this is the one case
that doesn't work because
there is no way to show
positive 128 in 8 bits using
two's complement format.
5.Provide a description of what would constitute OVERFLOW and UNDERFLOW for addition and subtraction involving 16-bit (word) 2's-complement numbers.
The number of bits used to represent a two's complement number determines the range of values that can be represented. For 8-bit numbers the range is from +127 to -128. For 16-bit numbers the range is from 32767 to -32768. Therefore overflow occurs in math with 16 bit numbers if the result of the operation is larger than 32767. Underflow occurs if the result is less than -32768.
Other Assembly Language Tutorials
Be sure to check out the other assembly language tutorials and the general programming pages on this web site.
Amazon: Atari 2600 Programming (#ad)
Amazon: 6502 Assembly Language Programming (#ad)
Atari 2600 Programming for Newbies (#ad)
|
|
|
Lesson 5: Binary Math
Disclaimer
View this page and any external web sites at your own risk. I am not responsible for any possible spiritual, emotional, physical, financial or any other damage to you, your friends, family, ancestors, or descendants in the past, present, or future, living or dead, in this dimension or any other.
Use any example programs at your own risk. I am not responsible if they blow up your computer or melt your Atari 2600. Use assembly language at your own risk. I am not responsible if assembly language makes you cry or gives you brain damage.