Signed Addition Increment ~X+1二~+[x+()]+1 (~x+x)+-+1=-1+(-×+1) ==-X So -~X+1==-X 16
16 Signed Addition • Increment – ~x + 1 = ~x +[x + (-x)] +1 – (~x + x) + -x + 1 == -1 + (-x + 1) == -x – So, – ~x + 1 == -x
Multiplication P75 Computing Exact Product of w-bit numbers x, y Either signed or unsigned Ranges Unsigned: 0x*ys(2w-1)2=22w-2W+1+1 Up to 2w bits Two's complement min: x*y2-2W-1x(2w-1-1)=-22w-2+ 2w-1 Up to 2w-1 bits Twos complement max: x*ys(-2w)2=22w-2 Up to 2w bits, but only for tminw2
17 Multiplication P75 • Computing Exact Product of w-bit numbers x, y – Either signed or unsigned • Ranges – Unsigned: 0 ≤ x * y ≤ (2w – 1) 2 = 22w – 2w+1 + 1 • Up to 2w bits – Two’s complement min: x *y ≥–2w–1*(2w–1–1) = –22w–2 + 2w–1 • Up to 2w–1 bits – Two’s complement max: x * y ≤ (–2w–1 ) 2 = 22w–2 • Up to 2w bits, but only for TMinw2
Multiplication Maintaining Exact Results Would need to keep expanding word size with each product computed Done in software by"arbitrary precision arithmetic packages
18 Multiplication • Maintaining Exact Results – Would need to keep expanding word size with each product computed – Done in software by “arbitrary precision” arithmetic packages
Power-of-2 Multiply with Shift k l疆噩翻器器 Operands: w bits *2k[0 True product: W+k bits u:2k璎霧o∴·p Discard k bits: w bits UMut(u,2)筹额赛∴·1回 TMult(u, 2)
19 Power-of-2 Multiply with Shift • • • 0 ••• 0 1 0 0 0 u 2 * k u · 2 True Product: w+ k k bits Operands: w bits Discard k bits: w bits UMultw(u , 2k ) ••• k • • • 0 ••• 0 0 TMultw(u , 2k ) ••• 0 ••• 0 0
Power-of-2 Multiply with Shift peration u<< k gives u* 2k gu Both signed and unsigned Examples -u<3 u*8 <5-u<3==u*24 Most machines shift and add much faster than multiply Compiler will generate this code automatically
20 Power-of-2 Multiply with Shift • Operation – u << k gives u * 2 k – Both signed and unsigned • Examples – u << 3 == u * 8 – u << 5 - u << 3 == u * 24 – Most machines shift and add much faster than multiply • Compiler will generate this code automatically