[컴퓨터시스템] 2의 제곱으로 나눗셈하기

이번 포스팅에서는 2의 제곱으로 정수를 나눌 때 컴퓨터에서의 결과값과 그 과정을 위해 쉬프트 연산이 사용될 수 있음을 알아보고자 합니다.

---

2의 제곱으로 정수를 나눌 때는 오른쪽 쉬프트 연산을 사용합니다. 비부호형 정수에는 논리 쉬프트, 부호형 정수에는 산술 쉬프트를 적용합니다. 우측 쉬프트 때 논리 쉬프트는 좌측에 0을 패딩으로 채워 넣고 산술 쉬프트는 MSB(most significant bit)를 패딩으로 반복하여 채워 넣습니다.

---

컴퓨터에서 정수를 정수로 나누어 정수 결과값을 계산할 때 그 값이 항상 0 방향으로 근사되도록 정의하였습니다. 예로 들어 1.24는 1(floor - 같거나 작은 최근접 정수), -1.24는 -1(ceiling - 같거나 큰 최근접 정수), 0과의 거리가 최소화되도록 근사되어야 합니다.

비부호형 정수에서는 우측 논리 쉬프트 연산을 통해 컴퓨터에서의 정수 나눗셈 정의가 만족되도록 2의 제곱의 나눗셈 연산을 수행할 수 있습니다.

부호형 정수에서는 우측 산술 쉬프트 연산을 사용하여 2의 제곱의 나눗셈 연산을 수행할 수 있지만 조금은 복잡한 과정이 추가되어야 합니다. 양수의 경우 MSB가 0이기 때문에 우측 산술 쉬프트는 우측 논리 쉬프트와 동일한 효과를 나타내며 비부호형 정수와 마찬가지로 정의를 만족하도록 나눗셈 연산을 할 수 있습니다. 하지만 음수의 경우 특별한 처리 없이 우측 산술 쉬프트를 하게 되면 쉬프트로 인해 제거된 비트가 양의 가중치를 가지는 탓에 나누어진 결과값이 실제의 값보다 작아진다는 사실을 관찰할 수 있습니다. 이는 처음에 설명했던 0에 근사하도록 나눈다는 정의에 위배되게 됩니다. 이를 해결하기 위해 음수를 우측 산술 쉬프트하기 전에 바이어스로 (1<<K)-1를 더해주어야 합니다. K는 우측 쉬프트하는 횟수입니다. 이 바이어스는 음수의 쉬프트 결과 값이 0에 가까워지도록 도와줍니다.

---

또 하나 특징적인 사실은 곱셈과는 달리 쉬프트 연산을 통한 2의 제곱 나눗셈을 모든 수의 나눗셈으로 확장하여 일반화할 수 없다는 것입니다.