1비트 두 개를 더하는데 왜 결과는 두 자리가 필요할까?

0과 1을 더하면 1이다. 1과 1을 더하면 2인데, 1비트에는 0과 1밖에 담을 수 없다. 그래서 합의 현재 자리와 다음 자리로 넘어갈 값을 나눠야 한다. 이 작은 덧셈을 회로로 만들면 여러 자리 정수를 더하는 원리도 보인다.

비트(bit)는 두 상태 가운데 하나를 0 또는 1로 나타내는 단위다. 이진수(binary)는 오른쪽부터 자릿값이 1, 2, 4처럼 두 배씩 늘어나는 숫자 표기다. 이진수 10은 십진수 2다. 입력 1과 1의 합이 10이 되므로 출력 두 자리가 필요하다.

네 가지 입력을 모두 적어 보기

논리 게이트(logic gate)는 0과 1을 받아 정해진 규칙으로 출력하는 회로다. 진리표(truth table)는 가능한 입력 조합마다 결과를 적은 표다. 입력 A와 B가 각각 0 또는 1이라면 조합은 네 가지다.

A	B	현재 자리의 합	다음 자리로 올림
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

마지막 줄에서 1과 1을 더한 결과는 이진수 10이다. 현재 자리에는 0을 쓰고 다음 자리에 1을 올린다. 둘을 더하는 이 회로를 반가산기(half adder)라고 한다.

합과 올림은 서로 다른 규칙이다

배타적 논리합(exclusive OR, XOR)은 입력 둘이 다를 때 1을 낸다. 위 표에서 현재 자리의 합과 같다. 논리곱(AND)은 입력 둘이 모두 1일 때만 1을 낸다. 위 표에서 올림과 같다.

현재 자리의 합 = A XOR B
다음 자리 올림 = A AND B

입력 넷을 표와 식에 하나씩 대입하면 두 결과가 일치한다. 회로 그림을 외우기보다 어떤 입력에서 올림이 생기는지 먼저 확인하는 편이 이해하기 쉽다.

여러 자리를 더하면 무엇이 더 필요한가

두 자리 이상의 수를 더할 때는 아래 자리에서 올라온 1도 함께 더해야 한다. 예를 들어 이진수 11과 01을 더하면 오른쪽의 1+1에서 올림 1이 생긴다. 왼쪽 자리에서는 원래 두 입력 1과 0에 그 올림 1까지 더해야 한다. 결과는 이진수 100, 십진수 4다.

  11   십진수 3
+ 01   십진수 1
----
 100   십진수 4

전가산기(full adder)는 두 입력 비트와 아래 자리에서 올라온 비트를 함께 받는다. 입력 세 개 중 몇 개가 1인지에 따라 현재 자리의 합과 다음 자리 올림을 만든다. 1비트 반가산기만 이어 붙이면 아래 자리의 올림을 받을 곳이 없어 여러 자리 덧셈을 제대로 처리할 수 없다.

여러 전가산기를 잇는 회로에서는 낮은 자리의 올림이 높은 자리까지 전해져야 결과가 정해진다. 비트 수가 늘수록 이 경로가 길어질 수 있어, 더 빠른 덧셈 회로는 올림을 미리 계산하는 방식도 쓴다. 정수 덧셈의 비용을 볼 때 회로가 몇 자리의 올림을 거쳐야 하는지도 살펴볼 이유다.

참고 자료

• MIT 강의: 조합 논리와 전가산기