1Queen’s University 1CISC 221: Computer Architecture Integer Arithmetic CISC 221: Computer Architecture Fall 2021 Instructor: Yuanzhu Chen 1 Queen’s University 2CISC 221: Computer Architecture Outline ¢ Addition ¢ Complement & increment ¢ Multiplication ¢ Power-of-2 via shifting 2 2Queen’s University 3CISC 221: Computer Architecture Unsigned Addition 3 Queen’s University 4CISC 221: Computer Architecture Unsigned Addition ¢ Standard addition function § Ignores carry output ¢ Implements modular arithmetic s = +!" = x + y mod 2w • • • • • • x y+ • • •x + y • • • True sum: w+1 bits Operands: w bits Discard carry: w bits +!" 4 3Queen’s University 5CISC 221: Computer Architecture 0 2 4 6 8 10 12 14 0 2 4 6 8 10 12 14 0 4 8 12 16 20 24 28 32 Integer Addition Visualizing (Mathematical) Integer Addition ¢ Integer addition § 4-bit integers x, y § Compute true sum x + y § Values increase linearly with x and y § Forms planar surface x + y x y 5 Queen’s University 6CISC 221: Computer Architecture 0 2 4 6 8 10 12 14 0 2 4 6 8 10 12 14 0 2 4 6 8 10 12 14 16 Visualizing Unsigned Addition ¢ Wraps around § If true sum ≥ 2w § At most once 0 2w 2w+1 +!" x y true sum modular sum Overflow Overflow 6 4Queen’s University 7CISC 221: Computer Architecture Mathematical Properties ¢ Modular addition forms an Abelian Group § Closed under addition 0 £ +!" £ 2w –1 § Commutative +!" = +!" § Associative( +!" ) +!" = +!" ( +!" ) § 0 is additive identity +!" 0 = § Every element x has an additive inverse2! − 7 Queen’s University 8CISC 221: Computer Architecture Two’s Complement Addition 8 5Queen’s University 9CISC 221: Computer Architecture Two’s Complement Addition • • • • • • x y+ • • •x + y • • • True sum: w+1 bits Operands: w bits Discard carry: w bits +!# 9 Queen’s University 10CISC 221: Computer Architecture Two’s Complement Addition ¢ +!# and +!" have identical bit-level behavior § Signed vs. unsigned addition in C: int s, t, u, v; s = (int) ((unsigned) u + (unsigned) v); t = u + v § Will give s == t • • • • • • x y+ • • •x + y • • • True Sum: w+1 bits Operands: w bits Discard Carry: w bits +!# 10 6Queen’s University 11CISC 221: Computer Architecture +!" Overflow ¢ Functionality § True sum requires w+1 bits § Drop off MSB § Treat remaining bits as 2’s complement integer –2w –1 –2w 0 2w –1–1 2w–1 True Sum +!# Result 1 000…0 1 011…1 0 000…0 0 100…0 0 111…1 100…0 000…0 011…1 PosOver NegOver 11 Queen’s University 12CISC 221: Computer Architecture -8 -6 -4 -2 0 2 4 6 -8 -6 -4 -2 0 2 4 6 -8 -6 -4 -2 0 2 4 6 8 Visualizing 2’s Complement Addition ¢ Values § 4-bit two’s comp. § Range from -8 to +7 ¢ Wraps Around § If sum ³ 2w–1 § Becomes negative § At most once § If sum < –2w–1 § Becomes positive § At most once x y PosOver NegOver +!# 12 7Queen’s University 13CISC 221: Computer Architecture Complement & Increment 13 Queen’s University 14CISC 221: Computer Architecture Negation: Complement & Increment ¢ Claim: the following holds for 2’s complement ~x + 1 == -x ¢ Complement § Observation: ~x + x == 1111…111 == -1 ¢ Increment § (complete proof?) 1 0 0 1 0 11 1x 0 1 1 0 1 00 0~x+ 1 1 1 1 1 11 1-1 14 8Queen’s University 15CISC 221: Computer Architecture Complement & Increment Examples Decimal Hex Binary x 15213 3B 6D 00111011 01101101 ~x -15214 C4 92 11000100 10010010 ~x+1 -15213 C4 93 11000100 10010011 y -15213 C4 93 11000100 10010011 x = 15213 Decimal Hex Binary 0 0 00 00 00000000 00000000 ~0 -1 FF FF 11111111 11111111 ~0+1 0 00 00 00000000 00000000 x = 0 15 Queen’s University 16CISC 221: Computer Architecture Multiplication 16 9Queen’s University 17CISC 221: Computer Architecture Multiplication ¢ Goal: Computing Product of w-bit numbers x, y § Either signed or unsigned ¢ But, exact results can be bigger than w bits § Unsigned: up to 2w bits § Result range: 0 ≤ x * y ≤ (2w – 1) 2 = 22w – 2w+1 + 1 § Two’s complement min (negative): Up to 2w-1 bits § Result range: x * y ≥ (–2w–1)*(2w–1–1) = –22w–2 + 2w–1 § Two’s complement max (positive): Up to 2w bits, but only for (TMinw)2 § Result range: x * y ≤ (–2w–1) 2 = 22w–2 ¢ So, maintaining exact results… § would need to keep expanding word size with each product computed § is done in software, if needed § e.g., by “arbitrary precision” arithmetic packages 17 Queen’s University 18CISC 221: Computer Architecture Unsigned Multiplication in C ¢ Standard multiplication function § Ignores high order w bits ¢ Implements Modular Arithmetic ∗!" = x × y mod 2w • • • • • • x y× • • •x×y • • • True product: 2*w bits Operands: w bits Discard w bits: w bits ∗!" • • • 18 10 Queen’s University 19CISC 221: Computer Architecture Signed Multiplication in C ¢ Standard multiplication function § Ignores high order w bits § Some of which are different for signed vs. unsigned multiplication § Lower bits are the same • • • • • • x y× • • •x×y • • • True Product: 2*w bits Operands: w bits Discard w bits: w bits ∗!# • • • 19 Queen’s University 20CISC 221: Computer Architecture Power-of-2 Multiplication & Division 20 11 Queen’s University 21CISC 221: Computer Architecture Power-of-2 Multiply with Shift ¢ Operation § x << k gives x * 2k § Both signed and unsigned ¢ Examples § x << 3 == x * 8 § (x << 5) – (x << 3)== x * 24 § Most machines shift and add faster than multiply § Compiler generates this code automatically • • • 0 0 1 0 0 0••• x 2k× x×2kTrue product: w+k bits Operands: w bits Discard k bits: w bits ∗!" 2# ••• w • • • 0 0 0••• ∗!$ 2# 0 0 0•••••• 21 Queen’s University 22CISC 221: Computer Architecture Unsigned Power-of-2 Divide with Shift ¢ Quotient of unsigned by power of 2 § x >> k gives ë x / 2k û § Uses logical shift Division Computed Hex Binary x 15213 15213 3B 6D 00111011 01101101 x >> 1 7606.5 7606 1D B6 00011101 10110110 x >> 4 950.8125 950 03 B6 00000011 10110110 x >> 8 59.4257813 59 00 3B 00000000 00111011 0 0 1 0 0 0••• x 2k/ x / 2kDivision: Operands: ••• k ••• ••• •••0 0 0••• ••• ë x / 2k û •••Result: . Binary Point 0 0 0••• 22 12 Queen’s University 23CISC 221: Computer Architecture Summary: Basic Rules ¢ Addition: § Unsigned/signed: Normal addition followed by truncate, same operation on bit level § Unsigned: addition mod 2w § Mathematical addition + possible subtraction of 2w § Signed: modified addition mod 2w (result in proper range) § Mathematical addition + possible addition or subtraction of 2w ¢ Multiplication: § Unsigned/signed: Normal multiplication followed by truncate, same operation on bit level § Unsigned: multiplication mod 2w § Signed: modified multiplication mod 2w (result in proper range) 23