C++로 숫자 N이 b진법에서 1로 시작하는지 확인하는 방법

숫자 N과 진법 b가 주어졌을 때, N을 b진법으로 표현했을 때 맨 앞자리 숫자가 1인지 확인하는 프로그램을 만들어 보겠습니다. 예를 들어 숫자 6이 주어졌다면 이진수로는 110이므로 1로 시작하고, 4진법으로 표현하면 12₄ 역시 마찬가지로 1로 시작합니다.

접근 방식

어떤 수 N이 b진법으로 표현되면 m+1자리 숫자 나열 b_m b_m-1 … b₀이 됩니다. 이는 다음 등식을 의미합니다.

b_m·b^m + b_m-1·b^m-1 + … + b₀·b⁰ = N

만약 맨 앞자리 숫자가 1이라면, m+1자리로 표현할 수 있는 수 중 가장 큰 값은 2·b^m − 1입니다. 따라서 N이 다음 범위에 속하면 N은 b진법에서 반드시 1로 시작합니다.

b^m ≤ N ≤ 2·b^m − 1

또 한 가지 주목할 점은 m이 ⌊log₂N⌋을 초과할 수 없다는 것입니다. 어떤 수를 2진법으로 표현하면 0과 1만으로 이루어진 수열이 되는데, 이 수열의 길이는 항상 다른 진법 표현보다 길거나 같으며 그 길이는 ⌊log₂N⌋ + 1과 같습니다. 따라서 주어진 수 N이 b진법에서 1로 시작하는지 확인하려면 m = 1부터 m = ⌊log₂N⌋까지 순회하면서 각 m값에 대해 N이 위 범위에 속하는지 검사하고, 그 결과에 따라 true 또는 false를 반환하면 됩니다.

예제 코드

#include <iostream>
#include <cmath>
using namespace std;

bool isStartWithOne(int number, int base) {
    int m = log2(number);
    for (int i = 1; i <= m; i++) {
        // number가 해당 범위 안에 있으면 1로 시작함
        if (number >= pow(base, i) && number <= 2 * pow(base, i) - 1)
            return true;
    }
    return false;
}

int main() {
    int num = 19, base = 16;
    if (isStartWithOne(num, base)) {
        cout << "표현 가능합니다";
    } else {
        cout << "표현할 수 없습니다";
    }
}

동작 원리

예제에서는 num = 19, base = 16입니다. 19를 16진수로 표현하면 13₁₆이므로 맨 앞자리가 1이고, 함수가 true를 반환하여 "표현 가능합니다"가 출력됩니다. 이 알고리즘은 최대 ⌊log₂N⌋번만 검사하면 되므로 시간 복잡도는 O(log₂N)입니다.

출력 결과

표현 가능합니다