CS/COE0447 Computer Organization & Assembly LanguageTopicsComputer OrganizationBinary ArithmeticBinary Number RepresentationUnsigned Binary NumbersUnsigned Binary Numbers in MIPSImportant 7-bit Unsigned NumbersSigned NumbersMethod 1: Sign MagnitudeMethod 2: One’s ComplementMethod 3: Two’s ComplementRanges of numbersSign ExtensionSummary2’s Complement ExamplesAdditionSubtractionSigned versus Unsigned OperationsSigned OverflowOverflowOverflow with Unsigned OperationsBranch Instructions: Branching Backwards1-bit AdderImplementing an AdderBoolean Logic formulasLogic GatesImplementation in logic gatesN-bit AdderN-bit Ripple-Carry Adder1CS/COE0447Computer Organization & Assembly LanguageChapter 32Topics•Negative binary integers–Sign magnitude, 1’s complement, 2’s complement–Sign extension, ranges, arithmetic•Signed versus unsigned operations•Overflow (signed and unsigned)•Branch instructions: branching backwards•Implementation of addition•Chapter 3 Part 2 will cover:–Implementations of multiplication, division –Floating point numbers•Binary fractions•IEEE 754 floating point standard•Operations–underflow–Implementations of addition and multiplication (less detail than for integers)–Floating-point instructions in MIPS–Guard and Round bits3Computer Organization4Binary Arithmetic•So far we have studied–Instruction set basics–Assembly & machine language•We will now cover binary arithmetic algorithms and their implementations•Binary arithmetic will provide the basis for the CPU’s “datapath” implementation5Binary Number Representation•We looked at unsigned numbers before–B31B30…B2B1B0–B31231+B30230+…+B222+B121+B020•We will deal with more complicated cases–Negative integers–Real numbers (a.k.a. floating-point numbers)Unsigned Binary Numbers•Limited number of binary numbers (patterns of 0s and 1s)–8-bit number: 256 patterns, 00000000 to 11111111–General: 2N bit patterns in N bits•16 bits: 216 = 65,536 bit patterns•32 bits: 232 = 4,294,967,296 bit patterns•Unsigned numbers use the patters for 0 and positive numbers–8-bit number range corresponds to•00000000 0•00000001 1•…•11111111 255–32-bit number range [0..4294967296]–In general, the range is [0…2N-1]•Addition and subtraction: as in decimal (on board)6Unsigned Binary Numbers in MIPS•MIPS instruction set provides support–addu $1,$2,$3 - adds two unsigned numbers–Addiu $1,$2,33 – adds unsigned number with SIGNED immediate (see green card!)–Subu $1,$2,$3–Etc•In MIPS: the carry/borrow out is ignored–Overflow is possible, but hardware ignores it–Signed instructions throw exceptions on overflow (see footnote 1 on green card)•Unsigned memory accesses: lbu, lhu–Loaded value is treated as unsigned–Convert from smaller bit width (8, 16) to 32 bits–Upper bits in the 32-bit destination register are set to 0s (see green card)7Important 7-bit Unsigned Numbers•American Standard Code for Information Interchange (ASCII)–7 bits used for the characters–8th bit may be used for error detection (parity)•Unicode: A larger encoding; backward compatible with ASCII8Signed Numbers•How shall we represent both positive and negative numbers?•We still have a limited number of bits–N bits: 2N bit patterns•We will assign values to bit patterns differently–Some will be assigned to positive numbers and some to negative numbers•3 Ways: sign magnitude, 1’s complement, 2’s complement910Method 1: Sign Magnitude•{sign bit, absolute value (magnitude)}–Sign bit•“0” – positive number•“1” – negative number–EX. (assume 4-bit representation)•0000: 0•0011: 3•1001: -1•1111: -7•1000: -0•Properties–two representations of zero–equal number of positive and negative numbers11Method 2: One’s Complement•((2N-1) – number): To multiply a 1’s Complement number by -1, subtract the number from (2N-1)_unsigned. Or, equivalently (and easily!), simply flip the bits•1CRepOf(A) + 1CRepOf(-A) = 2N-1_unsigned (interesting tidbit)•Let’s assume a 4-bit representation (to make it easy to work with)•Examples: •0011: 3•0110: 6•1001: -6 1111 – 0110 or just flip the bits of 0110•1111: -0 1111 – 0000 or just flip the bits of 0000•1000: -7 1111 – 0111 or just flip the bits of 0111•Properties–Two representations of zero–Equal number of positive and negative numbers12Method 3: Two’s Complement•(2N – number): To multiply a 2’s Complement number by -1, subtract the number from 2N_unsigned. Or, equivalently (and easily!), simply flip the bits and add 1.•2CRepOf(A) + 2CRepOf(-A) = 2N_unsigned (interesting tidbit)•Let’s assume a 4-bit representation (to make it easy to work with)•Examples: •0011: 3•0110: 6•1010: -6 10000 – 0110 or just flip the bits of 0110 and add 1•1111: -1 10000 – 0001 or just flip the bits of 0001 and add 1•1001: -7 10000 – 0111 or just flip the bits of 0111 and add 1•1000: -8 10000 – 1000 or just flip the bits of 1000 and add 1•Properties–One representation of zero: 0000–An extra negative number: 1000 (this is -8, not -0)13Ranges of numbers•Range (min to max) in N bits:–SM and 1C: -2(N-1) -1 to +2(N-1) -1–2C: -2(N-1) to +2(N-1) -114Sign Extension•#s are often cast into vars with more capacity•Sign extension (in 1c and 2c): extend the sign bit to the left, and everything works out•la $t0,0x00400033•addi $t1,$t0, 7•addi $t2,$t0, -7•R[rt] = R[rs] + SignExtImm•SignExtImm = {16{immediate[15]},immediate}15Summary•Issues–# of zeros–Balance (and thus range)–Operations’ implementationCode Sign-Magnitude 1’s Complement 2’s Complement000 +0 +0 +0001 +1 +1 +1010 +2 +2 +2011 +3 +3 +3100 -0 -3 -4101 -1 -2 -3110 -2 -1 -2111 -3 -0 -1162’s Complement Examples•32-bit signed numbers–0000 0000 0000 0000 0000 0000 0000 0000 = 0–0000 0000 0000 0000 0000 0000 0000 0001 = +1–0000 0000 0000 0000 0000 0000 0000 0010 = +2–…–0111 1111 1111 1111 1111 1111 1111 1110 = +2,147,483,646–0111 1111 1111 1111 1111 1111 1111 1111 = +2,147,483,647–1000 0000 0000 0000 0000 0000 0000 0000 = - 2,147,483,648 -2^31–1000 0000 0000 0000 0000 0000 0000 0001 = - 2,147,483,647–1000 0000 0000 0000 0000 0000 0000 0010 = - 2,147,483,646–…–1111 1111 1111 1111 1111 1111 1111 1101 = -3–1111 1111 1111 1111 1111 1111 1111