[컴퓨터 구조] 컴퓨터 연산[3] - 나눗셈

 

 

 

🧐 나눗셈

나눗셈은 다음과 같은 과정을 통해 계산됩니다.

 

나눗셈의 피연산자는 피제수(dividend)와 제수(divisor) 두 개이며,

몫(quotient) 과 나머지(remaunder) 두 개의 결과가 있습니다.

 

여기서 나머지는 제수보다 작습니다.

몫은 무시하고 나머지만을 구하기 위해 나눗샘 명령어를 사용하는 경우도 종종 있습니다.

 

 

 

 

 

 

 

 

🧐 나눗셈 알고리즘의 기본 아이디어

몫 레지스터 64비트를 0으로 초기화시키고 시작합니다.

나눗셈 알고리즘은 매번 반복할 때마다 제수를 오른쪽으로 한 비트씩 자리이동해야 합니다.

 

따라서 제수를 128비트 제수 레지스터의 왼쪽 절반에 넣고 시작합니다.

그리고 피제수와 자리를 맞추기 위해 반복할 때마다 오른쪽으로 한 비트씩 자리이동합니다.

 

나머지(remainder) 레지스터는 피제수로 초기화합니다.

 

또한 컴퓨터는 두 수 중 어느 수가 작은지 한번에 보고 판단할 수 없습니다.

따라서 먼저 피제수에서 제수를 빼줌으로써 판단하는데, 이때 피제수는 나머지 레지스터에 담겨있습니다.

 

만약 이 결과가 양수이면 제수는 피제수와 같거나 더 작습니다.

따라서 몫의 LSB에 1을 추가합니다.(기존 몫을 왼쪽으로 Shift 후 LSB에 1 추가)

 

만약 결과가 음수라면 제수를 나머지 레지스터에 다시 더함으로써 원래의 값을 회복하며, 몫에서는 0을 넣습니다.

 

위 알고리즘의 논리도입니다.

 

 

 

아래는 위 알고리즘을 구현한 논리회로입니다.

 

 

 

 

 

 

⭐️ 예시

간단한 나눗셈 $0111 / 0010 $ 예시를 통해 과정을 살펴보도록 하겠습니다.

반복	단계	몫	제수	나머지
0	초기값([나머지] = [피제수])	0000	0010 0000	0000 0111
1	[나머지] - [제수] 수행	0000	0010 0000	1110 0111
	[나머지] - [제수] 가 [음수]이므로 [나머지] + [제수]를 통한 [나머지] 복구 이후 [몫]을 [왼쪽]으로 1칸 Shift 이후 [LSB]에 [0] 추가.	0000	0010 0000	0000 0111
	[제수]를 [오른쪽]으로 1칸 Shift	0000	0001 0000	0000 0111
2	[나머지] - [제수] 수행	0000	0001 0000	0000 0011
	[나머지] - [제수] 가 [음수]이므로 [나머지] + [제수]를 통한 [나머지] 복구 이후 [몫]을 [왼쪽]으로 1칸 Shift 이후 [LSB]에 [0] 추가.	0000	0001 0000	0000 0111
	[제수]를 [오른쪽]으로 1칸 Shift	0000	0000 1000	0000 0111
3	[나머지] - [제수] 수행	0000	0000 1000	1111 1111
	[나머지] - [제수] 가 [음수]이므로 [나머지] + [제수]를 통한 [나머지] 복구 이후 [몫]을 [왼쪽]으로 1칸 Shift 이후 [LSB]에 [0] 추가.	0000	0000 1000	0000 0111
	[제수]를 [오른쪽]으로 1칸 Shift	0000	0000 0100	0000 0111
4	[나머지] - [제수] 수행	0000	0000 0100	0000 0011
	[나머지] - [제수] 가 [양수]이므로 [몫]을 [왼쪽]으로 1칸 Shift 이후 [LSB]에 [1] 추가.	0001	0000 0100	0000 0011
	[제수]를 [오른쪽]으로 1칸 Shift	0001	0000 0010	0000 0011
5	[나머지] - [제수] 수행	0001	0000 0010	0000 0001
	[나머지] - [제수] 가 [양수]이므로 [몫]을 [왼쪽]으로 1칸 Shift 이후 [LSB]에 [1] 추가.	0011	0000 0010	0000 0001
	[제수]를 [오른쪽]으로 1칸 Shift	0011	0000 0001	0000 0001

 

 

 

 

 

 

 

 

 

 

🧐 나눗셈 인스트럭션

div(divide),

rem(remainder),

divu(diveded unsigned),

remu(remainder unsigned) 의 네 가지 명령어를 사용하여 부호있는, 또는 부호없는 64비트 나눗셈의 몫 또는 나머지를 구합니다.