PadhaikoAll subjects

Computer Arithmetic

Computer Organization and Architecture (ENCT 303)

Open in the Padhaiko app

5.1 ALU (Arithmetic and logic unit)

The Arithmetic and Logic Unit (ALU) is the computational core of the CPU that performs arithmetic (+, -, *, /), bitwise logical (AND, OR, XOR, NOT), and shift operations on binary data.

5.2 Integer representation: Sign-magnitude representation, two's complement representation, converting between different bit lengths, fixed-point representation

For an -bit integer :

  1. Unsigned Representation: Represents non-negative integers in with value .
  2. Sign-Magnitude Representation: The most significant bit is the sign bit (0 for positive, 1 for negative), and the remaining bits hold the unsigned magnitude:

Drawbacks: Two representations of zero (+0 and -0), and addition/subtraction require comparing signs and magnitudes separately.

  1. Two's Complement Representation: The standard computer integer representation where the sign bit carries weight :

Negation rule: Flip all bits (1's complement) and add : . Has a unique zero (00...0) and handles signed addition/subtraction with a single binary adder.

  1. Converting Between Different Bit Lengths (Sign Extension):
    • To widen an -bit two's complement integer to bits, replicate its sign bit () into all upper bit positions (sign extension). For example, 4-bit -3 (1101) sign-extended to 8 bits becomes 1111 1101 ().
    • To narrow from bits to bits, discard the upper bits—valid only if all discarded bits match the new sign bit .
  2. Fixed-Point Representation: Uses an implicit, fixed binary point separating integer bits ( bits) and fractional bits ( bits) in an bit word:

Hardware treats fixed-point numbers as ordinary integers scaled by .

5.3 Integer arithmetic

5.3.1 Addition and subtraction algorithm

In two's complement arithmetic:

5.3.2 Multiplication algorithm

Unsigned multiplication can use shift-and-add (A, Q, M, C registers), while signed two's complement multiplication uses Booth's Algorithm, which handles positive and negative numbers uniformly without pre-negating operands:

5.3.3 Division algorithm

Unsigned integer division (, yielding quotient and remainder ) uses two classical shift-and-subtract hardware algorithms with -bit registers A (initialized to 0), Q (dividend), M (divisor), and Count = n:

AspectRestoring DivisionNon-Restoring Division
ShiftShift A, Q left by 1 bit (SHL(A, Q))If A >= 0: SHL(A, Q) then A <- A - M
If A < 0: SHL(A, Q) then A <- A + M
Test & Quotient BitCompute A <- A - M. If A < 0, set Q_0 <- 0 and restore A <- A + M; else set Q_0 <- 1If A >= 0, set Q_0 <- 1; else set Q_0 <- 0
Final CorrectionNone needed (A is always non-negative)After cycles, if A < 0, perform one final A <- A + M
EfficiencyUp to additions/subtractions per cycleStrictly addition or subtraction per cycle (faster)

5.4 Floating-point arithmetic

5.4.1 Floating-point representation: Principles, IEEE standard for binary floating-point arithmetic algorithm

Scientific computation spans tiny fractions and huge magnitudes that fixed-point integers cannot hold. A floating-point number encodes a value in normalized binary scientific form:

where is the sign bit (0 = positive, 1 = negative), is the biased exponent, and is the fractional significand (mantissa) with an implicit leading 1 for normal numbers.

IEEE 754 Binary Floating-Point Formats
FormatTotal BitsSign ()Exponent ()BiasFraction ()Approx. Normal Range
Single Precision (binary32) to
Double Precision (binary64) to

Special IEEE 754 Encodings:

5.4.2 Addition and subtraction algorithm

Adding or subtracting two floating-point numbers proceeds in four stages:

  1. Zero Check: If either operand is , return the other (adjusted for sign).
  2. Align Significands (Exponents Equalized): Compare exponents and ; shift the significand of the number with the smaller exponent right by bits while incrementing its exponent until .
  3. Add or Subtract Significands: Add (if effective signs match) or subtract (if effective signs differ) the aligned significands; if negative, take two's complement and flip result sign.
  4. Normalize & Round: Shift the resulting significand left (decrementing exponent) or right by 1 if carry-out occurred (incrementing exponent) until in 1.F form; check for exponent overflow / underflow and round (e.g., round to nearest even).

5.4.3 Multiplication algorithm

Multiplying does not require exponent alignment:

  1. Zero Check: If or , return .
  2. Compute Result Sign: .
  3. Add Biased Exponents: (subtracting once because both and already include ). Check overflow/underflow.
  4. Multiply Significands: Multiply the two unsigned -bit significands ( bits for single precision).
  5. Normalize & Round: Since , their product lies in ; at most one right shift by 1 bit (with ) normalizes it into , followed by rounding.

5.4.4 Division algorithm

Dividing mirrors multiplication:

  1. Zero / Infinity Check: If and , return ; if and , raise divide-by-zero (); if both , return NaN.
  2. Compute Result Sign: .
  3. Subtract Biased Exponents: (adding back since ). Check overflow/underflow.
  4. Divide Significands: Divide .
  5. Normalize & Round: Since , at most one left shift by 1 bit (with ) restores normalized 1.F form, followed by rounding.

Worked Out Examples

Example 1

1 (6 marks)

Multiply ( in 4-bit two's complement) by ( in 4-bit two's complement) using 4-bit Booth's Multiplication Algorithm, showing A, Q, Q_{-1}, and the operation at every cycle.

Setting up Booth's registers ( bits):

  • (), so ().
  • Initialize A = 0000, Q = 0101, Q_{-1} = 0, Count = 4.

Tracing the 4 cycles of Booth's algorithm:

4-Bit Booth's Trace for (-6) x (+5)
CycleOperationAQQ_{-1}
InitInitialize000001010
1(1,0): A <- A - M (0000 + 0110)011001010
ASR(A, Q, Q_{-1})001100101
2(0,1): A <- A + M (0011 + 1010)110100101
ASR(A, Q, Q_{-1})111010010
3(1,0): A <- A - M (1110 + 0110)010010010
ASR(A, Q, Q_{-1})001001001
4(0,1): A <- A + M (0010 + 1010)110001001
ASR(A, Q, Q_{-1})111000100

Verifying the 8-bit two's complement product: Reading AQ = 1110 0010_2: Because the MSB is 1, take the two's complement magnitude: , so AQ = -30.

Answer:

The 8-bit product is 1110 0010, matching .

Example 2

2 (6 marks)

Divide unsigned dividend (1101_2) by divisor (0011_2) using the 4-bit Restoring Division Algorithm, showing A, Q, and the restoring action at each cycle.

Initializing 5-bit accumulator A (with sign bit) and 4-bit Q:

  • A = 00000, Q = 1101, M = 00011 (), -M = 11101 ( in 5-bit two's complement).

Tracing the 4 restoring division cycles:

4-Bit Restoring Division Trace for 13 / 3
CycleActionA (5-bit)Q (4-bit)
InitInitialize000001101
1SHL(A, Q)00001101_
A <- A - M (00001 + 11101)11110 ()101_
Q_0 <- 0; Restore A <- A + M000011010
2SHL(A, Q)00011010_
A <- A - M (00011 + 11101)00000 ()010_
Q_0 <- 1 (no restore)000000101
3SHL(A, Q)00000101_
A <- A - M (00000 + 11101)11101 ()101_
Q_0 <- 0; Restore A <- A + M000001010
4SHL(A, Q)00001010_
A <- A - M (00001 + 11101)11110 ()010_
Q_0 <- 0; Restore A <- A + M000010100

Reading quotient and remainder:

  • Quotient
  • Remainder ().
Answer:

Quotient and Remainder .

Example 3

3 (5 marks)

Convert the decimal number into IEEE 754 Single-Precision (32-bit) binary and hexadecimal representation.

Converting magnitude to binary:

  • Integer part: .
  • Fractional part: .
  • Combined binary: .

Normalizing and finding biased exponent: Shift the binary point 4 places left:

  • Sign bit (since the number is negative).
  • Biased exponent .
  • Fraction field (23 bits after the implicit 1.): 10011000000000000000000.

Assembling the 32-bit IEEE 754 word and hex value: S | E (8 bits) | F (23 bits) = 1 | 10000011 | 10011000000000000000000 Grouping into nibbles (4 bits each): 1100 0001 1100 1100 0000 0000 0000 0000 = C1CC 0000H.

Answer:

32-bit binary: 1 10000011 10011000000000000000000; hexadecimal: C1CC0000H.

Exercises

Exercise — Computer Arithmetic

Question 1

Represent in 8-bit sign-magnitude and 8-bit two's complement form. Then sign-extend the 8-bit two's complement representation to 12 bits and verify its decimal value.

Finding 8-bit representations of : First write :

  • 8-bit Sign-Magnitude: Set the sign bit to 1 while keeping magnitude 0101101: 1010 1101.
  • 8-bit Two's Complement: Invert all bits of 0010 1101 (1101 0010) and add 1: 1101 0011.

Sign-extending to 12 bits and verifying: Replicate the MSB (1) into the upper 4 bits: 1111 1101 0011. Evaluating in two's complement: .

Answer:

8-bit sign-magnitude: 10101101; 8-bit two's complement: 11010011; 12-bit sign-extended two's complement: 111111010011 ().

Question 2

Multiply (0111_2) by (1011_2) using 4-bit Booth's algorithm, showing the complete register table (A, Q, Q_{-1}) for all 4 cycles.

Setting up Booth's registers:

  • (), ().
  • A = 0000, Q = 1011, Q_{-1} = 0.

Tracing the 4 Booth cycles:

  • Cycle 1 (Q_0 Q_{-1} = 10): A <- A - M = 1001; ASR A = 1100, Q = 1101, Q_{-1} = 1.
  • Cycle 2 (Q_0 Q_{-1} = 11): No arithmetic; ASR A = 1110, Q = 0110, Q_{-1} = 1.
  • Cycle 3 (Q_0 Q_{-1} = 01): A <- A + M = 1110 + 0111 = 0101; ASR A = 0010, Q = 1011, Q_{-1} = 0.
  • Cycle 4 (Q_0 Q_{-1} = 10): A <- A - M = 0010 + 1001 = 1011; ASR A = 1101, Q = 1101, Q_{-1} = 1.

Final product AQ = 1101 1101_2, whose two's complement magnitude is 0010 0011_2 = 35, i.e., .

Answer:

The 8-bit two's complement product is 1101 1101.

Question 3

Divide unsigned (1011_2) by (0011_2) using the 4-bit Non-Restoring Division Algorithm. Show A (5-bit), Q (4-bit), and the final remainder correction if needed.

Initializing registers: A = 00000, Q = 1011, M = 00011 (), -M = 11101 ().

Tracing the 4 non-restoring cycles:

  • Cycle 1 (A >= 0): SHL(A,Q) A=00001, Q=011_; A <- A - M = 11110 () Q_0 <- 0 (Q=0110).
  • Cycle 2 (A < 0): SHL(A,Q) A=11100, Q=110_; A <- A + M = 11111 () Q_0 <- 0 (Q=1100).
  • Cycle 3 (A < 0): SHL(A,Q) A=11111, Q=100_; A <- A + M = 00010 () Q_0 <- 1 (Q=1001).
  • Cycle 4 (A >= 0): SHL(A,Q) A=00101, Q=001_; A <- A - M = 00010 () Q_0 <- 1 (Q=0011).

Since A = 00010 >= 0 at the end, no final restoration step is needed. Quotient , Remainder .

Answer:

Quotient and Remainder .

Question 4

Decode the 32-bit IEEE 754 single-precision hexadecimal word 41C80000H into its decimal value, and briefly outline the four steps of floating-point addition.

Decoding 41C80000H: Expand to 32 binary bits: 0100 0001 1100 1000 0000 0000 0000 0000.

  • Sign bit (positive).
  • Biased exponent true exponent .
  • Fraction .
  • Value: .

Outlining floating-point addition steps:

  1. Check if either operand is zero.
  2. Align significands by shifting the smaller-exponent operand's mantissa right until exponents match.
  3. Add (or subtract) the aligned significands.
  4. Normalize the result into 1.F form, handle exponent overflow/underflow, and round.
Answer:

41C80000H represents . Floating-point addition follows zero-check, exponent alignment, significand addition, and normalization/rounding.

Question 5

Explain why floating-point multiplication subtracts Bias when adding biased exponents, whereas floating-point division adds Bias when subtracting biased exponents. Illustrate with two normalized IEEE 754 single-precision numbers having unbiased exponents and .

Deriving biased exponent rules for multiplication and division: Let and (with for single precision):

  • Multiplication: We want biased exponent . Simply adding double-counts the bias, so we compute:
  • Division: We want biased exponent . Subtracting cancels the bias completely, so we must add it back:

Illustrating with () and ():

  • Product exponent: (unbiased ).
  • Quotient exponent: (unbiased ).
Answer:

Multiplication subtracts Bias once because contains , while division adds Bias because cancels Bias. For () and (), () and ().

← Memory SystemPipelining and Vector Processing →