부스 곱셈 알고리즘 계산기
2의 보수 정수 두 개를 부스 알고리즘으로 곱하는 과정을 레지스터 단계별로 보여 줍니다. 기수-2와 기수-4(수정 부스)를 나란히 놓고 연산 횟수까지 비교합니다.
9 × 15
135
기수-2 부스와 기수-4 수정 부스가 모두 같은 값을 냈습니다. 8비트끼리 곱했으므로 결과는 16비트 0000000010000111입니다.
기수-2 부스 — 레지스터 단계별
| 단계 | Q₀Q₋₁ | 연산 | A (시프트 뒤) | Q | Q₋₁ |
|---|---|---|---|---|---|
| 1 | 10 | −M | 11111011 | 10000111 | 1 |
| 2 | 11 | 없음 | 11111101 | 11000011 | 1 |
| 3 | 11 | 없음 | 11111110 | 11100001 | 1 |
| 4 | 11 | 없음 | 11111111 | 01110000 | 1 |
| 5 | 01 | +M | 00000100 | 00111000 | 0 |
| 6 | 00 | 없음 | 00000010 | 00011100 | 0 |
| 7 | 00 | 없음 | 00000001 | 00001110 | 0 |
| 8 | 00 | 없음 | 00000000 | 10000111 | 0 |
(Q₀, Q₋₁)이 0 1이면 1의 구간이 시작된 것이라 더하고, 1 0이면 끝난 것이라 뺍니다. 0 0과 1 1은 구간 밖이거나 안이라 시프트만 합니다. 8단계가 끝나면 A:Q가 그대로 16비트 답입니다.
기수-4 수정 부스 — 승수를 −2 ~ +2 자리로 다시 적기
| 자리 | 본 세 비트 | 자리값 | 부분곱 |
|---|---|---|---|
| 4^0 | 110 | -1 | -9 |
| 4^1 | 111 | 0 | 0 |
| 4^2 | 001 | +1 | 144 |
| 4^3 | 000 | 0 | 0 |
| 부분곱 합 | 135 | ||
세 비트를 한꺼번에 보아 000→0, 001·010→+1, 011→+2, 100→−2, 101·110→−1, 111→0으로 적습니다. 단계 수가 절반이 되고 ×2는 시프트라 곱셈기가 필요 없습니다. 실제 하드웨어 곱셈기가 쓰는 것이 이쪽입니다.
사용 방법
- 1피승수 M과 승수 Q, 그리고 비트 폭을 넣습니다. 2의 보수로 담기는 범위 안이어야 합니다.
- 2기수-2 표에서 (Q₀, Q₋₁) 두 비트에 따라 더하는지 빼는지 아무것도 안 하는지 확인합니다.
- 3기수-4 표에서 승수가 −2 ~ +2 자리값으로 어떻게 다시 적히는지 봅니다.
- 4연산 횟수 비교에서 연속된 1이 많을수록 부스가 유리한 것을 확인할 수 있습니다.
자주 묻는 질문
2의 보수 표현을 그대로 곱해도 답이 맞기 때문입니다. 소박한 시프트-덧셈 곱셈기는 부호 있는 수를 만나면 절댓값을 곱하고 부호를 나중에 붙여야 해서 보수를 취하는 회로가 따로 필요합니다. 부스는 그 과정 없이 음수를 바로 다룹니다.
2^j + 2^(j−1) + … + 2^i = 2^(j+1) − 2^i이기 때문입니다. 1이 죽 이어져 있으면 그 개수만큼 더하는 대신 한 번 더하고 한 번 빼면 됩니다. 0111₂ = 8 − 1을 쓰는 셈입니다. 예를 들어 15 = 1111₂를 곱할 때 소박한 방법은 네 번 더하지만 부스는 두 번이면 됩니다.
1의 구간이 시작됐는지 끝났는지를 알기 위해서입니다. 0 1이면 구간이 시작된 것이라 더하고, 1 0이면 끝난 것이라 뺍니다. 0 0과 1 1은 구간 밖이거나 구간 안이라 아무것도 하지 않고 시프트만 합니다. Q₋₁은 직전에 밀려난 비트를 기억하는 자리입니다.
누산기 A의 부호를 지켜야 음수 부분합이 살아남기 때문입니다. 논리 우시프트를 쓰면 위에서 0이 채워져 음수가 큰 양수로 바뀌어 버립니다. 이 구현은 BigInt의 >> 연산이 음수에서 산술 시프트라는 성질을 그대로 씁니다.
세 비트를 한꺼번에 보아 승수를 −2·−1·0·+1·+2 자리값으로 다시 적습니다. 단계 수가 절반(⌈n/2⌉)이 되고, ×2는 시프트라 곱셈기가 필요 없습니다. 실제 하드웨어 곱셈기가 쓰는 것이 이쪽입니다.
아닙니다. 1과 0이 번갈아 나오는 승수(0101…)에서는 기수-2 부스가 매 단계 덧셈이나 뺄셈을 해서 소박한 방법보다 오히려 연산이 늘 수 있습니다. 이 계산기에서 승수를 85(= 01010101₂)로 넣어 보면 여덟 단계 모두 연산하는 것을 볼 수 있습니다. 기수-4는 단계 수가 절반으로 고정돼 있어 이런 최악의 경우에도 안전합니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 검증은 자바스크립트 BigInt 곱셈을 정답지로 삼아 했습니다. 4비트에서는 −8~7의 모든 조합 256가지를 빠짐없이 훑었고, 8비트에서도 넓게 대조했습니다.
- 경계값을 따로 고정했습니다. −2^(n−1)은 절댓값을 취할 수 없는 자리(2의 보수에서 양수 쪽에 짝이 없습니다)라 부호를 따로 다루는 구현이 가장 잘 틀리는 지점입니다. −128 × −128, −128 × −1을 4·8·16비트에서 확인했습니다.
- 홀수 비트 폭도 검사합니다. 기수-4는 세 비트씩 겹쳐 보려면 폭이 짝수여야 해서 홀수면 부호 확장해 다루는데, 그 처리가 맞는지 5·7·9비트에서 고정했습니다.
- 기수-4의 자리값이 언제나 −2 ~ +2 안에 드는 것, 그 자리값을 4의 거듭제곱 자리로 다시 더하면 원래 승수가 되는 것을 따로 확인했습니다. 재부호화가 맞는지 보는 가장 곧은 검산입니다.
- 연속된 1에서 부스의 연산 횟수가 줄어드는 것(15 = 1111₂에서 4번 → 2번), 1과 0이 번갈아 나오면 오히려 느는 것(85 = 01010101₂에서 8번)을 테스트로 남겨 두었습니다. 부스가 항상 빠르지는 않다는 것을 보이는 자리입니다.
- 비트 폭은 4부터 32까지 다룹니다. 기수-2는 비트 수만큼 단계가 나오므로 그보다 크면 표가 화면에 들어오지 않습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.