게이트로 수를 더하는 방법

XOR 게이트 하나와 AND 게이트 하나면 비트 두 개를 더할 수 있습니다. 전가산기 네 개를 이으면 0부터 15까지 두 수를 무엇이든 더할 수 있습니다.

더 읽기 전에 문제 하나를 풀어 보세요. 0101과 0011을 이진수 그대로 종이에 더합니다. 십진수 덧셈처럼 오른쪽 자리부터 더하고, 받아올림은 다음 자리 위에 작게 적습니다. 알아야 할 것은 세 가지뿐입니다. 0 + 0 = 0, 0 + 1 = 1, 그리고 1 + 1 = 10입니다. 마지막 것은 이 자리에 0을 쓰고 1을 받아올린다는 뜻입니다. 받아올림까지 셋을 더해야 할 때는 1 + 1 + 1 = 11이므로 1을 쓰고 1을 받아올립니다. 풀이는 바로 다음 문단에 있으니 손으로 가리고 먼저 해 보세요.

풀이입니다. 맨 오른쪽 자리는 1 + 1 = 10이니 0을 쓰고 1을 받아올립니다. 그다음 자리는 0 + 1에 받아올림 1을 더해 다시 10, 0을 쓰고 1을 받아올립니다. 셋째 자리는 1 + 0에 받아올림을 더해 10, 또 0을 쓰고 1을 받아올립니다. 맨 왼쪽 자리는 0 + 0에 받아올림을 더해 1입니다. 답은 1000, 십진수로 8이고, 5 + 3 = 8이니 맞습니다. 네 자리 가운데 세 자리에서 받아올림이 일어났습니다. 계산기 앱도, 게임도, 스프레드시트도 결국 이 계산을 합니다. 프로세서 안에서는 자리 하나를 게이트 몇 개가 맡고, 아래 장면도 바로 이 덧셈으로 시작합니다. 그다음에는 장면에서 9 + 8을 골라 보세요. 이번에는 다섯째 비트가 필요합니다.

맨 오른쪽 자리에는 게이트 두 개면 됩니다

맨 오른쪽 자리만 따로 떼어 보겠습니다. 이 자리의 답 비트인 합(sum)은 두 입력 가운데 딱 하나만 1일 때 1입니다. 앞 단원에서 본 XOR 규칙 그대로입니다. 받아올림(carry)은 두 입력이 모두 1일 때만 1입니다. 이것은 AND 규칙입니다. 그러니 같은 두 입력을 받는 XOR 게이트 하나와 AND 게이트 하나를 나란히 놓으면 비트 두 개를 더할 수 있습니다. 이 작은 회로를 반가산기(half adder)라고 합니다. 오른쪽에서 올라오는 받아올림을 받을 입구가 없어서 「반」이라는 이름이 붙었습니다. 앞 단원 장면의 게이트 메뉴 맨 끝에 있던 반가산기가 바로 이 회로입니다.

나머지 자리에서는 비트 세 개를 더합니다

나머지 자리에서는 비트 세 개가 만납니다. 두 수에서 하나씩, 그리고 오른쪽에서 올라온 받아올림입니다. 전가산기(full adder)는 이 셋을 모두 받습니다. 합은 A XOR B XOR 들어온 올림이고, 세 비트 가운데 1이 홀수 개일 때 1이 됩니다. 나가는 올림은 세 비트 가운데 둘 이상이 1일 때 1이 됩니다. 반가산기 두 개와 OR 게이트 하나로 전가산기 하나를 만들 수 있습니다. 전가산기 네 개를 한 줄로 세우고, 저마다의 나가는 올림을 왼쪽 가산기의 들어오는 올림에 이으면 4비트 덧셈기가 됩니다. 받아올림이 오른쪽에서 왼쪽으로 차례차례 번져 가야 맨 왼쪽 자리가 정해지기 때문에 이 설계를 리플 캐리 덧셈기라고 부릅니다. 실제 프로세서는 받아올림을 기다리지 않고 미리 계산하는 더 영리한 회로로 64비트 수를 더하지만, 자리마다 쓰는 규칙은 똑같습니다.

답이 너무 클 때 생기는 일

4비트로는 0부터 15까지 담을 수 있습니다. 9와 8을 더하면 진짜 답은 17이고, 17은 이진수로 10001이라 다섯 비트가 필요합니다. 네 비트만 담는 레지스터에는 0001, 십진수로 1이 남고, 왼쪽으로 넘친 받아올림 하나가 경고 신호가 됩니다. 이것이 오버플로입니다. 4비트에서 15 + 1을 하면 0000만 남습니다. 프로세서는 이때 플래그라는 표시를 세워 프로그램이 알아챌 수 있게 합니다. 뺄셈을 위해 회로를 따로 만들 필요는 없습니다. A − B를 할 때 프로세서는 B의 비트를 모두 뒤집고 1을 더해 B의 2의 보수를 만들고, 그것을 A에 더한 뒤 넘친 받아올림을 버립니다. 4비트로 5 − 3을 해 보겠습니다. 3은 0011, 뒤집으면 1100, 1을 더하면 1101입니다. 5인 0101에 더하면 0101 + 1101 = 10010이고, 아래 네 비트만 남기면 0010, 십진수로 2입니다.

곱셈은 자리를 옮겨 가며 더하는 계산

곱셈도 같은 부품으로 만듭니다. 이진수에서 2를 곱하면 모든 비트가 한 자리씩 왼쪽으로 옮겨 갑니다. 십진수에서 10을 곱하면 뒤에 0이 하나 붙는 것과 같습니다. 0011(3)은 0110(6)이 됩니다. 5 × 3을 하려면 3을 2 + 1로 나눠 생각합니다. 5 × 3 = 5 × 2 + 5 × 1 = 1010 + 0101 = 1111, 십진수로 15입니다. 곱셈 회로는 둘째 수에서 1인 비트를 하나씩 보면서 첫째 수를 그만큼 옮기고 더하는 일을 되풀이합니다.