n進数同士の加算アルゴリズムをC++で実装する方法

問題の概要

この問題では、基数（底）が n である2つの数が与えられます。これらの数を加算し、その結果も同じく n進法で求めることが目的です。

基本的な解き方の流れは以下のとおりです。まず与えられた2つの数をそれぞれ10進数に変換します。10進数に変換できれば、あとは通常の整数演算で簡単に加算できます。最後に、加算結果を再び n進数へ変換して出力します。

ここで注意すべき点は、n進数を文字列として扱うことです。基数が9を超える場合、10以上の値を1桁で表すためにアルファベットを使う必要があるからです。たとえば16進数では、10〜15を表すのに A〜F の6文字が使用されます。

入力と出力の例

入力：
基数：16
1つ目の数：2C
2つ目の数：5F

出力：
加算結果：8B

アルゴリズム

baseNtoDec(number, base) ― n進数を10進数へ変換

入力：n進数の数値文字列と基数 n の値
出力：10進数に変換した値

Begin
    len := number の桁数
    power := 1
    num := 0

    for i := len-1 down to 0, do
        if number[i] >= base, then
            return 不正な数値
        num := num + number[i] * power
        power := power * base
    done

    return num
End

最下位桁から順に、各桁の値に基数のべき乗を掛けながら累積することで、n進数を10進数へ変換します。ある桁の値が基数以上であれば、それは有効な数ではないためエラーを返します。

decToBaseN(dec, base) ― 10進数をn進数へ変換

入力：10進数と、変換先の基数 n
出力：n進数の数値文字列

Begin
    while dec > 0, do
        res := (dec mod base) を res に連結
        dec := dec / base
    done

    res を反転する
    return res
End

10進数を基数で割った余りを順に取り出していくことで n進数を得られます。余りは下位桁から求まるため、最後に文字列を反転させて正しい桁順に整えます。

addBaseN(num1, num2, base) ― n進数の加算

入力：n進数で表された2つの数と基数 n
出力：n進法で加算した結果

Begin
    dec1 := baseNtoDec(num1, base)
    dec2 := baseNtoDec(num2, base)
    sum := decToBaseN(dec1 + dec2, base)
    return sum
End

C++による実装例

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

int getVal(char c) {
    if(c >= '0' && c<='9')
        return int(c-'0');      // 数字の10進数としての値を返す
    else
        return int(c-'A'+10);   // 英字（A〜F）は10以上の値に対応させる
}

char revVal(int n) {
    if(n >= 0 && n <=9)
        return char(n+'0');     // 数値に対応する文字を返す
    else
        return char(n+'A'-10);  // 10以上の数値に対応する英字を返す
}

int baseNtoDec(string number, int base) {
    int len = number.size();
    int power = 1;
    int num = 0;

    for(int i = len-1; i>= 0; i--) {   // 最下位桁から最上位桁へ処理
        if(getVal(number[i]) >= base)
            return INT_MIN;            // 桁の値が基数以上ならエラーとして負の極小値を返す
        num += getVal(number[i])*power;
        power = power*base;
    }
    return num;
}

string decToBaseN(int dec, int base) {
    string res = "";            // 空文字列で初期化
    while(dec > 0) {
        res += revVal(dec%base);
        dec /= base;
    }

    reverse(res.begin(), res.end());   // 反転して正しい桁順にする
    return res;
}

int main() {
    int base;
    string num1, num2, sum;
    cout << "Enter Base: "; cin >> base;
    cout << "Enter first number in base "<<base<<": ";cin >> num1;
    cout << "Enter second number in base "<<base<<": ";cin >> num2;
    sum = decToBaseN((baseNtoDec(num1, base) + baseNtoDec(num2, base)), base);
    cout << "The result of addition is: " << sum;
}

実行結果

Enter Base: 16
Enter first number in base 16: 2C
Enter second number in base 16: 5F
The result of addition is: 8B

処理のポイント

このプログラムでは、getVal 関数が文字を対応する数値へ変換し、revVal 関数がその逆（数値から文字への変換）を担っています。これにより、16進数のように英字を含む基数にも柔軟に対応できます。

また、baseNtoDec では各桁の値が基数未満であるかどうかをチェックし、不正な入力に対しては INT_MIN を返してエラーを通知します。decToBaseN は「割り算の余り」を繰り返し取り出すことで10進数を任意の基数へ変換しており、この一連の変換処理こそが本プログラムの中核となる仕組みです。