【C++】数値が任意の基数(2〜32)で指定した桁数として表現できるか判定する方法

ある整数 n と桁数 d が与えられたとき、n を「2 から 32 までのいずれかの基数」における d 桁の数値として表現できるかどうかを判定する方法を解説します。

例えば、n = 8、d = 4 の場合を考えてみましょう。8 は 2 進法では「1000」と表され、これはちょうど 4 桁です。このように、特定の基数において指定された桁数で表現できるかを確認するのが本記事のテーマです。

アルゴリズムの考え方

基本的なアプローチはシンプルで、「2 から 32 までのすべての基数を一つずつ順番にチェックする」というものです。各基数に対する判定は、以下の手順で行います。

• 終了条件: 数値が基数より小さく、かつ残りの桁数が 1 であれば true を返します(その基数でちょうど d 桁に収まることを意味します)。
• 再帰処理: 桁数が 1 より大きく、数値が基数以上であれば、num ÷ base を計算して最下位の桁を取り除き、桁数を 1 つ減らして再帰的に同じ判定を繰り返します。
• それ以外: 上記のいずれにも当てはまらない場合は false を返します。

C++ サンプルコード

#include <iostream>
using namespace std;

// 指定した基数で num が d 桁として表現できるかを再帰的に判定する
bool isRepresentedInDDigits(int num, int d, int base) {
    if (d == 1 && num < base)
        return true;
    if (d > 1 && num >= base)
        return isRepresentedInDDigits(num / base, --d, base);
    return false;
}

// 2〜32 のすべての基数を順番にチェックする
bool checkNumber(int num, int d) {
    for (int base = 2; base <= 32; base++)
        if (isRepresentedInDDigits(num, d, base))
            return true;
    return false;
}

int main() {
    int num = 8;
    int dig = 2;
    if (checkNumber(num, dig))
        cout << "Can be represented";
    else
        cout << "Can not be represented";
}

実行結果

Can be represented

この例では num = 8、dig = 2 としています。8 は 3 進法では「22」となり、ちょうど 2 桁で表現できるため、「Can be represented(表現できる)」と出力されます。

処理の流れを具体例で確認

num = 8、d = 4、base = 2 の場合、再帰処理は次のように進みます。

1. 8 ≥ 2 かつ d = 4 > 1 なので、8 ÷ 2 = 4 となり、d は 3 に減ります
2. 4 ≥ 2 かつ d = 3 > 1 なので、4 ÷ 2 = 2 となり、d は 2 に減ります
3. 2 ≥ 2 かつ d = 2 > 1 なので、2 ÷ 2 = 1 となり、d は 1 に減ります
4. 1 < 2 かつ d = 1 なので true を返す → 8 は 2 進法で 4 桁(1000)であることが確認できます

まとめ

各基数ごとの判定は最大 d 回の除算で完了するため、全体の計算量は O(31 × d) 程度と非常に効率的です。再帰を while ループに置き換えて書き直すことも可能ですが、ロジックの明快さという点では再帰版の方が理解しやすいでしょう。