메뉴
Binary Division (이진 나눗셈)

2011. 3. 26. 18:56

Intro

사실 이진 나눗셈 자체가 십진수의 나눗셈과 큰 차이가 있는 것은 아니다.
단지 0~9 대신 0~1 이라는 숫자체계를 이용할 뿐이다. 
하지만 알고리즘이 생각만큼 이해하기가 쉽지 않다.
특히 음수와 양수의 나눗셈, 혹은 음수끼리의 나눗셈까지 모두 고려해야한다면 더더욱 그렇다.
일단, 양수 끼리의 나눗셈으로 부터 차근차근 접근해 보도록 하자.




Calculation by Hand

13 ÷ 5 는 이진수의 세계에서 어떻게 계산되는가.
어차피 둘 다 양수기 때문에 Sign Bit니 2's Complement니 하는 것들은 여기서 잠깐 생각을 접어두도록 하고
그냥 5bit의 간단한 이진수로만 각각을 나타내보면 각각 13 = 01101, 5 = 00101 이다. 
이제 준비가 끝났으면, 앞에서부터 숫자를 끊어 나가면서 제수와 비교해나간다. 

Step 1

01101 (00000 < 00101)
굵게 표시된 부분과 00101의 크기를 비교해보자.
당연히 00101이 더 크다. 다음 단계로 넘어가자.

Step 2

01101 (00001 < 00101)
마찬가지 작업을 수행한다. 역시 00101이 더 크다. 

Step 3

01101 (00011 < 00101)
역시 00101이 더 크다. 

Step 4

0110(00110 >= 00101)
드디어 좌변이 더 큰 경우가 발생했다. (같아도 된다.)
이 때 생각해 주어야 할 것이 몫과, 피제수의 상태 인데,
좌변이 크거나 같은 경우 몫에 1이 올라간다.
주의할 점은 여기서 말하는 1은, 이진수의 두번째 자리에서의 1이라는 것이다.
다시 말해서 여기서 올라가는 몫 1은 실은 이진수 10과 같다.
한편, 피제수를 제수로 빼 주어야 하는데, 이 작업은 다음 단계에서 진행하자.

Step 5

0001(00110 - 00101 = 00001)
한편 피제수는 00110 에서 00101을 빼주도록 한다. 그러면 남는 숫자는 00001 이다.
전체적으로는 00011이 남은 형태가 되었다. 복잡하게 느껴질 수도 있지만,
우리가 십진수 나눗셈을 할때를 생각해 보면 된다. 
999 ÷ 6을 한다고 생각해 보자. 

    1 
   ______

6 ) 9 9 9
    6 

    _____
    3 9 

    ...

999의 맨 첫자리가 6보다 크다. 우리는 그러므로 몫에 1을 올린 다음 9에서 6을 빼주고,
그 다음 Step인 39를 적어 내려간다. 지금 하고 있는 것도 이러한 과정과 다를게 없는 것이다.

Step 6

00011 (00011 < 00101)
00011은 역시 00101 보다 작다.
이제 더 이상 다음 단계로 넘어갈 필요가 없이 곧 00011이 이 나눗셈의 나머지가 된다.
결론적으로는 01101 ÷ 00101 = 00010 ... 00011 이라는 결과를 얻게 되었다.



Using Bitwise Operation

여기서는 13 ÷ 5 라는 예제에 대해서 조금 더 컴퓨터스러운(?) 마인드로 접근해 보고자 한다.
여기서도 마찬가지로 5bit의 이진수를 이용할 것이다.
하지만 앞에서와는 다르게 Shift Operator를 이용해 보자는 것이 주요 목적이다.

먼저 우리는 몫을 Quotient의 앞글자를 딴 Q로,
제수를 Divisor의 D로, 나머지를 Reminder의 R로 나타내도록 하겠다.
피제수를 의미하는 Dividend를 따로 언급하지 않는 이유는, 그 수가 곧 Quotient가 되기 때문이다. 
아마도 계산을 따라가다 보면 이해가 될 것이라고 본다.

D가 5bit를 가진다면, Q와 R을 위해 각각 5bit를 준비한다.
하지만 실제로는 Q와 R이 구분되어 있는 것이 아닌, 하나의 10bit 저장장소로 되어있다.
다시 말해서

R     Q     D
00000 01101 00101 

이런 상태로 R과 Q를 구분해서 생각해야 하지만,

R+Q        D
0000001101 00101 

실제 저장장소에서는 아래와 같이 되어있으며,
실제 계산에서도 아래와 같은 상태에 있다고 놓고 생각해야 한다.
각각의 색이 해당하는 bit와 연결되어 있다고 보면 되겠다.

아래의 설명에서는 구분하기 쉽도록 R과 Q를 띄어쓰기를 통해 구분하도록 하겠다.
또한 Divisor는 달라지지 않으므로 굳이 표시하지 않겠다.

자, 이제 이러한 환경에서 어떻게 계산이 수행되는지 따라가보도록 하자.
비교하기 쉽게 하기 위해서 '손으로 계산하기'의 Step과 동일하게 진행할 것이다.

Step 1

R과 Q를 왼쪽으로 1비트씩 움직인다. (첫번째 비트연산)

R     Q
00000 01101
00000 11010 


그런 다음 R과 D를 비교한다. R이 더 작다면 그냥 바로 다음단계로 넘어간다.



Step 2

다시 R과 Q를 왼쪽으로 1비트씩 움직인다. (두번째 비트연산)

R     Q
00000 11010
00001 10100 


역시 R과 D를 비교한다. 마찬가지로 다음단계로 넘어간다.


Step 3

다시 R과 Q를 왼쪽으로 1비트씩 움직인다.  (세번째 비트연산)

R     Q
00001 10100
00011 01000 


역시 R과 D를 비교한다. 마찬가지로 다음단계로 넘어간다.


Step 4

다시 R과 Q를 왼쪽으로 1비트씩 움직인다.  (네번째 비트연산)

R     Q
00011 01000
00110 10000 


R과 D를 비교해봤더니 R >= D 를 만족한다.
이때에는 Q의 첫째자리 bit를 1로 바꾼다.

R     Q
00110 10000
00110
 10001 


앞에서도 말했듯 Q는 몫을 나타낸다. 
아직은 아니지만 최종 단계에서는 그렇게 된다.
비트 연산을 할때 첫째자리가 계속 0으로 채워지고,
비트 연산은 Q의 bit 길이인 5번만 진행되므로 Q가 몫을 나타낼 수 있게 되는 것이다.
더 자세한 설명은 아래에서 계속 이어가도록 하겠다.


Step 5

R     Q
00110 10001
00001 10001 


R에서 D만큼 빼준다.



Step 6

다시 R과 Q를 왼쪽으로 1비트씩 움직인다.  (다섯번째 비트연산)

R     Q
00001 10001
00011
 00010


다섯번의 비트 연산을 마쳤다.
여기서도 마찬가지로 R과 D를 비교해야한다.
하지만 R < D이므로 추가적인 단계가 필요하지 않다.

이렇게 되면 더이상 연산을 할 필요가 없다.
이미 R과 Q는 우리가 원하는 값인 나머지와 몫을 나타내고 있기 때문이다.
Step 5에서 Q의 첫번째 자리수를 1로 바꿔주었던 것을 기억하는가?
결론적으로는 비트연산을 통해 자동적으로 10이 된 것이다.


사실 그럴싸 하게 '비트연산'이라는 말만 붙어있을 뿐
왼쪽으로 1비트씩 움직이는 것이 곧 2를 곱하는 것과 같은 효과라는 사실을 알고 있다면,
손으로 계산하는 것이나, 컴퓨터스러운 마인드(?)로 계산하는 것이나 큰 차이가 있다고 보기는 어렵다.
하지만 그것은 어디까지나 일반적인 양수 나누기 양수에서만 그렇다고 해두고 싶다.



Negative Divisor and Dividend

양수를 음수로 나누거나, 음수를 양수로 나누거나, 음수를 음수로 나누는 경우에는 어떨까?
먼저 음수를 표시하기 위해서는 2's Complement를 이용해야 한다.
맨 앞에 있는 bit를 sign bit로 사용하여 음수를 나타내는 보편적인 방법이다.
보다 자세한 내용에 대해서는 http://en.wikipedia.org/wiki/2%27s_complement 를 참고하기 바란다.

이러한 음수의 나눗셈에 대해서 위에서 언급된 방법을 사용할 수 있을까?
답은 그렇다 이지만, 정확히 말하면 같은 방법을 쓸 수는 없다.
R과 D를 비교하는 부분만 보더라도 그렇다.

만약 Divisor가 음수라면, R은 대부분의 경우에서 항상 D보다 큰 값을 가지게 되는 것이다.
또한 이런 경우에 대해서는 R - D 대신 R + D를 해야 한다.

실제 컴퓨터에서는 위의 과정을 조금 더 발전시켜
음수 양수든 가릴 것 없이 모두 계산 가능한 알고리즘을 택하고 있다.
숫자의 크기를 직접 비교하는 것이 아니라, 숫자의 합이 음수인지 양수인지를 확인하는 방법이 주가 되고 있다.
그 알고리즘은 다음과 같다.

1. R과 D의 부호를 비교한다.
1-1. R과 D의 부호가 다르다면 R' = R + D를 수행하고,
1-2. R과 D의 부호가 같으면 R' = R - D를 수행한다.

2. 이렇게 얻어낸 R' 과 R의 부호를 비교한다. (R'은 R의 메모리에 저장된다.)
2-1. R'이 R과 부호가 다르면, R의 메모리를 원래의 R로 복구하고 Q의 첫번째 자리수를 0으로 설정한다.
2-2. R'이 R과 부호가 같으면, Q의 첫번째 자리수를 1로 설정한다.


2번에서는 간단히 생각해서
양수와 양수의 나눗셈에서 나머지를 구하다가 나머지가 음수로 구해지는 경우를 떠올리면 된다.
당연히 음수의 나머지가 나오는 나눗셈을 해서는 안된다. 
10진수의 범위에서는 몫을 1만큼 줄여서 다시 계산을 해보면 되지만, 
2진수에서는 0과 1 뿐이므로 다시 계산을 하고 말고 할 것이 없다. 그냥 다음 단계로 넘어가면 된다.

이제 좀 더 발전된 알고리즘을 가지고 109 ÷ (-5) 를 계산해 보도록 하자.



Binary Division of Negative Numbers

109와 -5를 8bit의 이진수로 표현해 보자.
109는 01101101 이며, -5는 11111011 이다.
이것을 가지고 앞에서 했던 것과 같이 단계를 차례차례 밟아가면서 계산을 수행해 보도록 하자.
이번엔 Step을 따로 나누지는 않겠다.
R은 0으로 채워지는데, 만약 Dividend가 음수라면 1로 채워져야 한다.

R        Q
00000000 01101101
00000000 11011010
R과 Q를 왼쪽으로 1비트씩 움직인다. (첫번째 비트연산)
11111011 11011010 R과 D의 부호가 다르므로 R = R + D를 한다.
00000000 11011010 R이 이전과 부호가 달라졌다. 따라서 원래의 R로 다시 복구한다.

00000001 10110100 R과 Q를 왼쪽으로 1비트씩 움직인다. (두번째 비트연산)
11111100 10110100 R과 D의 부호가 다르므로 R = R + D를 한다.
00000001 10110100 R이 이전과 부호가 달라졌다. 따라서 원래의 R로 다시 복구한다

00000011 01101000 R과 Q를 왼쪽으로 1비트씩 움직인다. (세번째 비트연산)
11111110 01101000 R과 D의 부호가 다르므로 R = R + D를 한다.
00000011 01101000 R이 이전과 부호가 달라졌다. 따라서 원래의 R로 다시 복구한다

00000110 11010000 R과 Q를 왼쪽으로 1비트씩 움직인다. (네번째 비트연산)
00000001 11010000 R과 D의 부호가 다르므로 R = R + D를 한다.
00000001 1101000R이 이전과 부호가 같다. 따라서 Q의 첫번째 자리수를 1로 바꾼다.

00000011 10100010 R과 Q를 왼쪽으로 1비트씩 움직인다. (다섯번째 비트연산)
11111110 10100010 R과 D의 부호가 다르므로 R = R + D를 한다.
00000011 10100010 R이 이전과 부호가 달라졌다. 따라서 원래의 R로 다시 복구한다.

00000111 01000100 R과 Q를 왼쪽으로 1비트씩 움직인다. (여섯번째 비트연산)
00000010 01000100 R과 D의 부호가 다르므로 R = R + D를 한다.
00000010 0100010R이 이전과 부호가 같다. 따라서 Q의 첫번째 자리수를 1로 바꾼다.

00000100 10001010 R과 Q를 왼쪽으로 1비트씩 움직인다. (일곱번째 비트연산)
11111111 10001010 R과 D의 부호가 다르므로 R = R + D를 한다.
00000100 10001010 R이 이전과 부호가 달라졌다. 따라서 원래의 R로 다시 복구한다.

00001001 00010100 R과 Q를 왼쪽으로 1비트씩 움직인다. (여덟번째 비트연산)
00000100 00010100 R과 D의 부호가 다르므로 R = R + D를 한다.
00000100 0001010R이 이전과 부호가 같다. 따라서 Q의 첫번째 자리수를 1로 바꾼다.



나눗셈을 마치고, Divisor 와 Dividend의 부호가 다른 경우 Q를 2's Complement로 Negate 한다.
즉, 00010101양수 21에 해당하므로, 이를 음수인 -21로 바꾸는 작업을 하는 것이다.

00010101 -> 11101010 + 1 = 11101011 (= -21)

Reminder는 도출된 결과 그대로를 이용하면 된다.
이렇게 함으로써 몫 -21, 나머지 4 라는 결과를 얻었다.