이진수 뺄셈을 해보자!

이제 뺌셈을 해보자

뺄셈은 기본적으로 덧셈과는 다르게 빌림수(borrow)가 발생한다.

 

253 -176 =???

 

이 문제를 풀기 위해 오른쪽 자리에서부터 시작하도록 하자. 우선 6은 3보다 크기 때문에 윗자리의 5에서 1을 빌려와서 13에서 6을 빼는 형태로 연산을 수행하게 되고, 결과는 7이 된다. 좀 전에 아랫자리로 1을 빌려주었기 때문에 그다음자리의 연산은 4에서 7을 빼는 연산이 된다. 4 역시 7보다 작기 때문에 윗자리에의 2에서 1을 빌려와서 14에서 7을 뺴는 형태를 가지게 되고, 그 결과는 7이 된다. 그다음 자리 연산 역시 좀 전에 아랫자리로 1을 빌려주었기 때문에 2가 아닌 1이 되고, 1에서 1을 빼서 결과는 0이 된다. 따라서 최종 결과는 77이 되는 것이다.

 

253 -176 = 77

 

빌림(borrow) 없이 빼는 방법

어떻게 하면 논리 게이트들을 이용해서 이런 까다로운 뺌 셈 연산을 처리할 수 있을까? 그 대신 빌림 없이 뺄셈을 할 수 있는 간단한 트릭을 살펴보자. 이 과정을 설명하기 위하여 뺄셈에 사용되는 두 수에 대해서 살펴볼 필요가 있다.

 

빼는 수(subtrahend)와 빼어지는 수(minuend)이다.  빼어지는 수에서 뺴는 수를 빼면 그 결과는 두 수의 차(difference)가 된다.

 

빼어지는 수 - 빼는 수 =  두 수의 차

 

빌림 없이 뺄셈을 처리하려면 빼는 수를 빼어지는 수에서 바로 빼지 않고, 일단 아래와 같이 999에서 빼는 수를 빼는 방법을 사용한다.

 

999 - 176 = 823

 

999를 사용한 것은 빼는 수가 세 자리 숫자였기 때문이며, 뺴는 수가 네 자리 숫자였다면 9999가 사용되어야 했을 것이다. 이와 같이 9로 이루어진 숫자 열에서 어떤 값을 뺀 결과를 9의 보수(complement)라고 부른다. 예를 들어 176에 대한 9의 보수는 823이 되는 것이다. 그 반대로 823에 대한 9의 보수는 176이 된다. 보수를 사용할 때 좋은 점은 빼는 수가 무엇이든 9의 보수를 사용하여 계산하면 빌림 과정이 필요하지 않다는 것이다.

 

빼는 수에 대한 9의 보수를 구한 다음에 아래와 같이 빼어지는 수에 더하면 된다.

 

253 + 823 = 1076

 

그리고 마지막으로 1을 더한 다음 1000을 빼는 것이다.

 

1076 + 1 - 1000 = 77

 

드디어 연산을 끝냈다. 연산의 결과는 앞에서와 같지만 빌림은 한 번도 사용하지 않았다.

 

이런 과정이 어떻게 가능한 걸까? 원래의 뺄셈 문제는 아래와 같았다.

 

253 - 176

 

이 수식에서 어떤 수가 더해진 후에 다시 뺀다면 그 결과는 항상 동일하다. 따라서 이 경우에는 1000을 더하고 다시 1000을 빼보도록 하자.

 

253 - 176 + 1000 - 1000

 

이 수식은 아래와 같이 바꿀 수 있다.

 

253 - 176 + 999 + 1 - 1000

 

이제 몇몇 숫자들을 아래와 같이 묶어보도록 하자.

 

253 - (999 - 176) + 1 - 1000

 

이 수식은 앞에서 9의 보수를 이용하여 수행했던 계산 과정과 완전히 동일하다. 여기서 한 번의 뺄셈을 두 번의 뺼셈과 한 번의 덧셈으로 바꾸었지만, 이로 인해 귀찮은 빌림 과정은 없애버릴 수 있다.

 

빼는 수가 빼어지는 수보다 클 경우

만일 빼는 수가 빼어지는 수보다 크다면 어떻게 될까요? 예를 들어, 다음과 같은 뺄셈이 있을 수도 있다.

 

176 - 253 =???

 

머릿속에서 두 수를 바꿔서 뺀 후에 다음과 같이 결과를 쓰는 것이다.

 

176 - 253 = 77

 

빌림 없이 계산을 할 때는 위의 예와 약간 다르다. 일단 앞에서 했듯이 999에서 빼는 수를 빼서 9의 보수를 구하는 것부터 시작하도록 하자.

 

999 - 253 = 746

 

그리고 9의 보수와 뺴어지는 수를 더하면 다음과 같이 된다.

 

176 + 746 = 922

 

이 시점에서 앞의 예에서는 1을 더하고 1000을 빼서 최종 결과를 얻을 수 있었다. 하지만, 이번 예에서는 이런 방법이 먹혀 들어가지 않는다. 923에서 1000을 빼야 하는데 이렇게 되면 빌림이 발생해버리고 만다.

그럼, 대신에 앞에서 999를 더했으므로 999를 빼는 방법을 사용해 보자.

 

922 - 999 =???

 

이를 보면 결과가 음수가 된다는 것을 알 수 있다. 두 수를 바꾸어서 999에서 922를 빼야 하다는 말이다. 이와 같은 형태의 연산도 빌림이 사용되지는 않았으며, 결과는 우리가 예상했던 것과 같다.

 

922 - 999 = -77

 

정리해 보자

빌림수 발생하지 않고 뺄셈 하는 방법

• 999에서 빼는 수를 빼준다.
• 결과는 빼어지는 수와 더한다.
• 1을 더하고 1000을 뺀다.

빼는 수가 빼어지는 수보다 작다면

• 999에서 빼는 수를 빼준다.
• 결과는 빼어지는 수와 더한다.
• 999를 뺀다.

 

이진수 뺄셈에 대해서

이 숫자들을 이진수로 바꾸면 문제는 다음과 같이 된다. 단계별로 풀어보자.

 

11111101 - 10110000 =????????

 

• 1단계 : 빼는 수를 11111111에서 뺍니다. (십진수로는 255입니다.) 11111111 - 10110000 = 01001111

 

십진수에서 뺄셈을 할 때 9로만 이루어진 숫자열에서 빼는 수를 뺏기 때문에 이를 9의 보수라 불렀다. 이진수에서는 1로만 이루어진 숫자열에서 빼는 수를 빼기 때문에 그 결과 1의 보수라고 부른다. 하지만 1의 보수를 계산하기 위하여 실제로 뺄셈을 할 필요는 없다. 1의 보수에서는 원래 0이었던 비트값은 1이 되며, 1이었던 비트값은 모두 0이 되기 때문이다. 따라서 1의 보수를 이진수의 반대 값(negation) 혹은 연수(inverse)라 이야기한다.

 

• 2단계 : 11111101 + 01001111 = 101001100
• 3단계 : 결과에 1을 더한다. 101001100 + 1 = 101001101
• 4단계 : 100000000을 뺀다. (십진수로 256)

 

101001101 - 100000000 = 01001101 

 

이 결과는 십진수 77과 동일하다. 그럼 이번에는 빼는 수가 더 큰 경우에 대해서 생각해 보자. 앞의 예에서 두 수를 바꾸어 빼기 문제를 만들면 다음과 같다.

 

176 - 253 =???

 

이를 이진수로 바꾸면 다음과 같다.

 

10110000 - 11111101 =?????????

 

1단계 : 빼는 수를 11111111에서 빼서 1의 보수를 얻는다. 11111111 - 11111101 = 00000010

2단계 : 빼는 수에 대한 1의 보수와 빼어지는 수를 더한다. 10110000 + 00000010 = 10110010

 

이제 이 결과에서 어떤 방법을 사용해서 11111111을 빼야 한다. 앞에서 보신 것과 같이, 빼는 수가 빼어지는 수보다 작다면 1을 더하고 100000000을 빼서 위와 동일한 결과를 얻을 수 있었다. 하지만 이 경우에는 빌림 없이 뺄 수가 없으므로, 그 대신 아래와 같이 11111111에서 결과를 뺴는 방법을 사용한다.

 

11111111 - 10110010 = 01001101

 

사실 이 방법은 모든 비트를 반전(inverting)시켜서 결과를 얻을 수 있는 것이다.

 

이제 모든 지식을 대부분 얻은 거 같다.

 

이진수 덧셈을 해보자!

 

이전 포스팅에서 다룬 덧셈기에 추가하여 진행하면 좋을 거 같다. 덧셈기에 추가해야 하는 회로 중 주요한 부분은 8비트 숫자에 대한 1의 보수를 구하는 부분이다. 1의 보수는 비트 단위의 반전을 통하여 얻을 수 있다. 따라서 8비트 숫자에 대한 1의 보수는 다음과 같이 8개의 인버터를 통하여 구할 수 있다.

 

8비트 인버터

 

이 회로에서 문제는 인버터가 항상 입력 값을 반전시킨다는 것이다. 여기서는 덧셈과 뺄셈을 모두 수행할 수 있는 연산 기를 만드는 것이 목표이기 때문에 뺄셈인 경우에만 입력 값이 반전되도록 만들 필요가 있다. 따라서 다음 형태로 회로를 만드는 것이 더 좋을 거 같다.

 

controlled inverter

 

 

위의 회로에서 'invert'라고 이름이 붙어 있는 신호는 8개의 XOR(exclusive OR) 게이트에 모두 입력된다. XOR 게이트는 아래와 같이 동작한다.

 

XOR 게이트의 진리표

 

따라서 inverter 신호가 0인 경우에 XOR 게이트의 출력은 입력과 동일한 값이 되고 1인 경우에 반전된 값이 출력된다.

 

예를 들어, invert가 0이며 입력으로 01100001이 들어가고 있다면 출력으로 01100001이 나온다.

invert가 1이며 입력으로 01100001이라면, 출력으로 10011110이 나온다.

 

이 여덟 개의 XOR 게이트를 '1의 보수'라는 이름이 붙은 상자 하나로 표현해 보자

 

덧셈 계산기

 

뺼셈 계산기

 

 

+, - 신호는 덧셈과 뺄셈을 선택하는 스위치이다. 이 신호가 0인 경우에는 덧셈을 수행하게 되고 1인 경우에는 뺄셈을 수행한다. 뺄셈이 수행되는 경우 B 입력은 1의 보수를 만드는 회로를 통하여 덧셈기에 들어가기 전에 모든 비트가 반전된다. 이와 더불어, 뺄셈을 처리할 때 마지막에 덧셈의 결과에 1을 더하는 부분을 처리하기 위해서 덧셈기의 CI(Carry In, 자리올림 입력) 입력에 1을 입력시켜 준다. 덧셈을 처리하는 동안에 1의 보수를 처리하는 회로에서는 아무런 일을 처리하지 않는다. CI 입력도 0이 된다.

 

뺄셈에서 빼는 수가 빼어지는 수보다 작은 경우에는 덧셈기의 CO 출력으로 1이 출력된다. 이는 뺼셈의 마지막 단계에서 100000000이 빼어져야 함을 의미하므로 당연한 것이다. 따라서 오버플로/언더플로를 나타내는 전구는 덧셈기의 CO 출력이 0인 경우에 불이 들어와야 한다.

 

자, 이제 '뺄셈은 그럼 어떻게 하지?'라는 질문에 대한 해답을 어느 정도 얻은 것 같다.

 

함께 읽으면 좋은 글

이진수 덧셈을 해보자!

 

참고하면 좋은 사이트

Code: Chapter 16

 

출처

CODE (블랙 에디션) - 예스24