3

アセンブリ言語では、通常、2 つのオペランドとキャリーを追加する命令があります。大きな整数の加算を実装する場合は、最小の整数をキャリーなしで加算し、次の整数をキャリー付きで加算します。キャリー フラグにアクセスできない C または C++ で効率的に行うにはどうすればよいでしょうか。いくつかのコンパイラとアーキテクチャで動作するはずなので、単純にインライン アセンブリなどを使用することはできません。

4

4 に答える 4

6

「ネイル」(GMP の用語) を使用できます。uint64_t数値を表すときに a の 64 ビットすべてを使用するのではなく、63 ビットのみを使用し、最上位ビットをゼロにします。そうすれば、単純なビットシフトでオーバーフローを検出できます。63 未満が必要な場合もあります。

または、ハーフワード演算を実行できます。64 ビット演算ができる場合は、数値をuint32_ts の配列として表します (または、64 ビット ワードを上位と下位の 32 ビット チャンクに分割します)。次に、これらの 32 ビット整数で算術演算を行う場合、最初に 64 ビットに昇格してそこで算術を行い、次に元に戻すことができます。これにより、キャリーを検出できます。また、"multiply hi" 命令がない場合は、乗算にも適しています。

他の回答が示すように、次の方法で符号なし加算のオーバーフローを検出できます。

uint64_t sum = a + b;
uint64_t carry = sum < a;

余談ですが、実際にはこれは符号付き演算でも機能しますが、2 つの問題があります。

  • もっと複雑です
  • 技術的には、符号付き整数のオーバーフローは未定義の動作です

したがって、通常は符号なしの数値に固執する方がよいでしょう。

于 2012-06-09T09:33:15.103 に答える
3

2 つの数値を加算してオーバーフローした場合、結果は常に他の 2 つの値のいずれかよりも小さくなるため、キャリーを計算できます。

つまり、a + bが 未満の場合a、オーバーフローしました。aもちろん、それは正の値のためですbが、bignumライブラリに使用することはほぼ確実です。

残念ながら、キャリーを使用すると、可能な限り最大の値に 1 のキャリーを加算すると、元の値と同じ値が得られるという複雑な問題が発生します。したがって、それを特別なケースとして処理する必要があります。

何かのようなもの：

carry = 0
for i = 7 to 0:
    if a[i] > b[i]:
        small = b[i], large = a[i]
    else:
        small = a[i], large = b[i]
    if carry is 1 and large is maxvalue:
        c[i] = small
        carry = 1
    else:
        c[i] = large + small + carry
        if c[i] < large:
            carry = 1
        else
            carry = 0

実際には、配列要素のすべてのビットを使用しないことを検討することもできます。

過去にライブラリを実装したことがありますが、最大の「桁」は保持できる最大値の平方根以下です。したがって、8 ビット (オクテット) の数字の場合は、0 から 15 までの値を格納します。このようにすると、2 桁を乗算して最大桁上げを加算すると、常にオクテットに適合し、オーバーフロー検出が意味をなさなくなります。

同様に、16 ビットの数字の範囲は 0 ～ 255 であるため、65536 でオーバーフローしません。

実際、人工ラップ値が 10 の累乗になるように、それ以上に制限することもありました (したがって、オクテットは 0 ～ 9 を保持し、16 ビットの数字は 0 ～ 99、0 から 32 ビットの数字を保持します)。 9999 まで、など。

これはスペースを少し無駄にしますが、テキストとの間の変換 (数値の出力など) は非常に簡単になります。

于 2012-06-09T09:16:33.767 に答える
2

u は unsigned 型のキャリーをチェックすることでチェックできます。結果はオペランドよりも小さいです (どのオペランドでもかまいません)。

キャリー0で始めてください。

于 2012-06-09T09:13:11.273 に答える
0

私があなたを正しく理解しているなら、あなたはあなた自身の大きな整数型のためにあなた自身の足し算を書きたいと思うでしょう。

簡単な関数でこれを行うことができます。最初の実行でキャリーフラグについて心配する必要はありません。右から左に移動し、桁ごとにキャリーフラグ（その関数の内部）を追加し、キャリー0から始めて、結果を（a + b +キャリー）％10に設定し、キャリーを（a + b +キャリー）/10。

このSOは関連している可能性があります： cでbigintを実装する方法

于 2012-06-09T09:25:14.797 に答える