Computer Arithmetic
Open in the Padhaiko app5.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.
- Inputs: Two operand buses ( and , supplied from registers or memory buffers), an operation-select code (
OPRfrom the control unit), and incoming carry/shift bits. - Outputs: Result bus routed back to destination registers and status flags (
C,Z,S,V,P) latched into the Program Status Word (PSW). - Internal Design: Built from combinational parallel adders (ripple-carry or carry-lookahead adders), multiplexers, logic gates, and barrel shifters; integer numbers are represented in two's complement so the same binary adder handles both addition and subtraction.
5.2 Integer representation: Sign-magnitude representation, two's complement representation, converting between different bit lengths, fixed-point representation
For an -bit integer :
- Unsigned Representation: Represents non-negative integers in with value .
- Sign-Magnitude Representation: The most significant bit is the sign bit (
0for positive,1for 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.
- 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.
- 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 becomes1111 1101(). - To narrow from bits to bits, discard the upper bits—valid only if all discarded bits match the new sign bit .
- 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
- 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:
- Addition (): Feed and into an -bit binary adder and discard any carry-out beyond bit .
- Subtraction (): Compute using the same adder by inverting 's bits and setting carry-in .
- Overflow Rule: Signed overflow occurs if and only if the two operands added together have the same sign and the result has the opposite sign (equivalently, ). Subtraction overflows only if and have opposite signs and the result takes 's sign.
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:
- Registers for -bit multiplicand and multiplier :
A <- 0( bits),Q <- multiplier( bits),Q_{-1} <- 0(1 bit),M <- multiplicand( bits),Count <- n.
- Inspect the two-bit pair
(Q_0, Q_{-1})in each cycle:00or11: No arithmetic op; perform Arithmetic Shift Right (ASR) onA, Q, Q_{-1}.10(beginning of a run of1s):A <- A - M, thenASR(A, Q, Q_{-1}).01(end of a run of1s):A <- A + M, thenASR(A, Q, Q_{-1}).
- Decrement
Count; after cycles, the -bit signed product sits inA Q.
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:
| Aspect | Restoring Division | Non-Restoring Division |
|---|---|---|
| Shift | Shift A, Q left by 1 bit (SHL(A, Q)) | If A >= 0: SHL(A, Q) then A <- A - MIf A < 0: SHL(A, Q) then A <- A + M |
| Test & Quotient Bit | Compute A <- A - M. If A < 0, set Q_0 <- 0 and restore A <- A + M; else set Q_0 <- 1 | If A >= 0, set Q_0 <- 1; else set Q_0 <- 0 |
| Final Correction | None needed (A is always non-negative) | After cycles, if A < 0, perform one final A <- A + M |
| Efficiency | Up to additions/subtractions per cycle | Strictly 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.
| Format | Total Bits | Sign () | Exponent () | Bias | Fraction () | Approx. Normal Range |
|---|---|---|---|---|---|---|
Single Precision (binary32) | to | |||||
Double Precision (binary64) | to |
Special IEEE 754 Encodings:
- : Zero ().
- : Subnormal (denormalized) numbers for gradual underflow.
- (single) / (double), : Infinity ().
- / , : NaN (Not a Number, e.g., or ).
5.4.2 Addition and subtraction algorithm
Adding or subtracting two floating-point numbers proceeds in four stages:
- Zero Check: If either operand is , return the other (adjusted for sign).
- 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 .
- 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.
- Normalize & Round: Shift the resulting significand left (decrementing exponent) or right by 1 if carry-out occurred (incrementing exponent) until in
1.Fform; check for exponent overflow / underflow and round (e.g., round to nearest even).
5.4.3 Multiplication algorithm
Multiplying does not require exponent alignment:
- Zero Check: If or , return .
- Compute Result Sign: .
- Add Biased Exponents: (subtracting once because both and already include ). Check overflow/underflow.
- Multiply Significands: Multiply the two unsigned -bit significands ( bits for single precision).
- 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:
- Zero / Infinity Check: If and , return ; if and , raise divide-by-zero (); if both , return
NaN. - Compute Result Sign: .
- Subtract Biased Exponents: (adding back since ). Check overflow/underflow.
- Divide Significands: Divide .
- Normalize & Round: Since , at most one left shift by 1 bit (with ) restores normalized
1.Fform, followed by rounding.
Worked Out Examples
1
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:
| Cycle | Operation | A | Q | Q_{-1} |
|---|---|---|---|---|
| Init | Initialize | 0000 | 0101 | 0 |
| 1 | (1,0): A <- A - M (0000 + 0110) | 0110 | 0101 | 0 |
ASR(A, Q, Q_{-1}) | 0011 | 0010 | 1 | |
| 2 | (0,1): A <- A + M (0011 + 1010) | 1101 | 0010 | 1 |
ASR(A, Q, Q_{-1}) | 1110 | 1001 | 0 | |
| 3 | (1,0): A <- A - M (1110 + 0110) | 0100 | 1001 | 0 |
ASR(A, Q, Q_{-1}) | 0010 | 0100 | 1 | |
| 4 | (0,1): A <- A + M (0010 + 1010) | 1100 | 0100 | 1 |
ASR(A, Q, Q_{-1}) | 1110 | 0010 | 0 |
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.
The 8-bit product is 1110 0010, matching .
2
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:
| Cycle | Action | A (5-bit) | Q (4-bit) |
|---|---|---|---|
| Init | Initialize | 00000 | 1101 |
| 1 | SHL(A, Q) | 00001 | 101_ |
A <- A - M (00001 + 11101) | 11110 () | 101_ | |
Q_0 <- 0; Restore A <- A + M | 00001 | 1010 | |
| 2 | SHL(A, Q) | 00011 | 010_ |
A <- A - M (00011 + 11101) | 00000 () | 010_ | |
Q_0 <- 1 (no restore) | 00000 | 0101 | |
| 3 | SHL(A, Q) | 00000 | 101_ |
A <- A - M (00000 + 11101) | 11101 () | 101_ | |
Q_0 <- 0; Restore A <- A + M | 00000 | 1010 | |
| 4 | SHL(A, Q) | 00001 | 010_ |
A <- A - M (00001 + 11101) | 11110 () | 010_ | |
Q_0 <- 0; Restore A <- A + M | 00001 | 0100 |
Reading quotient and remainder:
- Quotient
- Remainder ().
Quotient and Remainder .
3
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.
32-bit binary: 1 10000011 10011000000000000000000; hexadecimal: C1CC0000H.
Exercises
Exercise — Computer Arithmetic
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
1while keeping magnitude0101101:1010 1101. - 8-bit Two's Complement: Invert all bits of
0010 1101(1101 0010) and add1: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: .
8-bit sign-magnitude: 10101101; 8-bit two's complement: 11010011; 12-bit sign-extended two's complement: 111111010011 ().
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;ASRA = 1100,Q = 1101,Q_{-1} = 1. - Cycle 2 (
Q_0 Q_{-1} = 11): No arithmetic;ASRA = 1110,Q = 0110,Q_{-1} = 1. - Cycle 3 (
Q_0 Q_{-1} = 01):A <- A + M = 1110 + 0111 = 0101;ASRA = 0010,Q = 1011,Q_{-1} = 0. - Cycle 4 (
Q_0 Q_{-1} = 10):A <- A - M = 0010 + 1001 = 1011;ASRA = 1101,Q = 1101,Q_{-1} = 1.
Final product AQ = 1101 1101_2, whose two's complement magnitude is 0010 0011_2 = 35, i.e., .
The 8-bit two's complement product is 1101 1101.
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 .
Quotient and Remainder .
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:
- Check if either operand is zero.
- Align significands by shifting the smaller-exponent operand's mantissa right until exponents match.
- Add (or subtract) the aligned significands.
- Normalize the result into
1.Fform, handle exponent overflow/underflow, and round.
41C80000H represents . Floating-point addition follows zero-check, exponent alignment, significand addition, and normalization/rounding.
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 ).
Multiplication subtracts Bias once because contains , while division adds Bias because cancels Bias. For () and (), () and ().