符号なしlong longに収まらない大きな整数をどのように集計しますか？ C++

Question

私は、与えられたデータのすべての可能な個々のサブ文字列をまとめてプログラムを作成しました。たとえば：大（10^15）の数字がでてくるとき 1 1 2 2は、30までの30

1 
1 + 1 
1 + 1 + 2 
1 + 1 + 2 + 2 
1 
1 + 2 
1 + 2 + 2 
2 
2 + 2 
2 

、なぜなら和を返す必要があり、今の問題は、このようなプログラムを作成されていない、問題がありますそれが10^5にもなることがあります。今私の質問は：どのように私はそのような数字に対処するのですか？私は標準ライブラリしか使えないので、残念なことに私のためのGMPはなく、GCC 4.4.4でも動作させる必要があります。

Answer 1

は答えに興味がある人のために私はちょうど符号なしlong long int型を分離するためにオーバーフローの数を移動して、それを考え出しました。

for(int i = 1; i <= n; i++){       
     SUM += addends[i - 1] * (i * (n - i + 1)); 

    if(SUM > 10000000000000000000){  // If close to overflow of unsigned long long int 
     SUM -= 10000000000000000000; // Remove 10^17 
     counter ++;      // And boost counter, to make recreating true value possible 
    } 
} 

おそらく実際には効果がありませんが、私の目的には十分です。あなたの助けをありがとう！

Answer 2

私はUINT_128の裸の骨（必要なものだけ）の実装を行うことは非常に簡単だと思います。私はあなたがプログラムを実施しようとしている方法を知っていると仮定すると、

、あなたが必要とするすべてはuint64_tをを取るコンストラクタです（あなたの最高の答えは、実際にuint_96に収まるでしょう）。加算演算子;乗算演算子;可能であればディスプレイに表示されます。

私は4のuint32_t（ワード）として内部的に格納しますし、操作は言葉だけに加えたり、長い乗算を手で小数のために行われているのと同じ方法を動作させることによって実現することができます。私があなたの要因がuint64_tを決して超えないと信じているので、乗算を単純化することができます。

バイナリまたは16進数以外のものを表示する必要がある場合は、ディビジョンも実装する必要があります（実際に怠けている場合は、バイナリ検索スタイルの推測で数字を取得し、小数点の表現）。