컴퓨터 연산

 

컴퓨터와 인간지능 : Donald G. Fink 저, 이기호 역, 이화여대 출판부, 1986, Page 27~47

 

10 진수와 2 진수의 변환

8 진수

2 진수의 덧셈과 뺄셈

2 진수의 곱셈과 나눗셈

숫자와 전류

곱셈과 나눗셈

 

전자계산기를 이해하기 위한 첫 번째 일은 기계는 명령받은 양보다 더 많게도 적게도 하지 않는다는 것이며, 두 번째는 컴퓨터에 주는 지시는 간단하고 직설적이어야 한다는 것이다. 컴퓨터는 복잡한 문제를 풀 수 있다. 그러나 그것은 단지 인간이 먼저 그 문제를 풀 수 있다. 그러나 그것은 단지 인간이 먼저 그 문제를 작은 단계의 연결로 나누어 놓았을 때 가능하다. 대부분 이들 단계는 단지 0, 1 만을 사용하는 가장 간단한 2 진수의 산술 계산 (binary arithmetic) 인 연산들이다.

만약 컴퓨터가 복잡한 문제를 어떻게 푸는지를 알기를 원한다면 컴퓨터 산술 계산의 작은 단계들에 익숙하여야 한다. 이 장에서는 먼저 0, 1 만을 사용하여 사람들이 어떻게 계산하는지를 복습하고, 간단한 전기회로가 어떻게 같은 방법으로 수행할 수 있는지는 다음 장에서 설명하겠다.

10 진수와 2 진수의 변환

모든 사람들이 잘 아는 0 에서 9 까지의 숫자에 의해 결정되는 10 진법부터 시작하자. 10 진법에서 각 숫자의 위치 (position) 는 10 의 멱 (power) 과 연관이 있다. 소수점을 기준으로 왼쪽으로 가면서 가장 처음의 숫자는 1 을 나타낸다 (100 = 1). 두 번째는 10 을 나타내고 (101 = 10) 그리고 다음은 100 (102 = 100) 을 나타낸다. 이상과 같이 말로 한 각 수를 10 의 멱으로 쓸 수 있다.

또한 10256 이란 수를 다섯 개의 10 진수의 합으로 표현할 수 있다. 즉 대응하는 10 의 멱에 의해서 각 숫자에 곱하고, 그것들을 다시 더한다.

똑같은 규칙이 2 진수에도 적용된다. 2 진수의 표시에서 각 숫자는 2 의 멱과 관련된다. 2 진수의 소수점에서 왼쪽 첫 번째 숫자는 1(20 = 1) 을 나타내고, 다음 숫자는 2(21 = 2) 를 나타낸다. 그 다음은 4(22 = 4) 를, 다음은 8(23 = 8) 등으로 나타낸다. 예를 들면, 10 진수 46 은 다음과 같이 2 의 멱으로서 2 진수를 나타낼 수 있다.

또는 5 개의 2 진수의 합으로도 알 수 있다.

2 진수를 10 진수로 바꾸기 위해서 각각의 숫자를 10 진수 (decimal) 로 바꾸고 그 10 진수를 다시 더하면 된다. 그래서 2 진수 101110 은 다음과 같이 변환된다.

즉 2 진수 101110 은 10 진수 46 과 같다. 두 수가 같다는 것을 1011102 = 4610 으로 표현한다. 여기서 아래쪽에 쓴 숫자 (subscripts) 2 와 10 은 각각 2 진수와 10 진수를 나타낸다.

역으로 10 진수에서 2 진수로 바꾸기 위해서는 10 진수의 숫자들이 2 의 멱으로 분산되어야만 한다. 10 진수를 2 로 계속 나누어야 한다. 즉 전체를 1/2 로, 1/2 을 1/4 로, 1/4 을 1/8 로, 1/8 을 1/16 로 계속 나눈다. 피제수가 홀수일 때는 언제나 몫은 1 의 나머지를 갖고 짝수의 피제수는 나머지가 항상 0 이다. 나눗셈을 할 때마다 나오는 각 나머지는 10 진수와 같은 2 진수의 숫자이다.

예를 들어 46 과 같은 2 진수를 찾기 위해서 2 로 나눈다. 몫은 23 이고, 나머지는 0 이다. 이 나머지는 46 을 2 진수로 만드는 것의 2 의 멱 (20) 을 나타낸다. 그래서 그것은 2 진수 형태에서 가장 오른쪽의 숫자가 된다. 그 다음 23 을 2 로 나누면 몫은 11 이고 나머지가 1 이 된다. 나머지는 2 의 처음 멱 (21) 이고, 그것은 2 진수의 왼쪽으로 두 번째 숫자가 된다. 4610 을 2 진수로 바꾸는 전체 과정은 다음과 같다.

나머지를 아래서부터 위로 쓴다. 그래서 4610 = 1011102 라는 것을 안다.

이와 같은 방법을 명확히 하기 위해 이번에는 10 진수 218 을 2 진수로 바꾸는 일을 다시 해본다.

다시 아래서부터 위로 나머지를 쓰면,

    21810 = 110110102

가 된다. 역으로 이 2 진수를 10 진수로 바꾸는 작업을 통해 이 변환을 검토할 수 있다.

명백히 10 진수를 2 진수로 바꾸는 일 또 2 진수를 10 진수로 바꾸는 일 등은 적어도 사람들에게는 매우 귀찮은 일이며 또 2 의 멱과 10 의 멱을 계산하고 더하는 과정에서 실수를 할 가능성이 많다. 더 많은 연습을 원하는 독자들은 적당히 큰 10 진수, 말하자면 1947563 과 같은 수의 2 진수를 찾는 문제를 풀어 보기를 원할지도 모른다. 2 진수를 찾기 위해 21 번의 계속적인 나눗셈을 한 후에 111011011011110101011 을 얻게 될 것이고, 여러분은 왜 인간의 계산 속에 2 진수가 사용되지 않는지 알게 될 것이다. 숫자가 너무 많고 (2 진수는 같은 10 진수보다 평균 세 배나 많은 숫자를 갖는다), 그리고 그 수는 너무 다양성이 없기 때문에 (즉 0 과 1 만) 식별하고 기억하기가 어렵다. 그러나 2 진수를 더하고 곱하는 방법은 우리가 곧 보게 되듯이 대단히 쉽다. 그리고 여러 특질 중에 때문에 컴퓨터에 사용하는 것이 좋다.

8 진수

2 진수와 10 진수 사이의 변환은 2 진수에서 8 진수 (octal number), 즉 8 의 멱으로 표현되는 수로 바꾸는 중간 과정을 통해 간단해질 수 있다. 2 진수와 같은 8 진수는 검사에 의해서 찾을 수 있다. 2 진수는 가장 오른쪽 숫자에서 시작해서 3 개의 숫자씩 한 묶음으로 정돈한다 (이를 3 수조, triads 라고 한다). 각 3 수조에 있는 세 개의 수의 각각의 위치는 그 위치에 해당하는 그의 멱과 연관된다. 즉 4-2-1 의 위치이다. 8 진수는 각 3 수조에 대해 하나의 숫자 (0 에서 7 까지의 수) 를 가지며, 그 8 진수의 값은 그 3 수조의 2 의 멱의 합이다. 예를 들면 2 진수 101010011 은 8 진수로 다음과 같이 된다 (2 진수의 3 수조에서 8 진수로 읽어 내려가면 된다).

8 진수에서 2 진수로 바꾸는 역변환은 8 진수에서 2 의 멱으로 읽어 올라가서 8 진수를 만들기 위해 필요했던 각 멱 아래 1 을 씀으로써 만들어질 수 있다.

8 진수에서 10 진수로 바꾸는 또 다른 중요한 단계는 8 진수의 각각에 8 의 멱의 10 진수값을 곱하고, 그 10 진수 곱을 더함으로써 만들어진다. 따라서 5238 은 다음과 같이 변환된다.

역으로 10 진수를 8 진수로 바꾸는 것은 8 로 계속 나누어서 나머지들을 기록하는 것이다. 다음은 33910 = 5238 이 된다는 증명이다.

대조적으로 33910 을 2 진수로 직접 바꾸는 일은 더 많은 계산이 필요하다.

아래서 위로 정돈하면 나머지는 101010011 이다. 숫자는 이미 앞에서 검토했다.

8 진수 변환이 얼마나 유용한가를 보여주기 위해서 194756310 과 같은 2 진수를 다시 보자. 이것이 111 011 011 011 110 101 011 과 같이 3  수조로 정리될 때 곧 각 3 수조 안에 4-2-1 이라는 그의 멱을 기억하고 각 3 수조에 있는 1 과 대응되는 멱을 더함으로써 7 3 3 3 6 5 3 이라는 8 진수를 만들어낸다.

2 진수의 덧셈과 뺄셈

다음에 재검토할 주제는 2 진수의 기본 연산인 덧셈이다. 2 진수의 덧셈이 귀찮다고만 생각된다면 먼저 10 진수의 덧셈부터 살펴보자. 한 열의 10 진수의 덧셈을 위한 공통된 일은 가장 위쪽에서부터 두 수씩 짝을 지어 한꺼번에 더하는 일이다. 그 합은 바로 아래에 있는 수에 더해진다. 그래서 맨 밑에 있는 줄까지 더해진다. 이 과정에서 어떤 것의 합이 9 를 초과할 때마다 우리는 왼쪽에 있는 다음 열로 숫자 하나를 넘긴다. 우리가 다음 열을 더할 때는 지금까지 누적되어온 올림수까지를 포함해서 계산한다. 10 진수를 더하기 위해서는 0 에서부터 9 까지의 모든 숫자와 다른 것과의 조합, 즉 100 가지의 조합을 기억해야 된다는 것은 명백한 사실이다. 우리는 어려서부터 이 합산을 기억 속에 넣고 생의 일부처럼 되었기 때문에 형식적인 관계를 잊고 있으므로 10 진수의 덧셈표를 이해하려면 두 번은 보아야 한다.

2 진수의 덧셈표는 10 진수 표의 위 왼쪽 끝에서 온다. 즉

별표 (*) 는 2 의 자리이다. 그런데 2 진수에서는 숫자 2 가 없다. 2 에 해당하는 2 진수는 10 또는 "0 과 올림수 1" 이다. 그래서 2 진수의 덧셈표는

이다. 2 진수의 열에 대한 덧셈 규칙은 10 진수에 따른다. 합이 1 을 초과할 때마다 왼쪽 다음 열에 숫자 하나를 옮긴다.

2 진수 덧셈에 관한 다음 예에서 그 열의 위에 올림수를 놓고 두 번째 올림수가 필요한 곳에서는 처음의 올림수 위에 놓았다.

[예제 1] 110010111 과 1010011 을 더하라.

[예제 2] 101, 111, 001 과 110 을 더하라.

예제 2 를 살펴보면 4 개의 2 진수와 같은 10 진수로부터 결과를 얻을 수 있다. 즉 5 + 7 + 1 + 6 = 19. 또한 100112 = 16 + 0 + 0 + 2 + 1 = 1910 (Q.E.D.)

덧셈의 역인 2 진수의 뺄셈은 두 숫자의 차가 0 보다 작을 때마다 왼쪽 다음 열로부터 수를 빌려옴으로써 연산될 수 있다. 뺄셈의 결과는 피감수를 만들기 위해 감수에 차를 더함으로써 검산할 수 있다.

[예제 3] 10101101 에서 1001100 을 빼고 덧셈에 이해 검산하라.

검산 :

[예제 4] 1100110 에서 1101, 1001, 1111 그리고 0010 을 빼라. 덧셈으로 검산하라.

검산 :

2 진수의 곱셈과 나눗셈

곱셈은 승수의 수만큼 많은 회수를 처음에 0 에, 다음엔 연속되는 합에 이르기까지 곱수가 더해지면서 덧셈이 반복된다. 우리는 매일 사용하기 위해 이 귀찮은 과정을 피하고 긴 곱셈의 형식을 대치하는데, 이 곱셈의 형식은 0 에서 9 까지의 수와 어떤 수와의 곱한 결과를 필요에 따라 내놓을 수 있다. 다음 표에서 보여주는 10 진수 곱셈표를 우리가 기억하고 있었음에 틀림없다.

2 진수의 곱셈표는 10 진수표의 위 왼쪽 끝에서 나온다.

이 간단한 표를 긴 곱셈에 적용시켰을 때 승수에 있는 모든 1 은 피승수를 반복시키지만 0 은 아무런 역할도 하지 않는다는 것을 알고 있다. 우리는 그 위치 (즉 옳은 숫자 밑에 곱을 적는) 을 기억하여야만 한다. 그렇지 않으면 긴 곱셈은 간단하다.

[예제 5] 101100101 에 1011 을 곱하라

2 진수의 긴 나눗셈은 10 진수 형태를 따른다.

[예제 6] 예제 5 를 곱하임수를 얻기 위해서 곱수로 곱을 나눔으로써 검산하라.

숫자와 전류

2 진수에 대한 인간의 계산은 이 정도로 해두자. 컴퓨터는 전류의 흐름으로 계산할 수 있다. 예를 들면, 전류가 흐르는 전기회로는 수 1 을 표시하고 전류가 흐르지 않으면 회로는 숫자 0 을 표시한다는 것은 이미 알고 있는 사실이다. 한 전구와 전지 그리고 스위치를 가지고 있는 회로가 <그림 1> 에서 그 방법을 설명한다.

 

스위치가 닫혔을 때 전류가 흐르고 불이 켜진다. 즉 회로는 조건 "1" 에 있게 된다. 스위치가 열릴 때는 어떤 전류도 흐를 수 없고 불이 꺼진다. 즉 회로는 조건 "0" 에 있게 된다.

이러한 회로 몇 개를 나란히 놓고 각각의 스위치를 켰다 껐다 함으로써 2 진수를 표시할 수 있다. <그림 2> 의 맨 위에 있는 6 개의 회로는 2 진수 101101 을 표시하고, 가운데 있는 회로들은 101000 을 표시한다.

회로에 이 숫자들을 더하려면 바로 밑에 있는 전구의 전류에 상응하는 위의 전구의 하나에 전류를 흐르게 (또는 흐르지 않게) 해야 한다. 합해진 전류들은 그림의 가장 밑에 있는 전구에서 나타난다. 그 합 1010101 이 7 개의 숫자를 가지고 있기 때문에 7 개의 전구가 필요하고 가장 왼쪽 전구는 가장 왼쪽의 올림 숫자를 표시한다.

전류들을 합하는 규칙은 2 진수의 덧셈표에서 주어진 규칙들이다.

처음 세 규칙을 만족시켜주는 회로는 <그림 3> 에서 볼 수 있다.

만약 스위치 A 와 B 가 열려 있으면 합산 전구는 꺼진 채로 있어서 (조건 "0") 첫째 규칙을 표시한다. 또한 스위치 A 나 B 중 하나가 닫혀 있으면 전구는 켜져서 (조건 "1") 두 번째와 세 번째의 규칙을 나타낸다. 그러나 이 회로에는 네 번째 규칙에 대해 잘못된 결과가 나온다. 왜냐하면 두 개의 스위치가 닫혔을 때 전구가 꺼져 있어야 하는데 불이 들어오기 때문이다. 더우기, 이 마지막 경우에서 우리는 네 번째 규칙의 올림수를 나타내는 어떤 방법을 가져야 한다.

네 가지 규칙을 모두 나타내기 위하여 우리는 다른 회로를 필요로 한다. 이것은 <그림 4> 에서 보는 것처럼 한 쌍으로 작동되는 네 개의 스위치를 포함하는 것으로 0 + 0 = 0 을 나타낸다. 만약 피가수 스위치가 내려지고 가수 스위치가 현재처럼 남겨졌다면 그 합에 대한 전구가 1 + 0 = 1 을 나타내면서 불을 켜 준다. 두 개의 스위치가 내려지면 전구는 꺼지고 1 + 1 = 0 을 나타낸다. 그러나 나중 경우에서 우리는 올림수가 생겼다는 것을 나타내야 한다.

올림수가 있느냐 없느냐를 나타내기 위해서 우리는 <그림 5> 의 위에 나타나 있는 또 다른 전구와 두 개의 덧셈 스위치를 더할 수 있다. 예를 들면 이 회로에서 두 개의 스위치가 둘 다 내려질 때 올림 전구는 켜지고 한 전구는 꺼진 채로 있다. 올림수 1 을 갖고 1 + 1 = 0 을 나타낸다. <그림 5> 의 회로는 "반가산기 회로 (half-adder)" 라고 한다. 나중에 우리는 2 진수를 더하기 위해서 컴퓨터 내에서 이것들이 어떻게 쌍으로 사용될 수 있는지를 알게 될 것이다.

뺄셈은 뺄셈표에 의해 표현될 수 있다.

이 배열은 숫자를 빌려오는 것을 제외하고는 2 진수의 덧셈표와 똑같은 형식을 갖는다. 때문에 피감수 스위치가 올라갈 때, 스위치 A3 가 닫혀지고, 반면에 덧셈 회로에서는 피가수 스위치가 올라갈 때 A3 이 열린다는 것을 제외하면 똑같은 회로가 2 진수의 뺄셈을 나타낸다. 이 회로가 "반가감기 (half-subtractor)" 이다.

<그림 7> 는 피가수 111 이 가수 110 에 어떻게 더해지는지를 나타낸다.

가장 오른쪽 숫자 1 과 0 은 각각 합이 1 이고 올림수가 0 으로 되는 0 명령 가산기 (zero-order adder) 이면서 계속해서 왼쪽으로 옮겨진다. 모든 피가수, 가수, 올림수가 계산되면 그 덧셈은 끝나는 것이다. 0 명령 가산기를 제외한 모든 가산기들은 세 개의 입력 (피가수, 가수, 오른쪽에서 온 올림수) 과 두 개의 출력 (합과 왼쪽으로 보내지는 올림수) 을 갖는다는 사실에 주의하라. 가산회로에 관해서는 제 6 장에서 더 자세히 검토할 것이다.

곱셈과 나눗셈

이미 언급하였듯이 곱셈에서 피승수는 곱수의 수만큼 영 (0) 을 더한다. 그런 반복된 덧셈이 컴퓨터 내에서 사용될 수 있다. 그러나 피승수에 곱수의 각 숫자를 하나씩 곱하면서, 그 숫자의 위치에 곱을 옮기면서 그 곱들을 더하는 긴 덧셈 절차가 더 간단하고 빠르기 때문에 유익하다. 컴퓨터 덧셈의 대표적인 체계에서 피승수의 숫자들은 왼쪽에서 오른쪽으로 읽혀진다. 숫자 1 은 피승수 자체를 만들어내고 숫자 0 은 피승수의 모든 수를 영으로 만든다. 이런 결과는 그것들을 만들어낸 숫자들로 "배열된다." 그런 결과들은 앞의 합에 더해진다. 곱의 모든 숫자들이 "다 사용되면", 마지막 합이 곧 곱이 된다.

예를 들면 (예제 5 에서 사용된 수들로),

각 덧셈의 가수가 앞의 가수의 오른쪽으로 한 자리 옮겨지는 것에 주의하라. 숫자 하나를 옮기기 위해서 주어진 수와 옆에 있는 수를 교체한다. 전기적으로 한 회로 내의 전류는 이웃한 회로의 전류와 교체된다. 2 진수 회로에서 단지 두 가지 경우가 나타난다. 만약 이웃한 숫자가 같다면 어떤 변화도 요구되지 않는다. 즉 만약 다르다면 전류는 교환되어야 한다. 옮김 연산을 수행하는 회로는 시프트 레지스터 (shift registers) 로 알려졌다.

컴퓨터의 나눗셈은 형태가 좀 다르다는 것을 제외하고는 나눗셈의 과정을 따른다. 대표적인 과정에서, 제수는 고정된 자리에 있고, 피제수는 한 번에 한 자리씩 왼쪽으로 옮겨진다. 각 자리에서 피제수의 수들은 제수의 수와 비교된다. 제수가 피제수보다 더 큰 때는 몫에 영 (0) 이 기입되고 피제수는 왼쪽으로 옮겨진다. 제수가 피제수와 같거나 또는 피제수보다 작으면, 몫에 1 이 기입되고, 피제수에서 제수를 빼고 2 차는 새로운 피제수로서 아래에 기입된다. 이 피제수는 다시 왼쪽으로 옮겨지고 모든 피제수가 다 사용될 때까지 그 과정을 계속한다.

예를 들면 (예제 6 을 반복한다),

위로부터 아래까지 얻어진 몫은 000101100101 이다. 앞에 있는 영 (0) 3 개는 무시해도 된다 (예제 6 과 같은 결과가 된다).

나눗셈에 대한 이런 귀찮은 과정을 써 나가는 것은 그것이 컴퓨터 세계의 기본적인 사실 중의 하나를 제시하기 때문에 의미를 갖는다. 즉 규칙은 간단해야 한다. 제수는 바로 위에 있는 피제수와 비교된다. 만약 제수가 바로 위의 수와 비교해서 작거나 같다면 몫은 1 이다. 각각의 몫이 발견된 뒤에 피제수는 왼쪽으로 한 자리 옮긴다. 1 이란 몫이 만들어진 후에 새로운 피제수가 만들어진다. 새로운 피제수란 제수와 원래 피제수와의 차이다. 이런 문장들은 나눗셈의 논리를 설명한다. 나눗셈에서 사용된 컴퓨터 회로들은 이런 논리를 구체화한다.

컴퓨터에 의해서 사용된 덧셈, 뺄셈, 오른쪽으로 옮김, 왼쪽으로 옮김, 또 두 수가 같은지, 둘 중의 어느 것이 작은지 혹은 큰지를 비교하는 산술 계산의 과정들을 조사함으로써, 연립방정식을 푸는 전면적인 계산에서 그것들을 사용할 수가 있다.