【C++】任意の基数変換アルゴリズムを実装してみた。～p進数からq進数へラクに変換したい～

お急ぎの方は「5. 実装コード」の項を参照。

はじめに
実装にあたって
基数変換のアルゴリズム
プログラムに落とし込んでいく
実装コード
例
参考記事
更新履歴

はじめに

AtCoder をやっているとたまに問われることがある「基数変換」。「10進数を2進数へ変換せよ」くらいであれば C++ の標準ライブラリにあるstd::bitsetなどを使えばいいのだが、「4進数を5進数へ」や「3進数を7進数へ」などと言われると、その場で書く場合にはかなり手間取る (そんな問題があるかは知らないが) 。ということで今回は、任意の基数変換 ( $p$ 進数から $q$ 進数へ変換する) アルゴリズムを実装してみる。

実装にあたって

今回、入出力する変数は共に文字列型とした。これは、16進数にはa, b, c, d, e, fの文字が使われているからである。また、ここで実装するアルゴリズムは整数にしか対応していない (小数の基数変換はできない) 。なお、動作検証に用いた C++ のバージョンは C++20 である。

今回の実装する関数の外枠はこんな感じ。

#include <iostream>
#include <string>

// x は変換元の数を文字列化したもの, from は変換元の数の基数(p), to は変換先の数の基数(q)
std::string radix_conversion(const std::string& x, const int& from, const int& to)
{
    std::string res = ""; // 変換後の文字列

    // 何かしらの処理

    return res;
}

基数変換のアルゴリズム

$p$ 進数の整数 $x_{(p)}$ を $q$ 進数の整数 $y_{(q)}$ へ基数変換するアルゴリズムは、一般的に以下のようになる。

$x$ の各桁を走査し、右から $i$ 桁目の $x_i$ について $x_i p^{i-1}$ を一時変数 $\mathrm{sum}$ に加算する。すなわち、 $\mathrm{sum} = \displaystyle \sum_{i=1}^{|x|} x_i p^{i-1}$ である ( $|x|$ は $x$ の桁数を表す) 。ここで、 $\mathrm{sum}$ は $x$ を10進数表示したものになる。
がになるまで次の操作を繰り返す。
- $\rm{sum}$ を $j$ 回目に $q$ で割った余りを $y$ の右から $j$ 桁目とする。
- $\rm{sum}$ を $\displaystyle \bigg\lfloor \frac{\mathrm{sum}}{q} \bigg\rfloor$ に置き換える。

プログラムに落とし込んでいく

前述のアルゴリズムを実際にプログラムに落とし込んでいくわけだが、今回は入出力を文字列で管理するため、変換に使う文字のテーブルtableをあらかじめ用意しておこう。これを拡張することで、変換できる基数を自由に変更できる。ここではひとまず2~16進数までが扱えるようtable = 0123456789abcdefとしておいた。

すると、手順1は以下のように書ける。

// Conversion table.
// To be changed as appropriate.
const std::string table = "0123456789abcdef";

unsigned long sum = 0;
for (char c : x)
{
    sum = sum * from + table.find(c);
}

s.find(c)は文字列 $s$ の中で最初に文字 $c$ と一致するインデックスを返す関数である。

cpprefjp.github.io

これを使うとtableから一発で $c_{(p)}$ の10進数表示を求められるので便利。

続いて、手順2は以下のように書ける。

std::string res = "";
do
{
    int mod = sum % to;
    res = table[mod] + res;
    sum /= to;
} while (sum);

do while文を用いる上にループ条件にsumを埋め込むという少々トリッキーな実装だが、bool型変数は0のときにのみfalseとなり、それ以外はtrueとなることを利用しており、こうすることで簡潔な記述となる。

以上でアルゴリズム自体は完成。まとめるとこんな感じになる。

#include <iostream>
#include <string>

// Arbitrary radix conversion
std::string radix_conversion(const std::string& x, const int& from, const int& to)
{
    // Conversion table.
    // To be changed as appropriate.
    const std::string table = "0123456789abcdef";

    unsigned long sum = 0;
    for (char c : x)
    {
        sum = sum * from + table.find(c);
    }

    std::string res = "";
    do
    {
        int mod = sum % to;
        res = table[mod] + res;
        sum /= to;
    } while (sum);

    return res;
}

最後に、対応していない基数が指定されたときに警告を出すようにするためにassertの処理を組み込んでおく。これは最低限のバグを防ぐための記述なので、アルゴリズム自体には不要である。

cpprefjp.github.io

assert((2 <= from && from <= 16) && (2 <= to && to <= 16));

実装コード

#include <iostream>
#include <string>
#include <cassert>

// Arbitrary radix conversion
std::string radix_conversion(const std::string& x, const int& from, const int& to)
{
    // Conversion table.
    // To be changed as appropriate.
    const std::string table = "0123456789abcdef";
    assert((2 <= from && from <= 16) && (2 <= to && to <= 16));

    unsigned long sum = 0;
    for (char c : x)
    {
        sum = sum * from + table.find(c);
    }

    std::string res = "";
    do
    {
        int mod = sum % to;
        res = table[mod] + res;
        sum /= to;
    } while (sum);

    return res;
}

例

#include <iostream>
#include <string>
#include <cassert>

int main() {
    cout << radix_conversion("777", 2, 10) << endl; // 1100001001
    cout << radix_conversion("110001111001", 2, 10) << endl; // 3193
    cout << radix_conversion("255", 10, 16) << endl; // ff
    cout << radix_conversion("ff00ff", 16, 10) << endl; // 16711935
    cout << radix_conversion("ff00ff", 16, 2) << endl; // 111111110000000011111111
    cout << radix_conversion("810", 9, 7) << endl; // 1626
}