6. 컴퓨터의 정수연산 (Integer Arithmetic of Computer)

컴퓨터의 산술연산은 크게 정수^Integer의 연산과 실수(부동소수점^{Floating Point})의 연산으로 나뉜다.

정수 연산

컴퓨터에서 정수는 이진수로 표현되는데, 이때 음수는 2의 보수로 표현된다.
2의 보수에 대한 자세한 설명은 아래 글을 참고하자.

2. 수 체계: 진수 변환과 이진수의 실수/음수 표현(Number System)

정수의 덧셈과 뺄셈

정수의 덧셈은 수 체계가 이진수일 뿐, 우리가 아는 덧셈과 똑같다. $1+1$이 되면 이진수에 $2$는 없으므로, 다음 자리로 올림한다. 예를들어, $11+10=101$이다.

2의 보수를 사용하여 음의 정수를 표현할 경우, 덧셈을 이용하여 정수의 뺄셈도 가능하다.

$6-4=6+(-4)$임을 이용하여, 그냥 서로 더하면 된다.

오버플로우

$n$비트의 정수 연산에서, 그 결과가 할당된 비트 $n$을 넘어설 경우 오버플로우가 발생한다. 예를들어 2비트 정수의 덧셈 $11+10$은 $101$이지만, 결과는 2비트까지 표시되므로 $01$이 된다.

오버플로우는 양수와 음수의 연산에서는 발생하지 않고, 같은 부호의 연산에서만 발생한다.

양수간의 연산 결과, 부호 비트가 1이면 오버플로우가 발생한 것이다.(양수의 덧셈이 음수가 되었으므로)
반대로 음수간의 연산 결과로 부호 비트가 0이면 오버플로우가 발생한 것이다.1

포화 연산^{Saturation Arithmetic}

오버플로우가 발생한 경우, 해당 비트내에서 가능한 최대 비트를 반환하는 방법이 있다.

예를들어, $11+10 = 11$이다. 2비트로 표현 가능한 최대값이 $11$이기 때문이다.

SIMD

64비트 정수 연산을 64비트 가산기로 처리할 수도 있지만, 더 적은 용량의 가산기 여러개로 처리할 수도 있다.
예를들어, 8비트 가산기 8개를 이용하여 64비트 덧셈을 수행할 수 있다.

이러한 방법을 Single Instruction Multiple Data, SIMD라고 부른다.

정수의 곱셈

이진수의 곱셈도 우리가 흔히 아는 방법을 이용한다. $1000 \times 1001 = 1000+00000+000000+1000000$이다.

문제는 이를 컴퓨터로 구현하는 방법인데, 우선 곱하고자 하는 두 수를 각각 Multiplicand, Multiplier로 부르겠다.

1. Multiplier에서 가장 우측의 한 비트와 Multiplicand를 곱하고, 이를 Product에 더한다.
2. Multiplier는 우측으로 Shift하고, Multiplicand는 좌측으로 Shift한다.
3. 1, 2를 반복하여 Multiplier의 모든 값을 곱한다.

예시

Multiplicand	Multiplier	연산	Product
1000	1001	초기 상태	0
1000	1001	1000 * 1	1000
10000	0100	10000 * 0	1000
100000	0010	100000 * 0	1000
1000000	0001	1000000 * 1	1001000

Optimized Multiplier

기존의 곱셈기는, Multiplicand와 Multiplier가 계속 Shift 되기 때문에, 32비트 연산에 64비트 변수 저장공간과 ALU가 필요했다. 이를 최적화하면, Multiplicand와 Multiplier를 32비트에 저장하고, ALU도 32비트로 처리할 수 있다.

Multiplier는 점점 작아지는 특성을 이용하면 된다.
일단 product 공간에 Multiplier를 저장해두고, Multiplicand는 아예 Shift없이 32비트로 고정한다.

Multiplier에서 값을 꺼내 Multiplicand와 곱한 후, Product의 앞부분에 넣어준다. 이후, Product안의 값을 우측으로 Shift하여, Multiplier도 Shift하고, Multiplicand를 좌측으로 Shift한 것과 같은 결과를 얻을 수 있다.

Array Multiplier

곱셈을 수행할 때, 덧셈 횟수를 최소화하기 위한 방법으로 Array Multiplier가 있다.

아래로 이어지는 선은 Sum, 좌하단 대각선은 Carry

다음 곱셈기에서, 덧셈은 병렬적으로 수행되어 최대 6회 수행된다.
각 자리수의 값을 모두 따로 더하는 것에 비하면 아주 빠른 시간이다.