이번 글에서는 주어진 숫자가 3의 배수인지 판별하는 프로그램을 C++로 작성하는 방법을 알아보겠습니다.
일반적인 접근 방식의 한계
가장 널리 알려진 방법은 숫자의 모든 자릿수를 더한 뒤, 그 합이 3의 배수인지 확인하는 것입니다. 합이 3으로 나누어떨어지면 원래 숫자도 3의 배수입니다. 하지만 이 방법은 숫자를 자릿수 단위로 하나씩 분해하고 반복적으로 덧셈을 수행해야 하므로, 가장 효율적인 해결책이라고 보기는 어렵습니다.
효율적인 해결책: 이진수 비트 카운트 활용
훨씬 효율적인 방법은 숫자의 이진수 표현에서 비트(bit) 개수를 활용하는 것입니다. 홀수 번째 위치에 있는 set bit(1)의 개수와 짝수 번째 위치에 있는 set bit의 개수 차이가 3의 배수라면, 해당 숫자 역시 3의 배수입니다.
구현 방식은 다음과 같습니다. 반복문 안에서 숫자의 비트를 두 칸씩 오른쪽으로 시프트하면서 홀수 위치와 짝수 위치의 set bit 개수를 각각 세고, 마지막에 두 값의 차이가 3의 배수인지 재귀적으로 검사하여 결과를 반환합니다.
알고리즘이 성립하는 원리
이 방법이 가능한 이유는 2² ≡ 1 (mod 3)이라는 성질 때문입니다. 이진수의 각 자릿값 중 짝수 번째 자리(2⁰, 2², 2⁴, …)는 3으로 나눈 나머지가 1이고, 홀수 번째 자리(2¹, 2³, 2⁵, …)는 나머지가 2, 즉 −1 (mod 3)입니다. 따라서 짝수 위치와 홀수 위치의 set bit 개수 차이가 0 또는 3의 배수라면 전체 숫자도 반드시 3으로 나누어떨어집니다. 이는 10진수에서 11의 배수를 판별하는 방법과 유사한 원리입니다.
동작 예시
간단한 예제로 판별 과정을 살펴보겠습니다.
입력
n = 24
판별 과정
이진수 표현 = 11000
짝수 위치 set bit 개수 = 1, 홀수 위치 set bit 개수 = 1
차이 = 0 → 3으로 나누어떨어짐
24는 실제로 3 × 8 = 24이므로 3의 배수가 맞습니다.
C++ 구현 코드
다음은 위에서 설명한 알고리즘을 구현한 전체 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
int isDivisibleBy3(int n) {
int oddBitCount = 0;
int evenBitCount = 0;
if (n < 0)
n = -n;
if (n == 0)
return 1;
if (n == 1)
return 0;
while (n) {
if (n & 1)
oddBitCount++;
if (n & 2)
evenBitCount++;
n = n >> 2;
}
return isDivisibleBy3(oddBitCount - evenBitCount);
}
int main() {
int n = 1241;
cout<<"The number "<<n;
if (isDivisibleBy3(n))
cout<<" is a multiple of 3";
else
cout<<" is not a multiple of 3";
return 0;
}
코드 설명
핵심 로직을 단계별로 정리하면 다음과 같습니다.
- 음수 입력은 부호를 제거하여 양수로 변환한 뒤 처리합니다.
- n이 0이면 3의 배수이므로 1을, n이 1이면 아니므로 0을 반환합니다(재귀 호출의 종료 조건).
- while 루프에서 n & 1로 최하위 비트를, n & 2로 그 다음 비트를 검사하여 각각 oddBitCount와 evenBitCount에 더합니다.
- n을 오른쪽으로 2비트 시프트(>> 2)하여 다음 위치의 비트 쌍으로 이동합니다.
- 루프가 끝나면 두 카운트의 차이를 인자로 함수를 재귀 호출하여 최종 판별 결과를 얻습니다.
실행 결과
The number 1241 is not a multiple of 3
실행 결과를 해석하면 "숫자 1241은 3의 배수가 아닙니다"라는 의미입니다. 이처럼 비트 연산만으로 자릿수 합산 방식보다 적은 연산으로 3의 배수 여부를 빠르게 판별할 수 있습니다.