One’s complement additionTwo’s complementMore about two’s complementTwo’s complement additionAnother two’s complement exampleWhy does this work?Comparing the signed number systemsRanges of the signed number systemsConverting signed numbers to decimalExample solutionOur four-bit unsigned adder circuitMaking a subtraction circuitA two’s complement subtraction circuitSmall differencesAn adder-subtractor circuitSigned overflowDetecting signed overflowSign extensionSubtraction summaryArithmetic-logic unitsThe four-bit adderIt’s the adder-subtractor again!The multi-talented adderModifying the adder inputsSome more possible functionsThe role of CITable of arithmetic functionsMapping the table to an adderBuilding the input logicPrimitive gate-based input logicPrimitive gate implementationBitwise operationsBitwise operations in programmingBitwise operations in networkingDefining a logic unitOur simple logic unitCombining the arithmetic and logic unitsOur ALU function tableA complete ALU circuitComments on the multiplexerThe completed ALUArithmetic summary01/15/19 Arithmetic-logic units 1One’s complement addition•To add one’s complement numbers:–First do unsigned addition on the numbers, including the sign bits.–Then take the carry out and add it to the sum.•Two examples:•This is simpler and more uniform than signed magnitude addition.0111 (+7)+ 1011 + (-4)1 00100010+ 10011 (+3)0011 (+3)+ 0010 + (+2)0 01010101+ 00101 (+5)01/15/19 Arithmetic-logic units 2Two’s complement•Our final idea is two’s complement. To negate a number, complement each bit (just as for ones’ complement) and then add 1. •Examples:11012= 1310(a 4-bit unsigned number)0 1101 = +1310(a positive number in 5-bit two’s complement)1 0010 = -1310(a negative number in 5-bit ones’ complement)1 0011 = -1310(a negative number in 5-bit two’s complement)01002= 410(a 4-bit unsigned number)0 0100 = +410(a positive number in 5-bit two’s complement)1 1011 = -410(a negative number in 5-bit ones’ complement)1 1100 = -410(a negative number in 5-bit two’s complement)01/15/19 Arithmetic-logic units 3•Two other equivalent ways to negate two’s complement numbers:–You can subtract an n-bit two’s complement number from 2n.–You can complement all of the bits to the left of the rightmost 1.01101 = +1310(a positive number in two’s complement)10011 = -1310(a negative number in two’s complement)00100 = +410(a positive number in two’s complement) 11100 = -410(a negative number in two’s complement)•Often, people talk about “taking the two’s complement” of a number. This is a confusing phrase, but it usually means to negate some number that’s already in two’s complement format.More about two’s complement100000- 01101 (+1310)10011 (-1310)100000- 00100 (+410)11100 (-410)01/15/19 Arithmetic-logic units 4Two’s complement addition•Negating a two’s complement number takes a bit of work, but addition is much easier than with the other two systems.•To find A + B, you just have to:–Do unsigned addition on A and B, including their sign bits. –Ignore any carry out.•For example, to find 0111 + 1100, or (+7) + (-4): –First add 0111 + 1100 as unsigned numbers:–Discard the carry out (1).–The answer is 0011 (+3).0111+ 11001001101/15/19 Arithmetic-logic units 5Another two’s complement example•To further convince you that this works, let’s try adding two negative numbers—1101 + 1110, or (-3) + (-2) in decimal.•Adding the numbers gives 11011:•Dropping the carry out (1) leaves us with the answer, 1011 (-5).1101+ 11101101101/15/19 Arithmetic-logic units 6Why does this work?•For n-bit numbers, the negation of B in two’s complement is 2n - B (this is one of the alternative ways of negating a two’s-complement number).A - B = A + (-B)= A + (2n - B)= (A - B) + 2n•If A B, then (A - B) is a positive number, and 2n represents a carry out of 1. Discarding this carry out is equivalent to subtracting 2n, which leaves us with the desired result (A - B). •If A B, then (A - B) is a negative number and we have 2n - (A - B). This corresponds to the desired result, -(A - B), in two’s complement form.01/15/19 Arithmetic-logic units 7Comparing the signed number systems•Here are all the 4-bit numbers in the different systems.•Positive numbers are the same in all three representations.•Signed magnitude and one’s complement have two ways of representing 0. This makes things more complicated.•Two’s complement has asymmetric ranges; there is one more negative number than positive number. Here, you can represent -8 but not +8.•However, two’s complement is preferred because it has only one 0, and its addition algorithm is the simplest.Decimal S.M. 1’s comp. 2’s comp. 7 0111 0111 0111 6 0110 0110 0110 5 0101 0101 0101 4 0100 0100 0100 3 0011 0011 0011 2 0010 0010 0010 1 0001 0001 0001 0 0000 0000 0000 -0 1000 1111 — -1 1001 1110 1111 -2 1010 1101 1110 -3 1011 1100 1101 -4 1100 1011 1100 -5 1101 1010 1011 -6 1110 1001 1010 -7 1111 1000 1001 -8 — — 100001/15/19 Arithmetic-logic units 8•How many negative and positive numbers can be represented in each of the different systems on the previous page?•In general, with n-bit numbers including the sign, the ranges are: Unsigned Signed Magnitude One’s complement Two’s complement Smallest 0 -(2n-1-1) -(2n-1-1) -2n-1 Largest 2n-1 +(2n-1-1) +(2n-1-1) +(2n-1-1) Ranges of the signed number systems Unsigned Signed Magnitude One’s complement Two’s complement Smallest 0000 (0) 1111 (-7) 1000 (-7) 1000 (-8) Largest 1111 (15) 0111 (+7) 0111 (+7) 0111 (+7)01/15/19 Arithmetic-logic units 9Converting signed numbers to decimal•Convert 110101 to decimal, assuming this is a number in:(a) signed magnitude format(b) ones’ complement(c) two’s complement01/15/19 Arithmetic-logic units 10Example solution•Convert 110101 to decimal, assuming this is a number in:Since the sign bit is 1, this is a negative number. The easiest way to find the magnitude is to convert it to a positive number.(a) signed magnitude formatNegating the original number, 110101, gives 010101, which is +21 in decimal. So 110101 must represent -21.(b) ones’ complementNegating 110101 in ones’ complement yields 001010 = +1010, so the original number must have been -1010.(c) two’s complementNegating 110101 in two’s complement gives 001011 =
View Full Document
Unlocking...