C++で数値Nが基数b表記において1から始まるかどうかを判定する方法

本記事では、数値Nと基数bが与えられたとき、「Nを基数bで表記すると先頭の桁が1になるかどうか」を判定する方法をC++で解説します。

まず具体例を見てみましょう。数値6を2進数で表すと「110」であり、先頭は1です。4進数で表すと「12₍₄₎」となり、これも先頭が1です。このように、同じ数でも基数によって表記が変わり、先頭の桁が1になる場合とならない場合があります。

判定の考え方（数学的な背景）

数値Nを基数bで表すと、m+1桁の数列 d_m d_m-1 … d₀ になり、次の関係が成り立ちます。

d_m × b^m + d_m-1 × b^m-1 + … + d₀ × b⁰ = N

ここで、先頭の桁 d_m が「1」であるような数の範囲を考えます。最小値は 1 × b^m = b^m です。一方、最大値は残りの下位の桁がすべて最大値（b − 1）になった場合で、b^m + (b^m − 1) = 2 × b^m − 1 となります。

つまり、Nが基数b表記で1から始まる ⟺ ある整数mについて b^m ≤ N ≤ 2 × b^m − 1 が成り立つということです。

さらに、探索すべきmの範囲には上限があります。どんな基数で表記しても、その桁数は2進数表記の桁数を超えません。2進数では数が0と1だけで表され、その桁数は常に最も長くなるためです。Nの2進数表記における桁数は ⌊log₂N⌋ + 1 なので、mは1から ⌊log₂N⌋ の範囲を調べれば十分です。

以上より、m = 1 から ⌊log₂N⌋ まで順番に確認し、いずれかのmで b^m ≤ N ≤ 2 × b^m − 1 が成立すれば「1から始まる」（true）、どこでも成立しなければ「1から始まらない」（false）と判定できます。

C++による実装例

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

// numberをbase進法で表したとき、先頭の桁が1かどうかを判定する
bool isStartWithOne(int number, int base) {
    int m = log2(number); // 探索範囲の上限（2進数表記の桁数 - 1）
    for (int i = 1; i <= m; i++) {
        // numberが [base^i, 2*base^i - 1] の範囲に入れば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 << "Can be represented";
    } else {
        cout << "Can not be represented";
    }
    return 0;
}

実行結果

Can be represented

この例では num = 19、base = 16 としています。19を16進数で表すと「13」であり、先頭の桁が1なので「Can be represented（1から始まる表記が存在する）」と出力されます。

計算量

ループは最大 ⌊log₂N⌋ 回繰り返されるため、時間計算量は O(log N) です。追加のメモリも不要で、空間計算量は O(1) となります。