Robert M Posted December 10, 2003 Share Posted December 10, 2003 Lesson 5 - Binary Math 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. Binary Addition: 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. Example: 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 lets try another one: Binary Addition exmaple 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. Binary 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 addtion. 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 substraction 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 example subtraction 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 substraction 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 Two' Complement Revisited: 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. FINDING THE TWO' 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! [u]THE DREADED OVERFLOW AND UNDERFLOW!:[/u] 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 famliy 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. [b]BONUS QUIZ[/b]: What are possible correct responses for a program to handle overflow or underflow? BINARY MULIPLICATION 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. Multiplying: Think for a moment about decimal multiplication. What does it mean to say 3 time 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 mulitply 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. Division: In a similar iterative fashion, division is accomplished via repeated subtraction. Example: 15 divided 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! Exercises: 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 = ? b. %00110100 + %01101111 = ? c. %10011100 + %11111000 = ? d. %01010011 + %11011101 = ? 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 = ? b. %00110100 - %01101011 = ? c. %10111100 - %11011010 = ? d. %00010111 - %11010111 = ? 3. Convert the following 8-bit 2's complement numbers to their negative equivalent a. %00010010 b. %01000101 c. %01111111 d. %00000000 4. Convert the following 8-bit 2's complement numbers to their positive equivalent a. %10110110 b. %11001101 c. %11111111 d. %10000000 5. Provide a description of what would constitute OVERFLOW and UNDERFLOW for addition and subtraction involving 16-bit (word) 2's-complement numbers. Quote Link to comment Share on other sites More sharing options...
Robert M Posted January 13, 2004 Author Share Posted January 13, 2004 Lesson 5 - Excercise Answers: Exercises: 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 --------- %11111100 -> No overflow or underflow. b. 11111 -> carry the 2. %00110100 + %01101111 --------- %10100011 -> Overflow occurred! Adding 2 positive numbers resulted in a negative. c. 11111 -> carry the 2. %10011100 + %11111000 --------- %10010100 -> No Underflow. d. 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 - 1 1 -> borrow 2 --------- %01001100 -> Underflow occurred! (-) minus (+) should not equal a (+) b. %00110100 - %01101011 - 11 1 11 -> borrow 2 --------- %11001001 -> No overflow or underflow. c. %10111100 - %11011010 - 11 1 -> borrow 2 --------- %11100010 -> No overflow or underflow. d. %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 |||||||| vvvvvvvv %11101101 -> invert all bits. + 1 -> add 1. --------- %11101110 b. %01000101 = %10111011 c. %01111111 = %10000001 d. %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 |||||||| vvvvvvvv %01001001 + 1 --------- %01001010 b. %11001101 = %00110011 c. %11111111 = %00000001 d. %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. ANSWER: 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. Quote Link to comment Share on other sites More sharing options...
flavoredthunder Posted April 19, 2004 Share Posted April 19, 2004 Hey thanks for writing this tutorial. I have been struggling with programming the 2600 for a couple of weeks now and I realized that it was because I had only a "loose" grasp over assembly. The 6502 book that I picked up was really too general for me and I really appreciate how you continually tie in references to the 2600. Keep up the good work. Quote Link to comment Share on other sites More sharing options...
Like us on Facebook
Follow us on Twitter
AtariAge on Instagram
Watch us on YouTube
Chat on Discord
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.