コンパイラが 128 ビット整数をサポートしていない場合、C または C++ で 128 ビット整数を加算および減算するにはどうすればよいですか?

StackOverflow https://stackoverflow.com/questions/741301

  •  09-09-2019
  •  | 
  •  

質問

私は 128 ビット数値の長いストリーム用のコンプレッサーを作成しています。数値を差分として保存したいと思います。数値自体ではなく数値間の差分のみを保存します。差分が小さいため、より少ないバイト数に詰めることができるからです。

ただし、圧縮の場合はこれらの 128 ビット値を減算する必要があり、解凍の場合はこれらの値を加算する必要があります。私のコンパイラの最大整数サイズは 64 ビット幅です。

これを効率的に行うためのアイデアを持っている人はいますか?

役に立ちましたか？

解決

あなたが必要とするすべては、足し算と引き算で、あなたはすでにバイナリ形式であなたの128ビットの値を持つ、ライブラリが便利かもしれませんが、厳密には必要ではない場合。この数学を自分で行うには簡単です。

私はあなたのコンパイラが64ビットのタイプに使用するかわからないので、私は符号付きと符号なしの64ビット整数量のためにINT64とUINT64を使用します。

class Int128
{
public:
    ...
    Int128 operator+(const Int128 & rhs)
    {
        Int128 sum;
        sum.high = high + rhs.high;
        sum.low = low + rhs.low;
        // check for overflow of low 64 bits, add carry to high
        if (sum.low < low)
            ++sum.high;
        return sum;
    }
    Int128 operator-(const Int128 & rhs)
    {
        Int128 difference;
        difference.high = high - rhs.high;
        difference.low = low - rhs.low;
        // check for underflow of low 64 bits, subtract carry to high
        if (difference.low > low)
            --difference.high;
        return difference;
    }

private:
    INT64  high;
    UINT64 low;
};

他のヒント

GMP のを見てみましょう。

#include <stdio.h>
#include <gmp.h>

int main (int argc, char** argv) {
    mpz_t x, y, z;
    char *xs, *ys, *zs;
    int i;
    int base[4] = {2, 8, 10, 16};

    /* setting the value of x in base 10 */
    mpz_init_set_str(x, "100000000000000000000000000000000", 10);

    /* setting the value of y in base 16 */
    mpz_init_set_str(y, "FF", 16);

    /* just initalizing the result variable */
    mpz_init(z);

    mpz_sub(z, x, y);

    for (i = 0; i < 4; i++) {
        xs = mpz_get_str(NULL, base[i], x);
        ys = mpz_get_str(NULL, base[i], y);
        zs = mpz_get_str(NULL, base[i], z);

        /* print all three in base 10 */
        printf("x = %s\ny = %s\nz = %s\n\n", xs, ys, zs);

        free(xs);
        free(ys);
        free(zs);
    }

    return 0;
}

が出力される

x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000
y = 11111111
z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001

x = 235613266501267026547370040000000000
y = 377
z = 235613266501267026547370037777777401

x = 100000000000000000000000000000000
y = 255
z = 99999999999999999999999999999745

x = 4ee2d6d415b85acef8100000000
y = ff
z = 4ee2d6d415b85acef80ffffff01

完全に偶然この比較的古い記事に出くわした、私は経験の浅い読者の利益のためにVoLTEのの前の推測について詳しく説明することが適切と思っています。

まず、128ビット数の符号付き範囲-2 127 2 127 -1としない-2 127 であります2 127 元々定める。

第2に、有限の演算の周期性を2つの128ビットの数との間の最大の必要な差は-2 127 2 127 -1、有するされ128ビット（2 127 -1）ではないが129の記憶前提 - （-2 127 ）= 2 128 -1れます我々の最大値よりも明らかに大きい2 127 -1正の整数、算術オーバーフローが常に確実との間の最も近い距離の任意の2つの N はビット番号は、常に範囲内に0~2 N -1、したがって暗黙-2 N -1 2 N -1 -1ます。

を明確にするために、私たちは最初の仮定の3ビットのプロセッサは、2進加算を実装する方法を調べてみましょう。一例として、3ビット整数の絶対符号なし範囲を示す次の表を考慮します。

0 = 000B
1 = 001B
2 = 010B
3 = 011B
4 = 100B
5 = 101B
6 = 110B
7 = 111B ---> [オーバーフローにバック000Bサイクル

上記の表から、ということは容易に明らかです

001B（1）+ 010B（2）= 011B（3）

その数値の補数でこれらの番号のいずれかを追加することが常に得られることも明らかである2 名詞 -1ます：

010B（2）+ 101B（[2の補数] = 5）= 111B（7）=（2 3 -1）

2の添加は、 N は（ N +1）ビットの結果の数値結果を - ビット、それ故に追加することになる場合に発生する環状のオーバーフローに起因その数値の補数+ 1を持つこれらの数値のいずれかが常に0が得られます。

010B（2）+ 110B（[2の補数] + 1）= 000B（0）

の N + [補体ように、 N -

このように、我々は[補体の N ] + 1 =と言うことができN ] + 1 = N +（ - N ）=更に0、今わかっている場合に、 N は+ [補数 X ] + 1なければならない= - N の + [補数N は、次に、 N ] + = 0~1の N - （ N - X ）= X

。

私たちのオリジナルの3ビットのテーブル利回りにこれを適用します：

0 = 000B = [0の補数] + 1 = 0
1 = 001B = [7の補数] + 1 = -7
2 = 010B = [6の補数] + 1 = -6
3 = 011B = 5の補数] + 1 = -5
4 = 100B = [4の補数] + 1 = -4
5 = 101B = 3の補数] + 1 = -3
6 = 110B = 2の補数] + 1 = -2
7 = 111B = [1の補数] + 1 = -1 ---> [オーバーフローにバック000Bサイクル

の符号付き2の補数演算で暗黙として表現抽象化は、正、負、または両方の組み合わせであるかどうか、我々は今持っている2 N N ビットパターン N -1と負0 - （2 N ） - 必要に応じて、いつ1個の範囲です。実際の点では、すべての現代のプロセッサは、加算と減算演算の両方に共通ALU回路を実現するために、まさにそのようなシステムを採用しています。 CPUはi1 - i2減算命令に遭遇すると、それは内部i2の[1 +補完]動作を行い、その後、追加を除いてi1 + [i2の補数] + 1を計算するために加算回路を介してオペランドを処理しますキャリー/ XORゲート型オーバーフローフラグを署名、両方の符号付きおよび符号なしの加算、及び含意減算することにより、各暗黙的である。

我々は入力シーケンスに上記テーブルを適用した場合[-2 N -1 2 N -1 -1、-2 N -1 VoLTEの独自の応答で提示される]、我々は今、共同することができ次のnビット差をmpute

のdiff＃1：
（2 N -1 -1） - （-2 N -1 ）=
3 - （-4）= 3 + 4 =
（-1）= 7 = 111B

のdiff＃2：
（-2 N -1 ） - （2 N -1 -1）=
（-4） - 3 =（-4）+（5）=
（-7）= 1 = 001B

私達の種子から開始-2 N -1 、我々は今、順次上記差分の各々を適用することによって、元の入力シーケンスを再生することができます：

（-2 N -1 ）+（差分＃1）=
（-4）+ 7 = 3 =
2 N -1 -1

（2 N -1 -1）+（差分＃2）=
3 +（-7）=（-4）=
-2 N -1

あなたはもちろん2 はN が周期的に順次番号が必要になる理由として、この問題と推測するより多くの哲学的アプローチを採用することを望むかもしれない以上2 名詞 周期的に順次差？

Taliadonます。

1.53を後押し今多倍精度が含まれます：

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>

// Requires Boost 1.53 or higher
// build: g++ text.cpp

int main()
{
    namespace mp = boost::multiprecision;

    mp::uint128_t a = 4294967296;
    mp::uint256_t b(0);
    mp::uint512_t c(0);

    b = a * a;
    c = b * b;

    std::cout << "c: " << c << "\n";
    return 0;
}

出力：

./a.out
c: 340282366920938463463374607431768211456

大整数の数学に関する文献は数多くあります。無料で利用できるライブラリ (リンクを参照) の 1 つを使用することも、独自のライブラリを作成することもできます。警告しておきますが、加算と減算 (およびシフト) よりも複雑な場合は、単純ではないアルゴリズムを使用する必要があります。

加算と減算を行うには、2 つの 64 ビット整数を保持するクラス/構造体を作成できます。簡単な学校の数学を使って足し算と引き算を行うことができます。基本的には、紙と鉛筆を使って足したり引いたりすることを、キャリー/ボローを注意深く考慮しながら行います。

大きな整数を検索します。ところで、最近のバージョンの VC++、IntelC++、および GCC コンパイラーには 128 ビット整数型がありますが、皆さんが望むほど簡単にアクセスできるかどうかはわかりません (これらは sse2/xmms レジスターで使用することを目的としています)。

TomsFastMath のビットGMP（上記）と同様であるが、パブリックドメインであり、そしてました非常に高速であるためにゼロから設計された（それもためのアセンブリコードの最適化が含まれたx86、x86-64で、ARM、SSE2、PPC32、およびAVR32）。

また、注目に値する：目標は、単にそれを前処理することによって数字のストリームの圧縮を向上させることにある場合は、前処理の流れを正確に計算違いで作られている必要はありません。あなたは^と+の代わりにXOR（-）を使用することができます。利点は、128ビットのXORは、64ビット部品上の2つの独立したXORと全く同じであるので、それはシンプルかつ効率的であることである。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top