이 튜토리얼에서는 비트 연산자(bitwise operator)만을 사용하여 주어진 두 수를 곱하는 프로그램을 작성해 보겠습니다.
곱셈에는 왼쪽 시프트(<<) 연산자를 사용하고, 나눗셈에는 오른쪽 시프트(>>) 연산자를 사용합니다. 왼쪽으로 1비트 시프트하면 값이 2배가 되고, 오른쪽으로 1비트 시프트하면 값이 절반이 되는 원리를 활용하는 것입니다.
핵심 아이디어
두 수 x, y의 곱은 다음과 같이 분해할 수 있습니다.
- y가 짝수일 때: x × y = (x × 2) × (y ÷ 2)
- y가 홀수일 때: x × y = (x × 2) × (y ÷ 2) + x
즉, 두 번째 수(y)가 홀수가 되는 순간마다 첫 번째 수(x)를 결과값에 더해주면 됩니다. 이 과정을 반복하면 곱셈 기호 없이 덧셈과 시프트 연산만으로 곱셈 결과를 얻을 수 있습니다.
알고리즘
문제를 해결하는 단계는 다음과 같습니다.
- 두 개의 숫자를 초기화합니다.
- 두 번째 숫자가 0이 될 때까지 반복하는 루프를 작성합니다.
- 두 번째 숫자가 홀수이면(최하위 비트가 1이면), 첫 번째 숫자를 결과값에 더합니다.
- 첫 번째 숫자를 왼쪽으로 1비트 시프트합니다.
- 두 번째 숫자를 오른쪽으로 1비트 시프트합니다.
C++ 구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
int multiplyTwoNumbers(int a, int b) {
int result = 0;
while (b > 0) {
if (b & 1) {
result += a;
}
a = a << 1;
b = b >> 1;
}
return result;
}
int main() {
cout << multiplyTwoNumbers(75, 4) << endl;
cout << multiplyTwoNumbers(90, 9) << endl;
cout << multiplyTwoNumbers(83, 66) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
300 810 5478
동작 원리 살펴보기
예를 들어 90 × 9의 경우를 살펴보겠습니다.
- b = 9는 홀수 → result에 90을 더함 (result = 90), a = 180, b = 4
- b = 4는 짝수 → 건너뜀, a = 360, b = 2
- b = 2는 짝수 → 건너뜀, a = 720, b = 1
- b = 1은 홀수 → result에 720을 더함 (result = 810), b = 0
루프가 종료되면 최종 결과인 810이 반환됩니다. 이 방식은 컴퓨터 내부에서 실제로 곱셈이 처리되는 방식과 유사하며, 곱셈 명령어를 직접 사용할 수 없는 환경에서도 유용하게 활용할 수 있습니다.