9. 가산기와 오버플로 (Adder and Overflow)

가산기와 감산기는 컴퓨터 시스템에서 중요한 역할을 하는데, 이진수를 서로 더하거나 빼는 역할을 한다.
하나의 가산기는 한 비트에 대응하며, 16비트 연산을 위해서는 1비트 가산기 16개가 필요하다.

가산기는 반가산기와 전가산기로 나뉜다.

반 가산기^{Half Adder}

두 2진수의 덧셈을 수행하고, 합^sum과 자리올림수^carry를 출력한다.

$$ S = x \oplus y \\ C = xy $$

$x$	$y$	$C$	$S$
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

반 가산기는 한 자리 2진수를 계산하는 데 쓸 수 있지만, 여러 자리를 계산하기 위해서는 두 정수 뿐만 아니라 지난 자리의 정수, 즉 carry 까지 고려를 해야하기 때문에 사용할 수 없다.

여러 자리의 2진수 덧셈을 위한 것이 바로 전가산기이다.

전 가산기^{Full Adder}

전 가산기는 세 개의 이진수를 입력받아 합과 자리올림수를 출력한다. 이때, 세 개의 입력 중 하나를 지난 자리의 자리올림수로 하여 여러 자리의 이진수를 처리할 수 있다.

$x$	$y$	$z$	$C$	$S$
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

$$ S = x \oplus y \oplus z \\ C = xy + (x \oplus y)z $$

반 가산기를 이용해 세 정수의 덧셈을 2번에 나눠 시행함으로서 전 가산기의 기능을 수행할 수도 있다.

감산

컴퓨터에서의 감산은 음수의 덧셈으로 할 수 있다. 음수의 표현은 2의 보수를 이용한다. 즉, 아래가 성립한다.

$$ N - M = N + (\text{Two's complement of M}) = N + (2^n - M) $$

이때, 2의 보수는 각 비트를 역전시킨 1의 보수에 1을 더하여 얻을 수 있다.
이때, 각 비트를 역전시키는 과정에 XOR 게이트를 사용하면, 하나의 회로로 덧셈과 뺄셈을 모두 수행할 수 있다.

위 그림에서, $M=0$이면 덧셈을, $M=1$이면 뺄셈을 수행한다.

오버플로

가산기는 n-bit의 덧셈에서 (n+1)bit의 결과를 출력할 수 있다. 이를 오버플로라고 한다. 계산한 결과의 가장 높은 자리에 carry가 있다면, 이는 오버플로가 발생한 것이다. 이는 XOR 게이트를 통해 탐지할 수 있다.

오버플로는 가산기에 들어간 두 수가 같은 부호를 가질 때(모두 양수이거나 모두 음수일 때)만 발생한다. 같은 부호를 갖는 수를 덧셈했는데 부호가 바뀌었다면, 이는 오버플로가 발생한 것이다.