나눗셈 알고리즘을 활용해 부호 없는 정수를 나누는 방법을 살펴보겠습니다. 나눗셈 알고리즘 중 일부는 종이 위에서 손으로 계산하는 방식으로 적용되고, 또 다른 알고리즘은 디지털 회로에 직접 구현됩니다. 나눗셈 알고리즘은 크게 느린(slow) 나눗셈 알고리즘과 빠른(fast) 나눗셈 알고리즘 두 가지 유형으로 나눌 수 있으며, 느린 나눗셈 알고리즘에는 복원(restoring) 방식, 비수행 복원(non-performing restoring) 방식, SRT 방식, 비복원(non-restoring) 방식이 포함됩니다.
이 튜토리얼에서는 0 < 제수(divisor) < 피제수(dividend)라는 조건을 전제로, 그중에서도 복원(Restoring) 나눗셈 알고리즘에 대해 자세히 알아보겠습니다.
문제 해결 접근 방식
이 알고리즘에서는 세 개의 레지스터를 사용합니다. 레지스터 Q에는 몫(quotient)을, 레지스터 A에는 나머지(remainder)를, M에는 제수(divisor)를 저장합니다. A의 초기값은 항상 0으로 설정되며, 연산 과정에서 음수가 되면 원래 값으로 되돌려 놓는데(복원), 바로 이 동작 때문에 이 방식을 '복원 나눗셈'이라고 부릅니다.
레지스터를 다음 값으로 초기화합니다.
- Q = 피제수(Dividend)
- A = 0
- M = 제수(Divisor)
- N = 피제수의 비트 수
AQ 좌측 시프트: 레지스터 A와 Q를 하나의 단위로 취급하여 함께 왼쪽으로 한 칸 이동시킵니다.
뺄셈: A에서 M을 빼고 그 결과를 다시 A에 저장합니다.
A의 최상위 비트(MSB) 확인:
- MSB가 0이면 Q의 최하위 비트(LSB)를 1로 설정합니다.
- MSB가 1이면 Q의 최하위 비트(LSB)를 0으로 설정합니다.
복원 및 반복: A의 값을 복원하고 카운터 N을 1만큼 감소시킵니다.
N = 0이면 루프를 종료하고, 그렇지 않으면 좌측 시프트 단계부터 다시 반복합니다.
모든 과정이 끝나면 레지스터 Q에 최종 몫이 저장됩니다.
흐름도
예제
위 접근 방식을 구현한 C++ 코드
#include <iostream>
using namespace std;
int main(){
// 모든 변수를 피제수 = 8, 제수 = 3으로 초기화합니다.
int Q = 8, q = 1, M = 3;
short N = 4;
int A = Q;
M <<= N;
// 비트 연산을 통해 나눗셈을 수행하는 반복문
for(int i = N - 1; i >= 0; i--) {
A = (A << 1) - M;
// A의 최상위 비트(MSB) 확인
if(A < 0) {
q &= ~(1 << i); // i번째 비트를 0으로 설정
A = A + M; // A 값 복원
} else {
q |= 1 << i; // i번째 비트를 1로 설정
}
}
cout << "몫: " << q;
return 0;
}출력
몫: 2
피제수가 8이고 제수가 3이므로, 실행 결과 몫은 2가 됩니다(8 ÷ 3 = 2, 나머지 2).
결론
이 튜토리얼에서는 부호 없는 정수를 위한 복원 나눗셈 알고리즘을 다루었습니다. 흐름도와 비트 연산을 활용해 문제를 해결하는 간단한 접근 방식을 살펴보았고, 이를 구현한 C++ 프로그램도 함께 확인했습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.