CS/COE0447 Computer Organization & Assembly Language Chapter 3 1 Topics Negative binary integers Sign magnitude, 1s complement, 2s 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 bits 2 Computer Organization 3 Binary 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 CPUs datapath implementation 4 Binary Number Representation We looked at unsigned numbers before B31B30B2B1B0 B31231+BB30230+B+BB222+BB121+BB020 We will deal with more complicated cases Negative integers Real numbers (a.k.a. floating-point numbers) 5 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 00000001 11111111 0 1 255 32-bit number range [0..4294967296] In general, the range is [02N-1] Addition and subtraction: as in decimal (on board) 6 Unsigned 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) 7 Important 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 ASCII 8

Signed 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, 1s complement, 2s complement 9 Method 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 numbers 10 Method 2: Ones Complement ((2N-1) number): To multiply a 1s Complement number by -1, subtract the number from (2N-1)_unsigned. Or, equivalently (and easily!), simply flip the bits 1CRepOf(A) +B 1CRepOf(-A) = 2N-1_unsigned (interesting tidbit) Lets assume a 4-bit representation (to make it easy to work with) Examples:

0011: 3 0110: 6 1001: -6 1111: -0 1000: -7 1111 0110 1111 0000 1111 0111 or just flip the bits of 0110 or just flip the bits of 0000 or just flip the bits of 0111 Properties Two representations of zero Equal number of positive and negative numbers 11

Method 3: Twos Complement (2N number): To multiply a 2s Complement number by -1, subtract the number from 2N_unsigned. Or, equivalently (and easily!), simply flip the bits and add 1. 2CRepOf(A) +B 2CRepOf(-A) = 2N_unsigned (interesting tidbit) Lets assume a 4-bit representation (to make it easy to work with) Examples: 0011: 3 0110: 6 1010: -6 1111: -1

1001: -7 1000: -8 10000 0110 10000 0001 10000 0111 10000 1000 or just flip the bits of 0110 and add 1 or just flip the bits of 0001 and add 1 or just flip the bits of 0111 and add 1 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) 12 Ranges of numbers Range (min to max) in N bits: SM and 1C: -2(N-1) -1 to +B2(N-1) -1 2C: -2(N-1) to +B2(N-1) -1 13 Sign 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} 14 Summary Code Sign-Magnitude 1s Complement 2s Complement 000 +B0

+B0 +B0 001 +B1 +B1 +B1 010 +B2 +B2 +B2 011 +B3 +B3

+B3 100 -0 -3 -4 101 -1 -2 -3 110 -2 -1 -2

111 -3 -0 -1 Issues # of zeros Balance (and thus range) Operations implementation 15 2s Complement Examples 32-bit signed numbers 0000 0000 0000 0000 0000 0000 0000 0000 = 0 0000 0000 0000 0000 0000 0000 0000 0001 = +B1 0000 0000 0000 0000 0000 0000 0000 0010 = +B2

0111 1111 1111 1111 1111 1111 1111 1110 = +B2,147,483,646 0111 1111 1111 1111 1111 1111 1111 1111 = +B2,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 1110 = -2 1111 1111 1111 1111 1111 1111 1111 1111 = -1 16 Addition We can do binary addition just as we do decimal arithmetic Examples in lecture

Can be simpler with 2s complement (1C as well) We dont need to worry about the signs of the operands! Examples in lecture 17 Subtraction Notice that subtraction can be done using addition Add 1 A B = A +B (-B) We know how to negate a number The hardware used for addition can be used for subtraction with a negating unit at one Invert (flip) the bits input 18

Signed versus Unsigned Operations unsigned operations view the operands as positive numbers, even if the most significant bit is 1 Example: 1100 is 12_unsigned but -4_2C Example: slt versus sltu li $t0,-4 li $t1,10 slt $t3,$t0,$t1 sltu $t4,$t0,$t1 $t3 = 1 $t4 = 0 !! 19 Signed Overflow Because we use a limited number of bits to represent a number, the result of an operation may not fit overflow No overflow when We add two numbers with different signs We subtract a number with the same sign Overflow when

Adding two positive numbers yields a negative number Adding two negative numbers yields a positive number How about subtraction? 20 Overflow On an overflow, the CPU can Generate an exception Set a flag in a status register Do nothing In MIPS on green card: add, addi, sub: footnote (1) May cause overflow exception 21 Overflow with Unsigned Operations addu, addiu, subu Footnote (1) is not listed for these instructions on the green card This tells us that, In MIPS, nothing is done on unsigned overflow How could it be detected for, e.g., add?

Carry out of the most significant position (in some architectures, a condition code is set on unsigned overflow, which IS the carry out from the top position) 22 Branch Instructions: Branching Backwards # $t3 = 1 +B 2 +B 2 +B 2 +B 2; $t4 = 1 +B 3 +B 3 +B 3 +B 3 li $t0,0 li $t3,1 li $t4, 1 loop: addi $t3,$t3,2 addi $t4,$t4,3 addi $t0,$t0,1 slti $t5,$t0,4 bne $t5,$zero,loop machine code: 0x15a0fffb BranchAddr = {14{imm[15]}, imm, 2b0} 23

1-bit Adder With a fully functional single-bit adder We can build a wider adder by linking many one-bit adders 3 inputs A: input A B: input B Cin: input C (carry in) 2 outputs S: sum Cout: carry out 24 N-bit Adder (0) An N-bit adder can be constructed with N one-bit adders A carry generated in one stage is propagated to the next (ripple carry adder)

3 inputs A: N-bit input A B: N-bit input B Cin: input C (carry in) 2 outputs S: N-bit sum Cout: carry out 28 N-bit Ripple-Carry Adder (0) (0) (0) (1) (1) (0) (0)

0 0 1 1 1 0 0 1 1 0 0 (0) 1

(1) 1 (1) 0 (0) 1 29 Describing a single-bit adder A truth table will tell us about the operation of a single-bit adder Input Output A B Cin

S Cout 0 0 0 0 0 0 0 1 1 0 0

1 0 1 0 0 1 1 0 1 1 0 0 1

0 1 0 1 0 1 1 1 0 0 1 1 1

1 1 1 30