This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

Chapter 2: Arithmetic Methods and Arithmetic Units

2.1 Number Systems and Encoding

I. Positional Number Systems and Mutual Conversions

Conversion between decimal and radix-R number systems R-to-decimal conversion:

$\sum\_{i = n}^{-m} k_i × r^i$ e.g., Binary to decimal conversion

//二转十
int bToD(char str[]) {
    int sum = 0;
    for(int i = 0; str[i] != '\0'; i++) {
        sum = sum*2 + (str[i] - '0');
    }
    return sum;
}

Decimal-to-R conversion:

• Integer part: divide by r and take the remainder, where r is the radix
• Fractional part: multiply by r and take the integer part. Code as follows:

//将十进制数n转化为k进制整数
void dToK(int n, int k, char str[]) {
    int i = 0;
    if (n == 0) {
        str[0] = '0';
        return;
    }
    while(n) {
        str[i++] =n % k + '0';
        n = (n-n % k) / k;
    }
    i--;
    //reverse
    for (int j = 0; j < i; j++,i--) {
        char t = str[j];
        str[j] = str[i];
        str[i] = t;
    }
}

II. True Value and Machine Number

• True value: The number as normally written
• Machine code: The number as represented in the machine, which must address issues of representing positive/negative signs and decimal point operations within the computer.

III. BCD Code

Each digit of a BCD-encoded decimal number has a definite weight in its binary representation. The commonly used 8421 code has weights of 8, 4, 2, and 1 from high to low for its 4 binary digits. 0000, 0001, ..., 1001 represent 0, 1, ..., 9 respectively. Within each digit, binary rules apply, while between digits, decimal rules apply. Hence this encoding is called "Binary Coded Decimal (BCD) code."

Note! BCD code values range from 0000 to 1001 (i.e., decimal 0 to 9) Sometimes addition or subtraction of BCD codes produces values outside this range, requiring manual adjustment to obtain correct results.

The correction rules for BCD addition operations implemented within a computer are:

• If the sum of two single-digit BCD codes is less than or equal to (1001)₂, i.e., (9)₁₀, no correction is needed;

Example 1 ① 1+8 = 9
  0 0 0 1
+ 1 0 0 0
——————————
  1 0 0 1
No correction needed

• If the sum is greater than or equal to (10)₁₀, add-6 correction must be performed, with a carry to the higher digit. The carry can occur during the initial addition (Example 1 ③) or during correction (Example 1 ②).

Example 1 ② 4+9 = 13
  0 1 0 0
+ 1 0 0 1
——————————
  1 1 0 1
+ 0 1 1 0  correction
——————————
1 0 0 1 1
0001 0011 represents 13~
③ 9+7 = 16
  1 0 0 1
+ 0 1 1 1
——————————
1 0 0 0 0
+ 0 1 1 0 correction
——————————
1 0 1 1 0
0001 0110 represents 16~

IV. Characters and Character Strings

1. Representation of Characters and Character Strings

Symbol data: Character information is represented using data codes, such as ASCII Character representation method ASCII: Uses one byte, with the lower 7 bits for encoding (128 characters), and the highest bit as a parity bit, as shown:

Character string storage method: Occupies consecutive bytes in main memory, each byte stores one character.

2. Representation of Chinese Characters

First-level Chinese characters: 3755 characters; Second-level Chinese characters: 3008 characters Chinese character internal code: Machine code for storing, exchanging, and retrieving Chinese character information, composed of two bytes, with the high bit of each byte set to 1 (to distinguish from English characters) Chinese character font code: Character dot matrix patterns

V. Error Detection Codes (Key Topic)

Recommended videos: 3Blue1Brown's Hamming Code Part 1, 3Blue1Brown's Hamming Code Part 2. Very interesting! Although mainly about Hamming codes, they also provide detailed explanations of parity check codes. Error Detection Codes (only parity check codes are introduced)

Introduction

Information is susceptible to errors during transmission and processing due to interference and faults.

Solution

Add redundant information (check bits) to the valid information.

Definition

Let x=(x₀ x₁.x_n-1) be an n-bit word, then the even parity bit C is defined as: C=x₀ ^ x₁ ^ x₂ ^ ... ^x_n-1, where ^ represents bitwise addition, indicating that C=0 only when x contains an even number of 1s; otherwise C=1. This can only detect errors but cannot correct them. Odd parity can be similarly defined. Odd parity: C=0 only when there is an odd number of 1s; otherwise C=1

2.2 Fixed-Point Number Representation and Operations (Key Topic)

I. Fixed-Point Number Representation

1. Sign-Magnitude Representation

Fixed-point fraction x_n.x_n-1x_n-2……x₀, x is the true value

$$[x]_原 = \begin{cases} x, & \text{0 ≤ x < 1 i.e., x is positive} \\ 1-x, & \text{-1 < x ≤ 0 i.e., x is negative} \end{cases}$$

Range: 2^-n-1 to 1-2^-n e.g.: x = +0.1001, [x]sign-magnitude = 0.1001 x = -0.1001, [x]sign-magnitude = 1-(-0.1001)=1.1001

Fixed-point integer x_nx_n-1x_n-2……x₀, x is the true value

$$[x]_原 = \begin{cases} x, & \text{0 ≤ x < }2^n \text{ i.e., x is positive}\\ 2^n-x, & \text{-2}^n<x≤ 0 \text{ i.e., x is negative} \end{cases}$$

Range: 1-2ⁿ to 2ⁿ-1 e.g.: x = +1001, [x]sign-magnitude = 01001 x = -1001, [x]sign-magnitude = 2⁴+1001=11001 There is a distinction between positive 0 and negative 0!!

2. One's Complement Representation

Definition

• Positive numbers are represented the same as in sign-magnitude and two's complement.
• For negative numbers, the one's complement has sign bit 1, and the magnitude bits are the bitwise inverse of the sign-magnitude magnitude bits.
• Easy to implement in circuits, as flip-flop outputs have positive and negative states. For the mantissa inversion, the one's complement differs from two's complement by not adding 1 to the least significant bit, so the one's complement definition can be derived.

Fixed-point fraction x_n.x_n-1x_n-2……x₀, x is the true value

$$[x]_反 = \begin{cases} x, & \text{0 ≤ x < 1 i.e., x is positive} \\ (2-2^{-n})+x, & \text{-1 < x ≤ 0 i.e., x is negative} \end{cases}$$

e.g.: X1=+0.1011011, [X1]one's complement =0.1011011 X2= -0.1011011, [X2]one's complement =1.0100100 Fixed-point integer x_nx_n-1x_n-2……x₀, x is the true value

$$[x]_反 = \begin{cases} x, & \text{0 ≤ x < }2^n \text{ i.e., x is positive} \\ (2^{n+1}-1)+x, & \text{-2}^n<x≤ 0 \text{ i.e., x is negative} \end{cases}$$

One's complement has a distinction between positive 0 and negative 0!!

3. Two's Complement Representation

Definition The two's complement of a positive number is the number itself. The two's complement of a negative number is the original negative number plus the modulus (invert all bits of the negative number except the sign bit, then add 1). Computer arithmetic is bounded by word length and belongs to modular arithmetic. The greatest advantage of two's complement is converting subtraction to addition. Fixed-point fraction x_nx_n-1x_n-2……x₀, with modulus 2

$$[x]_补 = \begin{cases} x, & \text{0 ≤ x < 1 i.e., x is positive} \\ 2+x, & \text{-1 < x ≤ 0 i.e., x is negative} \end{cases}$$

e.g.: x= -0.1011, [x]two's complement=10+x=10.0000-0.1011=1.0101

y=-0.01111 [y]two's complement=10+y=10.00000-0.01111=1.10001 Fixed-point integer xnxn-1xn-2……x0, with modulus 2ⁿ⁺¹

$$[x]_补 = \begin{cases} x, & \text{2}^n {＞x ≥ 0 \text{ i.e., x is positive}} \\ 2^{n+1}+x, & \text{0 ≥ x > -2}^n \text{ i.e., x is negative} \end{cases}$$

Properties of two's complement:

• The high bit indicates sign
• For positive numbers, the mantissa is the same as sign-magnitude
• Range: -2ⁿ to 2ⁿ-1 (fixed-point integers)
• No distinction between positive zero and negative zero!!

4. Biased Representation (Excess Code)

Used in exponent fields. Its characteristic is that biased and two's complement share the same mantissa, with opposite sign bits. Range: -2ⁿ to 2ⁿ-1 e.g.: True value -1011111 Sign-magnitude: 11011111 Two's complement: 10100001 One's complement: 10100000 Biased: 00100001

5. Summary

• If x is positive, [x]_{sign-magnitude} = [x]two's complement = [x]one's complement
• If x is negative, the sign-magnitude sign bit remains 1, invert each binary digit of the integer to get the one's complement, keep the sign bit unchanged, and add 1 to the least significant bit of the one's complement value to get the two's complement.
• Biased and two's complement share the same mantissa, with opposite sign bits

II. Fixed-Point Number Operations (Key Topic)

Computer Organization: Fixed-Point Operations - Shift, Add, Subtract, Multiply, Divide

1. Shift Operations on Fixed-Point Numbers

Shifting in computers means data shifts relative to the decimal point (left or right shift); the data moves while the decimal point position does not change.

Signed Number Shifts

Left shift by 1: The absolute value of the true value corresponding to the machine number becomes 2 times the original Right shift by 1: The absolute value of the true value corresponding to the machine number becomes 1/2 of the original During shifting, filling vacated positions:

• The magnitude part of negative numbers is the same as the true value

  

Unsigned Number Shifts

• Logical left shift: Fill low bits with 0, high bits are shifted out
• Logical right shift: Fill high bits with 0, low bits are shifted out

e.g.: 01010011 Logical left shift: All bits participate in the shift, high bit 0 is shifted out, lowest bit filled with 0: 10100110 Arithmetic left shift: The first 0 is the sign bit, indicating a positive number. The sign bit does not participate in the shift; what shifts is the subsequent data: 00100110

e.g.: 10110010 Logical right shift: All bits participate in the shift, vacated highest bit filled with 0, lowest bit discarded: 01011001 Arithmetic right shift: The highest bit does not participate in the shift (sign bit), indicating a negative number. Right shift fills the vacated highest bit with 1, the rightmost 0 is discarded: 11011001

2. Two's Complement Addition and Subtraction

Two's Complement Addition

Formula: $[x+y]*补=[x]*补+[y]\_补 (mod 2^{n+1}) \\ |x|<(2n-1) , |y|<(2n-1) , |x+y|<(2n-1)$ The formula states: Under modulus 2ⁿ⁺¹, the sum of the two's complements of any two numbers equals the two's complement of the sum of those two numbers. Proof: (1) x > 0, y > 0, then x+y > 0. Since the sign-magnitude and two's complement of positive numbers are the same, [x]two's complement_+[y]two's complement = x+y = [x+y]two's complement

(2) x > 0, y < 0, then x+y > 0 or x+y < 0 [x]two's complement= x, [y]two's complement = 2ⁿ⁺¹+y [x]two's complement_+[y]two's complement = (x+y)+2ⁿ⁺¹ = [x+y]two's complement (mod 2ⁿ⁺¹)

(3) x < 0, y > 0, then x+y > 0 or x+y < 0 [x]two's complement= 2ⁿ⁺¹+x, [y]two's complement = y [x]two's complement_+[y]two's complement = (x+y)+2ⁿ⁺¹ = [x+y]two's complement (mod 2ⁿ⁺¹)

(4) x < 0, y < 0, then x+y < 0 [x]two's complement= 2ⁿ⁺¹+x, [y]two's complement = 2ⁿ⁺¹+y [x]two's complement_+[y]two's complement = 2ⁿ⁺¹+x + 2ⁿ⁺¹+y = 2ⁿ⁺¹+( 2ⁿ⁺¹+x+y) = [x+y]two's complement (mod 2ⁿ⁺¹)

e.g.: x=+1011, y=-0101, find x+y=? Solution: [x]two's complement = 01011, [y]two's complement = 11011 　　　　　[x]two's complement　　　0 1 0 1 1 　　+　　[y]two's complement　　　1 1 0 1 1 　　———————————————— 　　　　[x+y]two's complement　　1 0 0 1 1 0 Therefore x+y = +0110

1. The sign bit participates in the operation as part of the number.
2. Addition is performed under modulus 2n+1, i.e., carries exceeding 2n+1 are discarded.

Two's Complement Subtraction

To convert subtraction to addition, the following formula must be proven: $[x-y]*补=[x]*补-[y]*补 = [x]*补+[-y]\_补 (mod 2^{n+1})$ [x-y]two's complement= [x]two's complement- [y]two's complement=[x]two's complement+[-y]two's complement (Proof) To obtain [-y]two's complement simultaneously, we need to prove that [-y]two's complement=complement of [y]two's complement+2^-n (meaning [-y]two's complement equals [y]two's complement with all bits including the sign bit inverted, plus 1 at the least significant bit) Since [x]two's complement_+[y]two's complement = [x+y]two's complement Therefore [y]two's complement = [x+y]two's complement - [x]two's complement Also since [x-y]two's complement = [x+(-y)]two's complement = [x]two's complement_+[-y]two's complement Therefore [-y]two's complement = [x-y]two's complement - [x]two's complement Hence [y]two's complement + [-y]two's complement = [x+y]two's complement - [x]two's complement + [x-y]two's complement - [x]two's complement = [x+y+x-y]two's complement_-[x+x]two's complement = [x+x]two's complement - [x+x]two's complement = 0 Hence [-y]two's complement = -[y]two's complement (mod 2ⁿ⁺¹)

To find [-X]two's complement from [X]two's complement: invert all bits including the sign bit, then add 1 to the least significant bit

3. Fixed-Point Multiplication and Division

Multiplication

Division

Restoring remainder method: Subtract the divisor from the dividend. If the result is greater than 0, quotient bit is 1, left-shift the remainder. If the result is less than 0, quotient bit is 0, restore the remainder, then left-shift the remainder. Repeat the above operations until the quotient precision meets requirements.

Non-restoring remainder method (alternating addition-subtraction method)

• First step: If the dividend and divisor have the same sign, perform dividend minus divisor; if the dividend and divisor have different signs, perform dividend plus divisor
• If the remainder and divisor have the same sign, quotient bit is 1, left-shift the remainder, and subtract the divisor; if the remainder and divisor have different signs, quotient bit is 0, left-shift the remainder, and add the divisor
• The last quotient bit is always set to 1 (error 2-n); the remainder can be negative, and no remainder restoration is needed.

  

  e.g.: p44

  

4. Overflow Concept and Detection Methods

Overflow Concept

In a fixed-point integer machine, the number representation range is |x| < (2ⁿ-1). If during computation a value exceeding the word length absolute value appears, it is called "overflow." [Example 15] x=+1011, y=+1001, find x+y. Solution: [x]two's complement=01011, [y]two's complement=01001 　　　[x]two's complement　　　0 1 0 1 1 +　　[x]two's complement　　　0 1 0 0 1 —————————————— 　　[x+y]two's complement　　　1 0 1 0 0

The result of adding two positive numbers becomes negative, called overflow (positive overflow, the result exceeds the maximum positive number the machine can represent)

[Example 16] x=-1101, y=-1011, find x+y. Solution: [x]two's complement=10011, [y]two's complement=10101 　　　[x]two's complement　　　1 0 0 1 1 +　　[x]two's complement　　　1 0 1 0 1 —————————————— 　　[x+y]two's complement　　　0 1 0 0 0 The result of adding two negative numbers becomes positive, called underflow (the result is smaller than the minimum negative number the machine can represent)

Overflow Detection

Double Sign Bit Method (Modified Two's Complement)

Numbers participating in addition/subtraction use modified two's complement representation [x]two's complement=2ⁿ⁺²+x (mod 2ⁿ⁺²) [x+y]two's complement_=[x]two's complement_+[y]two's complement (mod 2ⁿ⁺²)

• Both sign bits participate in the operation
• Addition is under modulus 2ⁿ⁺², i.e., carries from the highest sign bit are discarded 　　　Sf1　SF2 　　　 0　　 0　　　Correct (positive number) 　　　 0 　1　　　Positive overflow 　　　 1 　　0　　　Negative overflow 　　　 1　　 1　　　Correct (negative number) When the two sign bits differ, it indicates overflow; when they are the same, there is no overflow. Regardless of overflow, Sf1 (the highest bit) represents the correct sign of the result

Practice Problems

2.3 Floating-Point Number Representation and Operations

I. Floating-Point Number Representation

Representation range of floating-point numbers

II. IEEE754 Standard

III. Floating-Point Addition and Subtraction

1. Check for 0 operands to see if operations can be simplified;
2. Compare exponents and perform exponent alignment (align the smaller exponent to the larger one);
3. Perform addition or subtraction on the mantissa;
4. Normalize the result and perform rounding.

Exponent Alignment

The process of making two numbers' exponents equal. Alignment principle: The number with the smaller exponent aligns to the number with the larger exponent. Alignment process: First, find the difference between exponents E_x and E_y to check if they are equal. If not, adjust E_x or E_y by shifting the mantissa, i.e., align so they become equal. The mantissa of the smaller exponent is right-shifted (equivalent to moving the decimal point left); for each right shift by one position, the exponent increases by 1, until the two exponents are equal. The number of right shifts equals the exponent difference.

Mantissa Addition

The method is exactly the same as fixed-point addition and subtraction.

Normalization

Floating-point normalization requires that the most significant bit of the mantissa field should be 1. Right-shifting the operation result to achieve normalization is called right normalization, and left-shifting is called left normalization.

Method for determining normalized numbers (single sign bit method)

• Sign-magnitude: Whether positive or negative, the first data bit is 1
• One's complement, two's complement: The sign bit and the first data bit differ

  

Rounding

Purpose of rounding: During exponent alignment or right normalization, the mantissa is right-shifted, and the shifted-out lower bits are discarded, causing some error. Rounding aims to reduce this error. IEEE754 standard rounding methods:

• Round to nearest (round half up): Similar to "round half up"; if the highest discarded bit is 1, add 1
• Round toward 0: Simple truncation
• Round toward +infinity: For positive numbers, if remaining bits are not all "0", add 1; for negative numbers, truncate
• Round toward -infinity: For negative numbers, if remaining bits are not all "0", add 1; for positive numbers, truncate

  

  

  

  

2.4 Arithmetic Logic Unit (ALU)

I. Serial Adder and Parallel Adder

The logic expressions for a one-bit full adder are: F_i = A_i XOR B_i XOR C_n+i C_n+i+1 = A_iB_i + A_iC_n+i + B_iC_n+i C is the carry Serial Adder

• Has only one full adder; data is serially fed bit by bit into the adder for computation. A carry flip-flop stores the carry signal for participation in the next operation.
• If the operand is n bits long, addition must be performed n times, each time producing one sum bit, which is serially sent back to the register bit by bit.

Parallel Adder

• A parallel adder consists of multiple full adders, with the number of bits equal to the machine's word length, and all bit positions operate simultaneously.
• The longest operation time of a parallel adder is mainly determined by the propagation time of carry signals.
• Each full adder in the parallel adder has a carry input from the lower bit and a carry output to the higher bit.
• Carry in parallel adders is usually either ripple carry or look-ahead carry.

II. ALU Functions and Structure

The ALU logic diagram is shown above F_i = X_i XOR Y_i XOR C_n+1 C_n+i+1 = X_iY_i + Y_iC_n+1 + X_iC_n+1 Different control parameters yield different combinational functions, enabling multiple arithmetic and logical operations.

The truth table showing the relationship between Xi, Yi, control parameters, and inputs is constructed as follows: