Division
dividend = quotiend x divisor + remainder
결과적으로는 몫 * 제수 + 나머지 등식이 성립한다.
2n 비트 / n비트 몫 최대 n+1 비트
실제 정수로 선언된 변수 가지고 하면, 앞의 32비트 영을 붙여서 하기 때문에 33비트는 안나온다. 33비트가 나오면 divied overflow라고 한다. 그러므로 책에서는 일절 언급이 없다.
10진수 나누기
1001010 / 1000 1000 빼고 이런 식. 빼지느냐 안 뺴지느냐 . 컴퓨터는 그걸 모르니까. 일단 빼 보고 뺀 결과가 +면 몫이 1 -면 몫이 0, -가 되었을 때, 빼기 전 상태로 만들어줘야 하므로 다시 더해주는 과정이 필요하다.
first version - 곱하니 첫 번째 버전과 비슷
ex) 7 / 2
quotient 레지스터 - 몫. 현재 아무런 관계 없음 divisor - 왼쪽에 0010이 들어감 . 아래쪽은 0으로 채워짐 remainder ->0000 0111 피제수가 들어가 있다.
- 맨 처음 빼기. 2의 보수를 더한다.
- divisor 0010 0000을 2의 보수 취해서 1110 0000을 더한다
- 1110 0111이 된다.
- remainder가 마이너스가 되었다.
- 다시 더해서 빼기 전 상태로 바꾸어 준다.
- 0000 0111
-
shift div reigster를 오른쪽으로 한칸 민다. -> 0001 0000
- 이 divisor를 빼 본다. 그럼 2의 보수를 취한다 1111 0000 이걸 reaminderv에 더하
-
1111 0111이 된다. 그러면 또 음수가 나오므로 다시 더해서 뺴기 전 상태로 만들어준다.
- 0000 0111
- 그리고 나서 diviosr를 오른쪽으로 한칸 민다 -> 0000 1000
- 보수를 취해서 remainder에 빼준다. 1111 1000이다.이걸 remaninderd에 더하면
- 1111 1111이다. 또 마이너스 이므로 다시 더해서 원래전으로 만들어준다.
- 0000 0111
- 그리고 나서 divisor를 오른쪽으로 한 칸 민다 -> 0000 0100. 이걸 보수화해준11
- 1111 1100 이걸 remainder에 더한다. -> 0000 0011
17 플러스가 되었으므로 다시 더하기 안해줘도 된다. 이 상태에서 shift div right를 해주면 0000 0010이 되므로 이걸 0000 0011에 빼주면 0000 0001이 된다.
- 몫을 하나 추가해준다. shift left하면서 끝에 1이 들어가게 됌
- 다시 빼주기 위해서 divisor를 shift right1 해주면 0000 0001
- 이걸 빼주려면 보수화 - 1111 1110 이걸 더해주면 0000 0001이 된다.
- 위에가 0이 되었어도, 빼지는 거니까 몫은 +1 부호비트가 0이 되고 shift left 하면서 1
이게 첫 번째 알고리즘.
두 번째 알고리즘 divisor -> 32비트, ALU도 32비트로. 내려가면서 빼는 대신에, 같은 자리에서 빼고, 빼지는 녀석 중간 결과를 위로 올려보낸다.
마지막 알고리즘
향상된 함수 -> 복잡한 더했다가 뺐다 하지 말고, 몫은 0이라고 가정하고 remainder를 shift left 해버린 것이다.
그 다음은 똑같다.
-
7/2를 하는데, divisor 에는 2, reaminder 에는 7이 들어가 있다. 처음 loop 반복하기 전에 처음 몫은 0 이라고 가정하고 shift left register 한번 한다
- 그러면 remainder는 0000 1110이 된다.
- 0010을 2의 보수화 취해서 remainder에 더해준다.
- 1110 1110이 된다.
- 마이너스 이므로 다시 restoring 해준다.
- 0000 1110이 되고, 여기서 shift left register를 해주면
- 0001 1100이 된다.
- 0010을 2의 보수화 취해서 remainder에 더해준다.
- 1111 1100 또 마이너스 이므로 restoring
- 그리고 나서 shift left register를 해주면
- 0011 1000이 된다.
- 0010을 보수화하면 1110 이걸 더해주면 +가 되므로, 몫이 1이 된다. shift left하면
- 0011 0001이 된다.
- 0010을 보수화 해서 더해주면 1110이걸 더해주면 +가 되므로 또 몫이 1이
- 0010 0011
- 의미없는 0이 계속 따라가게 되니까. 나중에 최종적인 나머지가 밀려서 올라가 있다.
- 그걸 왼쪽 반만 shift right해서 맞춰줘야 한다. 그래서
- 0001 0011이 된다. (사진 회색 제로 참고)
Divide in MIPS
몫은 lo register에 나머지는 hi rigister에 들어간다.
제수와 피제수의 부호가 같으면 + 다르면 - 나머지의 부호는 항상 피제수의 부호와 같다. 부호있는 정수를 나눠주는 알고리즘은 없다.
non restoring division
원상복귀 안해주는 division
remainder 레지스터에서 divisor 레지스터를 뺴는 거다. shift left를 한다 -> 곱하기 2. 그리고서, 또 올라가면 또 뺀다. divisor를 다시 뺴는거다. 몫이 0이 되었을 때, 하는 건 무조건 이걸 하고 마이너스가 되면 다시 더해서 원래 빼기 전상태로 만들고, shift라는게 곱하기 2이니까.
결국은 2 리메인더- div
-값을 그냥 가져간다. 그래서 런 리스토링. 리메인더가 마이너스면 빼기를 하지 말고 더하기를 한다. 이걸 풀어보면 빼기 전의 값을 만들어서 두개 만들어서 빼주거나 더해주는건 결과가 같다.
더하기든 뺴기든 한번만 하면 된다. +면 -기하고. -다 그러면 더하기를 한다.
51분 까지 들음
참고자료
컴퓨터 구조 및 설계 지음 DAVID A.PATTERSON, JOHN L>HENNESSY