[Computer Architecture] Arithmetic for computers

Integer Addition

  0111   (+7)
+ 0110   (+6)
------

carry 1
  0111
+ 0110
------
    01

여기서 carry는 다음 자리 수 올림이라 보면 된다.

Overflow

양수 + 양수인데 결과 sign bit가 1이면 overflow
음수 + 음수인데 결과 sign bit가 0이면 overflow

  01111111   (+127)
+ 00000001   (+1)
-----------
  10000000

Integer Substraction

뺄셈은 직접 빼지 않고, 2의 보수로 변환 후 계산한다.
여기서 2의 보수는 2만큼 보충해야 되는 수를 의미한다.

A - B = A + (-B)

$-B$ 는

B의 bits를 반전
1을 더함

예를 들어 $7-6$ 을 구한다고 하면,

+7 = 00000111
+6 = 00000110

여기서 6을 음수로 변환한다.

비트 반전

00000110 -> 11111001

1 더하기

11111001
+00000001
---------
11111010

이제 여기서 계산하면 된다.

  00000111
+ 11111010
----------
1 00000001

Multiplication

\text{Multiplicand} \times \text{Multiplier}

Multiplicand: 계속 더해지는 수
Multiplier: 각 bit를 보면서 몇 번 더할지 결정하는 수

이진수 곱셈은 multiplier의 각 bit를 보면서
해당 bit가 $1$ 이면, multiplicand를 더하고.
$0$ 이면, 아무것도 안한다.
그리고 한 칸씩 shift한다.

예를 들어 다음 수식을 계산해 보자.

1000_2 \times 1001_2

맨 오른쪽 bit부터 본다. (i.e. Big endian)

   1000
×  1001
--------
   1000
  0000
 0000
1000
--------
1001000

즉 결과는 $1001000_2 = 72$ 이다.
결과를 보면 알겠지만, 길이가 2배가 되었다.
그래서 n-bit x n-bit = 2n이 필요하다.

Improved Multiplier

Product 회로가 Right shift를 수행하기 때문에 곱셈하면서 오른쪽 레지스터까지 사용할 경우가 없다.
때문에 오른쪽 부분에 multiplier를 배치함으로써, 회로 최적화가 가능하다.

                 +-------------------+
Multiplicand --->| Multiplicand Reg  |-------------------+
                 +-------------------+                   |
                                                         v
                                                   +-----------+
                                                   |   Adder   |
                                                   +-----------+
                                                         |
                                                         v
        +---------------------------------------------------------------+
        |                 Product / Multiplier Register                 |
        |   [ upper half: partial product | lower half: multiplier ]    |
        +---------------------------------------------------------------+
                                   |
                                   v
                            Right Shift Control

Division

\text{Dividend} = \text{Quotient} \times \text{Divisor} + \text{Remainder}

Quotient: 몫
Divisor: 나누는 수
Remainder: 나머지s

예를 들어 다음 수를 계산해 보자.

1001010_2 \div 1000_2

       1001
1000 ) 1001010
       -1000
        ----
          10

$74 \div 8 = 9 \cdots 2$ 즉 remainder는 $2$ 이다.

곱셈은 결과를 뱉으면 끝인데, 나눗셈은 조금 다르다.
나눗셈은 divisor를 빼고 양수면 몫이라 판단하고, 음수면 몫이 아니라 판단하기 때문에 빼고 복구하는 작업이 추가적으로 필요하다.

1. shift
2. subtract divisor
3. if result >= 0:
       quotient bit = 1
   else:
       restore
       quotient bit = 0

Floating Point

IEEE 754 Floating-Point Format

single 4-byte(32 bits) 기준

|  S   | Exponent | Fraction |
| 1bit |   8bits  |  23bits  |

Bias: 127

double 8-byte(64 bits) 기준

|  S   | Exponent | Fraction |
| 1bit |  11bits  |  52bits  |

Bias: 1023

X = (-1)^S \times (1+\text{Fraction}\times 2^{(\text{Exponent - Bias})})

Fraction: 소수 부분
Exponent: 2를 몇 번 곱할지 정함
Bias: 음수를 위해 필요함

음수처리를 위해 Bias를 사용한다.
예를 들어 single precision 기준에서, exponent가 $-2$ 이면 $127+(-2)$ 로 저장된다.
때문에 실제 사용할 때 bias 만큼 빼주어야 한다.

이를 이해했다면 실제 exponent 범위를 알 수 있다.

-126 \leq E_{actual} \leq 127

여기서 왜? $-127$ 이 아니고, $-126$ 인지 의문이 든다.
IEEE 754 기준에서 exponent가 $0$ 인 값은 special case로 처리되어서,
최소 $1$ 부터 시작이기 때문이다.

1 - 127 = -126