キャリーを伝播させずに2つの数値を加算する方法

本記事では、キャリー（繰り上がり）を伝播させずに、n桁の2つの数値を加算するという興味深い問題を取り上げます。通常の足し算では、ある桁での和が10以上になると繰り上がりが発生し、次の桁へ伝播します。しかし今回は、各桁ごとに単純に数字を加算し、その結果をそのまま並べるだけの計算を行います。

具体例を見てみましょう。

例えば、7583 + 9642 をキャリーなしで計算すると、次のようになります。

• 最上位桁：7 + 9 = 16
• 次の桁：5 + 6 = 11
• 次の桁：8 + 4 = 12
• 最下位桁：3 + 2 = 5

これらを左から順に並べると、答えは 1611125 となります。

解法のポイント

この問題には一つのコツがあります。それは数値を右から左へ走査するということです。まず最下位桁の 3+2=5 が計算されますが、この結果は答えの末尾に配置されるべきものです。そこで、中間結果を一時的に保存するためにスタックを使用します。スタックはLIFO（後入れ先出し）構造なので、最下位桁から順にプッシュしていけば、ポップする際には自然と正しい順序（最上位桁から）で結果を取り出せます。

アルゴリズム

noPropagateCarry(a, b)

begin
    size := a と b の桁数のうち大きい方
    for i in range i to size, do
        al := a の最下位桁
        bl := b の最下位桁
        (al + bl) をスタックにプッシュ
        a := a / 10
        b := b / 10
    done
    スタックから要素をポップして表示
end

C++による実装例

#include<iostream>
#include<stack>
#include<cmath>
using namespace std;
int length(int n){
    return log10(n) + 1;
}
void noPropagateCarry(int a, int b){
    int size = max(length(a), length(b));
    stack<int> stk;
    for(int i = 0; i <size; i++){
        int al = a % 10; // a の最下位桁
        int bl = b % 10; // b の最下位桁
        stk.push(al + bl);
        a = a / 10; b = b/10;
    }
    while(!stk.empty()){
        cout << stk.top();
        stk.pop();
    }
}
main() {
    int a = 7583, b = 9642;
    cout << "Result: ";
    noPropagateCarry(a, b);
}

実行結果

Result: 1611125

処理の流れの解説

このコードの動作を順を追って説明します。

1. length() 関数は log10(n) + 1 を用いて数値の桁数を求めます。
2. noPropagateCarry() 関数内では、まず2つの数値のうち長い方の桁数を取得し、ループ回数とします。
3. 各ループでは、剰余演算子 % によって両数値の最下位桁を取り出し、その和をスタックにプッシュします。
4. その後、整数除算 / 10 によって数値を1桁右にシフトします。
5. すべての桁を処理したら、スタックが空になるまでポップしながら出力します。これにより、最上位桁から順に結果が表示されます。

この手法の計算量は O(max(桁数)) であり、非常に効率的です。キャリー伝播を扱わないため、多倍長演算の基礎的な練習問題としても適しています。