컴퓨터 산술 연산

CPU의 산술 연산은 데이터가 어떤 형식으로 표현되어 있느냐에 따라 알고리즘이 달라진다. 이 노트는 각 형식에서 덧셈·뺄셈·곱셈·나눗셈을 하드웨어로 어떻게 처리하는지 정리한다. 수의 표현 자체는 데이터의 표현을 참고한다.

산술 연산의 대상 데이터 형식

실제 컴퓨터는 보통 2의 보수 고정 소수점과 부동 소수점을 쓴다.

덧셈과 뺄셈

부호-절댓값 데이터

사람이 손으로 계산하는 방식과 비슷하다.

1. 두 수의 부호를 XOR로 비교한다. 0이면 같은 부호, 1이면 다른 부호다.
2. 같은 부호의 덧셈(또는 다른 부호의 뺄셈): 절댓값끼리 더하고 부호는 그대로 둔다. 결과가 비트 수를 넘으면 오버플로우다. 다른 부호끼리의 덧셈에서는 오버플로우가 생기지 않는다.
3. 다른 부호의 덧셈(또는 같은 부호의 뺄셈): 절댓값을 비교해 큰 쪽에서 작은 쪽을 빼고, 결과의 부호는 절댓값이 큰 쪽을 따른다. A < B인지 A > B인지에 따라 처리가 달라진다.

2의 보수 데이터

훨씬 단순하다. 부호 비트를 포함해 그냥 더한다.

1. 덧셈은 AC와 BR 레지스터의 값을 더해 AC에 넣는다. 맨 위에서 나온 올림수는 버린다. 뺄셈은 BR의 2의 보수를 더한다(A − B = A + (−B)).
2. 마지막 두 캐리를 비교해 오버플로우 여부만 확인한다. 4비트라면 V = C₄ ⊕ C₃이고, 뺄셈도 덧셈으로 하므로 같은 식을 쓴다.

이 덧셈을 하는 병렬 가산기는 비트 수만큼의 전가산기로 이뤄지고, 결과에 따라 C(올림수)·S(부호)·Z(0)·V(오버플로우) 플래그를 세트한다(CPU와 명령어 구조의 「상태 플래그」).

부호를 따로 비교할 필요가 없어서 대부분의 컴퓨터가 2의 보수를 쓴다.

곱셈

연속적인 시프트와 덧셈으로 한다. 사용하는 레지스터:

1. 두 수의 부호를 비교해 결과의 부호를 정한다(같으면 +, 다르면 −).
2. Q의 가장 오른쪽 비트를 확인해 1이면 AC에 BR을 더한다.
3. E, AC, Q를 한 덩어리로 오른쪽으로 시프트하고 SC를 1 줄인다.
4. SC가 0이 될 때까지 2~3을 반복한다. 최종 곱은 AC와 Q에 걸쳐 저장된다.

손으로 곱할 때 부분 곱을 한 칸씩 왼쪽으로 밀어 쓰는 것을, 하드웨어는 누적값을 오른쪽으로 미는 방식으로 구현한 것이다.

2의 보수 곱셈: 부스 알고리즘

위 방식은 부호를 따로 처리하는 부호-절댓값용이다. 2의 보수끼리는 부스 알고리즘(Booth's algorithm)으로 부호까지 한 번에 곱한다. 하드웨어는 위 승산기에 두 가지를 더한다. 피승수 레지스터 M과 가산기 사이의 보수기(뺄셈용), 그리고 Q 오른쪽에 붙이는 1비트 레지스터 Q₋₁이다.

1. A ← 0, Q₋₁ ← 0으로 시작한다.
2. Q의 최하위 비트 Q₀와 Q₋₁ 두 비트를 본다. 10이면 A ← A − M, 01이면 A ← A + M, 00·11이면 아무것도 하지 않는다.
3. A, Q, Q₋₁을 한 덩어리로 산술 오른쪽 시프트한다(부호 비트 유지).
4. 승수 비트 수만큼 2~3을 반복한다. 곱은 A:Q에 남는다.

3 × (−2), 4비트: M = 0011, Q = 1110
        A     Q     Q₋₁
시작   0000  1110   0
1회    0000  0111   0     Q₀Q₋₁=00 → 시프트만
2회    1110  1011   1     10 → A−M = 1101, 시프트
3회    1111  0101   1     11 → 시프트만
4회    1111  1010   1     11 → 시프트만
결과   A:Q = 11111010 = −6

승수에 1이 연속으로 이어진 구간은 시작과 끝에서만 덧셈·뺄셈을 하므로(…0111 0… = 1000 0… − 1), 1이 몰려 있는 승수에서 연산 횟수가 준다.

곱셈기를 회로로 둘 것인가: 복잡도와 속도의 교환

곱셈·나눗셈을 어디서 처리하느냐는 설계 선택이다.

회로를 더하면 칩이 복잡해지는 대신 그 연산이 빨라진다. 이 교환은 곱셈에서 끝나지 않는다. 범용 명령어로 수많은 클럭이 걸리는 일(벡터 연산, 암호화, 영상 압축 해제 등)은 전용 회로와 전용 명령어로 옮겨 가는 것이 컴퓨터 설계의 반복된 흐름이다(CPU와 명령어 구조).

나눗셈

연속적인 시프트와 뺄셈으로 한다. 하드웨어 구성은 곱셈과 같다.

1. 부호를 비교해 결과의 부호를 정한다.
2. 피제수에서 제수를 뺄 수 있는지 확인한다. 몫이 레지스터에 담기지 않을 만큼 크면 나눗셈 오버플로우(divide overflow) 로 처리한다(0으로 나누기 포함).
3. 왼쪽으로 시프트하며 제수를 빼 보고, 뺄 수 있으면 몫 비트를 1, 아니면 0으로 둔다.
4. 모든 비트에 대해 반복해 몫과 나머지를 얻는다.

부동 소수점 연산

수는 M × r^e(가수 M, 기수 r, 지수 e)로 표현하며, 가수용 레지스터와 지수용 레지스터를 함께 쓴다.

곱셈 예: (0.1011 × 2³) × (0.1001 × 2⁵)는 가수 곱 0.01100011, 지수 합 8이고, 정규화하면 0.1100011 × 2⁷이다.

연산 중 생길 수 있는 예외는 네 가지다.

정규화는 가수의 첫 비트가 1이 될 때까지 가수를 시프트하고, 시프트한 만큼 지수를 조정하는 과정이다. 덧셈의 네 단계는 그대로 산술 파이프라인의 세그먼트가 된다. 지수를 맞추며 밀려난 비트가 버려지는 데서 생기는 반올림 오차와 흡수·상쇄는 부동소수점 오차: 반올림·비교·누적에 있다.

십진 산술

BCD 가산기

4비트 이진 덧셈의 결과를 BCD로 보정한다. 두 BCD 자리와 캐리를 더한 이진 합이 9를 넘으면 6(0110)을 더해 올바른 BCD 자리와 캐리를 만든다. 보정 조건의 논리식과 회로는 디지털 논리 회로와 부품의 「BCD 가산기」에 있다.

BCD 감산기

빼는 수의 9의 보수를 구해 더하는 방식으로 뺄셈을 한다.

십진 연산

• 덧셈·뺄셈: BCD 가산기·감산기를 자릿수만큼 병렬로 연결한다. 예: 가산기 3개로 세 자리 10진수 연산.
• 곱셈·나눗셈: BCD 가산기·감산기를 써서 이진 곱셈·나눗셈과 같은 방식(시프트 + 덧셈·뺄셈)으로 처리한다.

핵심 정리

• 부호-절댓값은 부호 비교와 절댓값 비교가 필요하고, 2의 보수는 그냥 더한 뒤 오버플로우만 확인한다.
• 곱셈 = 시프트 + 덧셈, 나눗셈 = 시프트 + 뺄셈(나눗셈 오버플로우 주의). 2의 보수 곱셈은 Q₀Q₋₁ 두 비트를 보고 더하거나 빼는 부스 알고리즘으로 한다.
• 곱셈기·나눗셈기를 회로로 두면 빠르지만 칩이 커진다. 작은 프로세서는 덧셈 반복의 소프트웨어 루틴으로 대신한다.
• 부동 소수점 곱셈은 지수 덧셈·가수 곱셈, 나눗셈은 지수 뺄셈·가수 나눗셈 후 정규화한다.
• BCD 덧셈은 이진 합이 9를 넘으면 6을 더해 보정한다.

관련 노트: 데이터의 표현, 레지스터 전송과 마이크로 연산, 부동소수점 오차: 반올림·비교·누적, 디지털 논리 회로와 부품