Integer Arithmetic - Northwestern University

Integer Arithmetic - Northwestern University

CS213 Integers Apr 7, 2008 Topics Numeric Encodings Unsigned & Twos complement Programming Implications C promotion rules Basic operations Addition, negation, multiplication Programming Implications Consequences of overflow Using shifts to perform power-of-2 multiply/divide EECS213 S08 C Puzzles Taken from old exams Assume machine with 32 bit word size, twos complement integers For each of the following C expressions, either: Argue that is true for all argument values Give example where not true 1. x < 0 Initialization ((x*2) < 0)) < 0) 2) < 0). ux >= 0 3. x & 7 == 7 (x<<30) < 0 int x = foo(); 4. ux > -1

int y = bar(); 5. x > y unsigned ux = x; 6. x * x >= 0 unsigned uy = y; 7. x > 0 && y > 0 x + y > 0 2 -x < -y 8. x >= 0 -x <= 0 9. x <= 0 -x >= 0 EECS213, S08 Encoding Integers Unsigned B2U(X ) w 1 xi 2 Twos Complement i B2T (X ) xw 1 2 i0 w 1 w 2 xi 2 i i0 short int x = 152) < 0)13; short int y = -152) < 0)13; Sign

Bit C short 2 bytes long x y Decimal 15213 -15213 Hex 3B 6D C4 93 Binary 00111011 01101101 11000100 10010011 Sign Bit For 2s complement, most significant bit indicates sign 0 for nonnegative 1 for negative 3 EECS213, S08 Encoding Example (Cont.) x = y = 4 Weight 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 -32768 Sum 152) < 0)13: 00111011 01101101 -152) < 0)13: 11000100 10010011

15213 1 1 0 0 1 4 1 8 0 0 1 32 1 64 0 0 1 256 1 512 0 0 1 2048 1 4096 1 8192 0 0 0 0 15213 -15213 1 1 1 2 0 0 0 0 1 16 0 0 0 0 1 128 0 0 0 0

1 1024 0 0 0 0 0 0 1 16384 1 -32768 -15213 EECS213, S08 Numeric Ranges Unsigned Values UMin = 0 Twos Complement Values TMin = 2w1 0000 UMax 1000 = 2w 1 1111 TMax = 2w1 1 0111 Other Values Minus 1 1111 Values for W = 16 UMax TMax TMin

-1 0 5 Decimal 65535 32767 -32768 -1 0 Hex FF FF 7F FF 80 00 FF FF 00 00 Binary 11111111 11111111 01111111 11111111 10000000 00000000 11111111 11111111 00000000 00000000 EECS213, S08 Values for Different Word Sizes W UMax TMax TMin 8 255 127 -128 16 65,535 32,767 -32,768 32 4,294,967,295 2,147,483,647 -2,147,483,648 C Programming Observations |TMin | = TMax + 1

Asymmetric range UMax = 64 18,446,744,073,709,551,615 9,223,372,036,854,775,807 -9,223,372,036,854,775,808 #include Declares constants, e.g., ULONG_MAX LONG_MAX 2 * TMax + 1 LONG_MIN 6 Values platform-specific EECS213, S08 Unsigned & Signed Numeric Values X B2U(X) B2T(X) Equivalence 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 Same encodings for nonnegative values Uniqueness Every bit pattern represents unique integer value Each representable integer has unique bit encoding Can Invert Mappings U2B(x) = B2U-1(x)

Bit pattern for unsigned integer T2B(x) = B2T-1(x) Bit pattern for twos comp integer EECS213, S08 Casting Signed to Unsigned C Allows Conversions from Signed to Unsigned short int x = 152) < 0)13; unsigned short int ux = (unsigned short) x; short int y = -152) < 0)13; unsigned short int uy = (unsigned short) y; Resulting Value No change in bit representation Nonnegative values unchanged ux = 15213 Negative values change into (large) positive values uy = 50323 8 EECS213, S08 Relation between Signed & Unsigned Twos Complement Unsigned T2U T2B x B2U ux X Maintain Same Bit Pattern -

w1 ux + + + 0 +++ x +++ -++ +2w1 2w1 = 2*2w1 = 2w 9 ux x w x 2 x 0 x 0 EECS213, S08 Relation Between Signed & Unsigned Weight 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 Sum 10 uy

= -15213 1 1 1 2 0 0 0 0 1 16 0 0 0 0 1 128 0 0 0 0 1 1024 0 0 0 0 0 0 1 16384 1 -32768 -15213 y + 2 * 32768 = 50323 1 1 1 2 0 0 0 0 1 16 0 0 0 0

1 128 0 0 0 0 1 1024 0 0 0 0 0 0 1 16384 1 32768 50323 y + 65536 EECS213, S08 Signed vs. Unsigned in C Constants By default are considered to be signed integers Unsigned if have U as suffix 0U, 42) < 0)949672) < 0)59U Casting Explicit casting between signed & unsigned same as U2T and T2U int tx, ty; unsigned ux, uy; tx = (int) ux; uy = (unsigned) ty; Implicit casting also occurs via assignments and procedure calls tx = ux; uy = ty; 11 EECS213, S08 Casting Surprises Expression Evaluation

If mix unsigned and signed in single expression, signed values implicitly cast to unsigned Including comparison operations <, >, ==, <=, >= Examples for W = 32 Constant1 00 0U0U Relation Evaluation == unsigned < signed 0U > unsigned -2) < 0)147483648 > signed -2) < 0)147483648 < unsigned -2) < 0) > signed (unsigned) -1 -2) < 0) > unsigned

< unsigned -1 -1 -1 -1 00 0U 2) < 0)147483647 -2) < 0)147483648 2) < 0)147483647U -2) < 0)147483648 -1 -2) < 0) 2) < 0)147483647 2) < 0)147483647U -1 (unsigned) -1 2) < 0)147483647 2) < 0)147483647 12 Constant2 -2) < 0) 2) < 0)147483648U 2) < 0)147483648U EECS213, S08 Explanation of Casting Surprises 2s Comp. Unsigned Ordering Inversion

Negative Big Positive TMax 2s Comp. Range 13 0 1 2 TMin UMax UMax 1 TMax + 1 TMax Unsigned Range 0 EECS213, S08 Sign Extension Task: Given w-bit signed integer x Convert it to w+k-bit integer with same value Rule: Make k copies of sign bit: X = xw1 ,, xw1 , xw1 , xw2 ,, x0 w k copies of MSB X

X 14 k w EECS213, S08 Sign Extension Example short int x = 152) < 0)13; int ix = (int) x; short int y = -152) < 0)13; int iy = (int) y; Decimal Hex 15213 3B 15213 00 00 3B -15213 C4 -15213 FF FF C4 x ix y iy 15 Binary 6D 00111011 6D 00000000 00000000 00111011 93 11000100 93 11111111 11111111 11000100 Converting from smaller to larger integer data type C automatically performs sign extension 01101101 01101101 10010011 10010011 EECS213, S08

Justification For Sign Extension Prove Correctness by Induction on k Induction Step: extending by single bit maintains value Key observation: 2w1 = 2w +2w1 Look at weight of upper bits: X 2w1 xw1 xw1 + 2w1 xw1 X 2w = 2w1 xw1 w X X - -+ w+1 16 EECS213, S08 Why Should I Use Unsigned? Dont Use Just Because Number Nonzero C compilers on some machines generate less efficient code Easy to make mistakes (e.g., casting)

Few languages other than C supports unsigned integers Do Use When Need Extra Bits Worth of Range 17 Working right up to limit of word size EECS213, S08 Negating with Complement & Increment Claim: Following Holds for 2s Complement ~x + 1 == -x Complement Observation: ~x + x == 1111112 == -1 x 10011101 + ~x 01100010 -1 11111111 Increment 18 ~x + x + (-x + 1) == -1 + (-x + 1) ~x + 1 -x == EECS213, S08 Comp. & Incr. Examples x = 15213 Decimal

x 15213 ~x -15214 ~x+1 -15213 y -15213 Hex 3B 6D C4 92 C4 93 C4 93 Binary 00111011 01101101 11000100 10010010 11000100 10010011 11000100 10010011 0 0 ~0 ~0+1 19 Decimal 0 -1 0 Hex 00 00 FF FF 00 00 Binary 00000000 00000000 11111111 11111111 00000000 00000000 EECS213, S08 Unsigned Addition u v u+v

UAddw(u , v) Operands: w bits + True Sum: w+1 bits Discard Carry: w bits Standard Addition Function Ignores carry output Implements Modular Arithmetic s = 20 UAddw(u , v) = u + v mod 2w EECS213, S08 Visualizing Integer Addition Integer Addition 4-bit integers u, v Compute true sum Add4(u , v) Values increase linearly with u and v Forms planar surface Add4(u , v) Integer Addition 32 28 24 20 16

14 12 12 10 8 8 4 6 0 4 0 2 u 21 4 6 v 2 8 10 12 0 14 EECS213, S08 Visualizing Unsigned Addition Wraps Around If true sum 2w At most once True Sum 2w+1

Overflow UAdd4(u , v) 16 14 Overflow 12 10 8 2w 14 6 12 10 4 0 22 8 2 Modular Sum 6 0 v 4 0 u 2 4 6 2 8 10

12 0 14 EECS213, S08 Twos Complement Addition u v u+v TAddw(u , v) Operands: w bits + True Sum: w+1 bits Discard Carry: w bits TAdd and UAdd 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 23 Will give s == t EECS213, S08 Characterizing TAdd Functionality True Sum True sum requires w+1 bits 0 1111

Drop off MSB 0 1000 2w 1 0111 Treat remaining bits as 2s comp. integer 0 0000 0 0000 PosOver 1 1000 2w 1 1 0000 2w TAdd(u , v) >0 v <0 2w1 PosOver TAdd Result 1000 NegOver (NegOver) <0 u >0

(PosOver) NegOver 24 EECS213, S08 Visualizing 2s Comp. Addition NegOver Values 4-bit twos comp. Range from -8 to +7 Wraps Around If sum 2w1 Becomes negative At most once If sum < 2w1 Becomes positive At most once TAdd4(u , v) 8 6 4 2 0 6 -2 4 2 -4 0 -6 -2 -8

-4 -8 -6 -4 u 25 -2 v -6 0 2 4 -8 6 PosOver EECS213, S08 Detecting 2s Comp. Overflow Task 2w1 Given s = TAddw(u , v) Determine if s = Addw(u , v) Example int s, u, v; PosOver 2w 1 0 s = u + v; Claim

Overflow iff either: NegOver u, v < 0, s 0 (NegOver) u, v 0, s < 0 (PosOver) ovf = (u<0 == v<0) && (u<0 != s<0); 26 EECS213, S08 Multiplication 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 Twos complement min: x * y (2w1)*(2w11) = 22w2 + 2w1 Up to 2w1 bits Twos complement max: x * y (2w1) 2 = 22w2 Up to 2w bits, but only for (TMinw)2 Maintaining Exact Results 27 Would need to keep expanding word size with each product computed Done in software by arbitrary precision arithmetic packages EECS213, S08 Unsigned Multiplication in C Operands: w bits *

True Product: 2*w bits u v u v UMultw(u , v) Discard w bits: w bits Standard Multiplication Function Ignores high order w bits Implements Modular Arithmetic UMultw(u , v) 28 = u v mod 2w EECS213, S08 Unsigned vs. Signed Multiplication Unsigned Multiplication unsigned ux = (unsigned) x; unsigned uy = (unsigned) y; unsigned up = ux * uy Truncates product to w-bit number up = UMultw(ux, uy) Modular arithmetic: up = ux uy mod 2w Twos Complement Multiplication int x, y; int p = x * y; 29 Compute exact product of two w-bit numbers x, y

Truncate result to w-bit number p = TMultw(x, y) EECS213, S08 Unsigned vs. Signed Multiplication Unsigned Multiplication unsigned ux = (unsigned) x; unsigned uy = (unsigned) y; unsigned up = ux * uy Twos Complement Multiplication int x, y; int p = x * y; Relation 30 Signed multiplication gives same bit-level result as unsigned up == (unsigned) p EECS213, S08 Shift Operations (from the last class) Left Shift: x << y Shift bit-vector x left y positions Throw away extra bits on left Fill with 0s on right Right Shift: x >> y Logical shift Fill with 0s on left Arithmetic shift Replicate most significant bit on right Useful with twos complement integer representation 31

<< 3 00010000 Log. >> 2) < 0) 00011000 Arith. >> 2) < 0) 00011000 Shift bit-vector x right y positions Throw away extra bits on right Argument x 01100010 Argument x 10100010 << 3 00010000 Log. >> 2) < 0) 00101000 Arith. >> 2) < 0) 11101000 EECS213, S08 Power-of-2 Multiply with Shift Operation u << k gives u * 2k Both signed and unsigned Operands: w bits * True Product: w+k bits u 2k u k 2k 0 0 1 0 0 0

UMultw(u , 2k) Discard k bits: w bits 0 0 0 0 0 0 TMultw(u , 2k) Examples u << 3 == u * 8 u << 5 - u << 3 Most machines shift and add much faster than multiply == u * 2) < 0)4 Compiler generates this code automatically 32 EECS213, S08 Unsigned Power-of-2 Divide with Shift Quotient of Unsigned by Power of 2 u >> k gives u / 2k Uses logical shift k Operands: Division: Result: x

x >> 1 x >> 4 x >> 8 33 u / 2k 0 0 1 0 0 0 u / 2k 0 u / 2k 0 Division 15213 7606.5 950.8125 59.4257813 Binary Point Computed 15213 7606 950 59 Hex 3B 6D 1D B6 03 B6 00 3B . Binary 00111011 01101101 00011101 10110110 00000011 10110110

00000000 00111011 EECS213, S08 Signed Power-of-2 Divide with Shift Quotient of Signed by Power of 2 x >> k gives x / 2k Uses arithmetic shift Rounds wrong direction when u < 0 k Operands: x / Division: Result: y y >> 1 y >> 4 y >> 8 34 2k x / 2k RoundDown(x / 2k) Division -15213 -7606.5 -950.8125 -59.4257813 Binary Point 0 0 1 0 0 0 0 0

Computed -15213 -7607 -951 -60 Hex C4 93 E2 49 FC 49 FF C4 . Binary 11000100 10010011 11100010 01001001 11111100 01001001 11111111 11000100 EECS213, S08 Correct Power-of-2 Divide Quotient of Negative Number by Power of 2 Want x / 2k Compute as (x+2k-1)/ 2k (Round Toward 0) In C: (x + (1<> k Biases dividend toward 0 Case 1: No rounding k Dividend: u +2k +1 1 / 2k u / 2k Biasing has no effect 35

0 0 0 0 0 0 1 1 1 1 Divisor: 1 1 1 Binary Point 0 0 1 0 0 0 0 1 1 1 1 . 1 1 1 EECS213, S08 Correct Power-of-2 Divide (Cont.) Case 2: Rounding k Dividend: x +2k +1 1 0 0 0 1 1 1 1 Incremented by 1 Divisor: / 2k

x / 2k 0 0 1 0 0 0 0 1 1 1 1 Biasing adds 1 to final result 36 Binary Point . Incremented by 1 EECS213, S08 C Puzzles Taken from old exams Assume machine with 32 bit word size, twos complement integers For each of the following C expressions, either: Argue that is true for all argument values Give example where not true 1. x < 0 Initialization ((x*2) < 0)) < 0) 2) < 0). ux >= 0 3. x & 7 == 7 (x<<30) < 0 int x = foo(); 4. ux > -1 int y = bar(); 5. x > y

unsigned ux = x; 6. x * x >= 0 unsigned uy = y; 7. x > 0 && y > 0 x + y > 0 37 -x < -y 8. x >= 0 -x <= 0 9. x <= 0 -x >= 0 EECS213, S08

Recently Viewed Presentations

  • SEM+: a tool for concept mapping in the

    SEM+: a tool for concept mapping in the

    Thanks to ESIP for Funding Friday Support Domain thesauri offer more precise definition of concepts in a context. By using them, the SEM+ will be able to give a more accurate similarity score.
  • Introduction to Marketing - Duke University

    Introduction to Marketing - Duke University

    Agenda Marketing Planning PharmaSim The Purpose of Planning "Planning is everything, plans are nothing." General Eisenhower Planning is to a large extent the job of making things happen that would not otherwise occur.
  • eClaims for Claimant and Carrier Representatives

    eClaims for Claimant and Carrier Representatives

    Initial Action on a Claim: reporting and filing. Subsequent Action on a Claim: start/stop payments; summarize payments; filings regarding certain events and actions. Be cognizant of: look and feel changes, procedural changes, availability of precise data. Overview of eClaims. Reduces...
  • Establish a Positive Command Climate MQS II Training

    Establish a Positive Command Climate MQS II Training

    References FM 22-100 Army Leadership DA PAM 600-69 Command Climate Survey Handbook AR 600-20 Army Command Policy Outline Define command climate Assess the command climate to determine the health of your unit Apply the elements which contribute to a positive...
  • The Global: Ideas and Ideologies

    The Global: Ideas and Ideologies

    Historical Family Types The CLAN The Extended Family The Bi-lateral extended family Nuclear family Modified Extended Family Single Parent Family Same Sex Family Blended/Reconstituted or Step Family The Traditional Nuclear Family and New Alternatives legally married never married singlehood, nonmarital...
  • Perinatal Loss: A continuum of loss

    Perinatal Loss: A continuum of loss

    Define types of perinatal loss and frequency of occurrence for each type. Describe emotional responses to perinatal loss related to fetal/neonatal gestational age, culture, and religion . Describe unique aspects of perinatal loss, including the process of grief and mourning,...
  • Presentation Template - Sword &amp; Shield

    Presentation Template - Sword & Shield

    What is PowerShell? Windows PowerShell is an interactive object-oriented command environment with scripting language features that utilizes small programs called cmdlets to simplify configuration, administration, and management of heterogeneous environments in both standalone and networked typologies by utilizing standards-based remoting...
  • Enhancing Belongingness - Piedmont Technical College

    Enhancing Belongingness - Piedmont Technical College

    Cont'd. Roy Baumeister and Mark Leary (1995) "the need to belong is a fundamental human motivation…more precisely, the belongingness hypothesis is that human beings have a pervasive drive to form and maintain at least minimum quantity of lasting, positive, and...