반가산기(Half-adder)와 전가산기(Full-adder)

반가산기란 두 개의 비트를 더하여 합(sum)과 올림자(carry)를 구하는 것이다.
머리 속으로 구현해 보자.

0+0=0
0+1=1
1+0=1

이까지만 보면 마치 OR연산자로 처리될 것 같지만 문제는 이거다.

1+1=0

두 비트가 모두 1일 때 결과는 10이 되어야 한다. 올림자(Carry)가 1이 되고 합(sum)은 0이 돼야 하는 것이다. 기초를 제대로 공부 했다면 아래와 같은 연산 결과를 가지는 연산자를 바로 알아챌 수 있을 것이다.

0 0 → 0
0 1 → 1
1 0 → 1
1 1 → 0

바로 XOR 이다. XOR이 있기 때문에 합(sum)은 의외로 간단하게 구현된다.
올림자(carry)는 더 쉽다. 위에서 보았듯이 둘다 1일 때만 1을 반환하면 된다. 그냥 AND연산자 하나면 쉽게 해결되는 것이다. 결국 반가산기는

합(sum) = A XOR B
올림자(carry) = A AND B

이렇게 하면 덧셈은 얼추 해결되겠네? 라고 생각할 수도 있지만 이름에서 알 수 있듯이 아직 반밖에 안 왔다. 실제로 여러 일련된 비트열은 더하려면 맨 끝자리가 아닌 이상 그 전 자리의 올림자까지 고려해서 더해줘야 한다. 결국 현재 자리의 비트 두 개와 전 자리에서 올라온 올림자 한 개까지 총 3개의 비트를 더해야 하는 것이다.

전가산기는 이와 같은 연산을 하게 해준다.

합(sum)은 쉽다. 그냥 아까와 같은 방식으로 비트 3개를 차례로 XOR연산 해 주면 된다.
(A XOR B) XOR C

올림자가 조금 어렵다. 전 연산에서 Carry가 발생하였는지, 이번 연산에서Carry가 발생 할 것인지 모두 고려해야 하기 때문이다. 이번 연산만으론 Carry가 발생하지 않지만 이번 연산과 저번 Carry가 더해져서 Carry가 발생하게 될 수도 있다.

1. 이번 연산으로Carry가 발생하는가
2. 이번 연산의 결과와 저번 연산의 Carry가 더해져서 Carry가 발생하는가

위 두 가지 경우중 어떤 경우에도 Carry가 반환되어야 하므로 둘은 OR연산자로 묶일 수 있다.
그럼 두 조건을 하나씩 식으로 풀어보자. 1번의 경우 반 가산기와 동일하다.

A AND B

2번의 경우 Carry를 구하기 위해 AND 연산자로 묶되 이번 연산의 결과와 저번 연산의 Carry를 묶어 주어야 한다.

(A XOR B) AND C

그리고 둘을 OR 로 묶어 준다.

(A AND B) OR ((A XOR B) AND C)

컴퓨터에서 사칙 연산은 모두 가산기를 이용해서 하는 것이기 때문에 가산기는 정말 중요하다.
뺄셈은 감수의 보수를 구해 더하는 것이고
곱셈은 덧셈연산의 반복,
나눗셈은 뺄셈 연산의 반복이기 때문에 결국 가산기가 혼자 다 해 먹는 것이다.