如果我的编译器不支持它们，我如何在 C 或 C++ 中添加和减去 128 位整数？

How can I add and subtract 128 bit integers in C or C++ if my compiler does not support them?

提问by Billy ONeal

I'm writing a compressor for a long stream of 128 bit numbers. I would like to store the numbers as differences -- storing only the difference between the numbers rather than the numbers themselves because I can pack the differences in fewer bytes because they are smaller.

我正在为一长串 128 位数字编写压缩器。我想将数字存储为差异——只存储数字之间的差异而不是数字本身，因为我可以用更少的字节来打包差异，因为它们更小。

However, for compression then I need to subtract these 128 bit values, and for decompression I need to add these values. Maximum integer size for my compiler is 64 bits wide.

但是，对于压缩，我需要减去这些 128 位值，而对于解压缩，我需要添加这些值。我的编译器的最大整数大小为 64 位宽。

Anyone have any ideas for doing this efficiently?

有没有人有任何想法可以有效地做到这一点？

回答by Mark Ransom

If all you need is addition and subtraction, and you already have your 128-bit values in binary form, a library might be handy but isn't strictly necessary. This math is trivial to do yourself.

如果您所需要的只是加法和减法，并且您已经拥有二进制形式的 128 位值，那么库可能会很方便，但并不是绝对必要的。这个数学是你自己做的微不足道的。

I don't know what your compiler uses for 64-bit types, so I'll use INT64 and UINT64 for signed and unsigned 64-bit integer quantities.

我不知道你的编译器对 64 位类型使用什么，所以我将 INT64 和 UINT64 用于有符号和无符号 64 位整数量。

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;
};

回答by Chas. Owens

Take a look at GMP.

看看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;
}

The output is

输出是

x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000
y = 11111111
z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001

x = 235613266501267026547370040000000000
y = 377
z = 235613266501267026547370037777777401

x = 100000000000000000000000000000000
y = 255
z = 99999999999999999999999999999745

x = 4ee2d6d415b85acef8100000000
y = ff
z = 4ee2d6d415b85acef80ffffff01

回答by Taliadon

Having stumbled across this relatively old post entirely by accident, I thought it pertinent to elaborate on Volte's previous conjecture for the benefit of inexperienced readers.

完全偶然地偶然发现了这篇相对较旧的帖子，我认为为了没有经验的读者的利益，详细阐述 Volte 之前的猜想是恰当的。

Firstly, the signed range of a 128-bit number is -2¹²⁷to 2¹²⁷-1 and not -2¹²⁷to 2¹²⁷as originally stipulated.

首先，128 位数字的有符号范围是 -2 ¹²⁷到 2 ¹²⁷-1 而不是最初规定的-2 ¹²⁷到 2 ¹²⁷。

Secondly, due to the cyclic nature of finite arithmetic the largest required differential between two 128-bit numbers is -2¹²⁷to 2¹²⁷-1, which has a storage prerequisite of 128-bits, not 129. Although (2¹²⁷-1) - (-2¹²⁷) = 2¹²⁸-1 which is clearly greater than our maximum 2¹²⁷-1 positive integer, arithmetic overflow always ensures that the nearest distance between any two n-bit numbers always falls within the range 0 to 2ⁿ-1 and thus implicitly -2^n-1to 2^n-1-1.

其次，由于有限算术的循环性质，两个 128 位数字之间所需的最大差为 -2 ¹²⁷到 2 ¹²⁷-1，其存储先决条件是 128 位，而不是 129。虽然 (2 ¹²⁷-1) - (-2 ¹²⁷) = 2 ¹²⁸-1 显然大于我们最大的 2 ¹²⁷-1 正整数，算术溢出总是确保任意两个n位数字之间的最近距离总是落在 0 到 2 ⁿ的范围内- 1，因此隐含 -2 ^n-1到 2 ^n-1-1。

In order to clarify, let us first examine how a hypothetical 3-bit processor would implement binary addition. As an example, consider the following table which depicts the absolute unsigned range of a 3-bit integer.

为了澄清起见，让我们首先研究一下假设的 3 位处理器如何实现二进制加法。例如，请考虑下表，该表描述了 3 位整数的绝对无符号范围。

   0 = 000b
   1 = 001b
   2 = 010b
   3 = 011b
   4 = 100b
   5 = 101b
   6 = 110b
   7 = 111b ---> [Cycles back to 000b on overflow]

   0 = 000b
   1 = 001b
   2 = 010b
   3 = 011b
   4 = 100b
   5 = 101b
   6 = 110b
   7 = 111b ---> [溢出时循环回到 000b]

From the above table it is readily apparent that:

从上表不难看出：

   001b(1) + 010b(2) = 011b(3)

   001b(1) + 010b(2) = 011b(3)

It is also apparent that adding any of these numbers with its numeric complement always yields 2ⁿ-1:

很明显，将这些数字中的任何一个与其数字补码相加总是产生 2 ⁿ-1：

   010b(2) + 101b([complement of 2] = 5) = 111b(7) = (2³-1)

   010b(2) + 101b([2 的补数] = 5) = 111b(7) = (2 ³-1)

Due to the cyclic overflow which occurs when the addition of two n-bit numbers results in an (n+1)-bit result, it therefore follows that adding any of these numbers with its numeric complement + 1 will always yield 0:

由于当两个n位数字相加产生 ( n+1) 位结果时会发生循环溢出，因此将这些数字中的任何一个与其数字补码相加 + 1 将始终产生 0：

   010b(2) + 110b([complement of 2] + 1) = 000b(0)

   010b(2) + 110b([2 的补数] + 1) = 000b(0)

Thus we can say that [complement of n] + 1 = -n, so that n+ [complement of n] + 1 = n+ (-n) = 0. Furthermore, if we now know that n+ [complement of n] + 1 = 0, then n+ [complement of n- x] + 1 must = n- (n-x) = x.

因此，我们可以说，[补Ñ] + 1 = - Ñ，使得Ñ+ [补Ñ+ 1 =] Ñ+（ - ñ）= 0。此外，如果我们现在知道，Ñ的+ [补Ñ] + 1 = 0，然后n+ [ n- x 的补码 ] + 1 必须 = n- ( n- x) = x。

Applying this to our original 3-bit table yields:

将此应用于我们原始的 3 位表产生：

   0 = 000b = [complement of 0] + 1 = 0
   1 = 001b = [complement of 7] + 1 = -7
   2 = 010b = [complement of 6] + 1 = -6
   3 = 011b = [complement of 5] + 1 = -5
   4 = 100b = [complement of 4] + 1 = -4
   5 = 101b = [complement of 3] + 1 = -3
   6 = 110b = [complement of 2] + 1 = -2
   7 = 111b = [complement of 1] + 1 = -1 ---> [Cycles back to 000b on overflow]

   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]

Whether the representational abstraction is positive, negative or a combination of both as implied with signed twos-complement arithmetic, we now have 2ⁿn-bit patterns which can seamlessly serve both positive 0 to 2ⁿ-1 and negative 0 to -(2ⁿ)-1 ranges as and when required. In point of fact, all modern processors employ just such a system in order to implement common ALU circuitry for both addition and subtraction operations. When a CPU encounters an i1 - i2subtraction instruction, it internally performs a [complement + 1] operation on i2and subsequently processes the operands through the addition circuitry in order to compute i1+ [complement of i2] + 1. With the exception of an additional carry/sign XOR-gated overflow flag, both signed and unsigned addition, and by implication subtraction, are each implicit.

无论表示抽象是正数、负数还是两者的组合，如带符号二进制补码算法所暗示的，我们现在有 2 ⁿn位模式，它们可以无缝地服务于正 0 到 2 ⁿ-1 和负 0 到 -(2 ⁿ)-1 范围根据需要。事实上，所有现代处理器都采用这样的系统，以便为加法和减法运算实现通用的 ALU 电路。当 CPU 遇到i1 - i2减法指令时，它会在内部执行 [complement + 1] 运算i2，然后通过加法电路处理操作数，以便计算i1+ [complement ofi2] + 1. 除了额外的进位/符号异或门控溢出标志外，有符号和无符号加法以及隐含减法都是隐式的。

If we apply the above table to the input sequence [-2^n-1, 2^n-1-1, -2^n-1] as presented in Volte's original reply, we are now able to compute the following n-bit differentials:

如果我们将上表应用到Volte 原始回复中提出的输入序列 [-2 ^n-1, 2 ^n-1-1, -2 ^n-1]，我们现在可以计算以下 n 位差分：

diff #1:
   (2^n-1-1) - (-2^n-1) =
   3 - (-4) = 3 + 4 =
   (-1) = 7 = 111b

差异 #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:
   (-2 ^n-1) - (2 ^n-1-1) =
   (-4) - 3 = (-4) + (5) =
   (-7) = 1 = 001b

Starting with our seed -2^n-1, we are now able to reproduce the original input sequence by applying each of the above differentials sequentially:

从我们的种子 -2 ^{n-1 开始}，我们现在可以通过依次应用上述每个差异来重现原始输入序列：

   (-2^n-1) + (diff #1) =
   (-4) + 7 = 3 =
   2^n-1-1

   (-2 ^n-1) + (diff #1) =
   (-4) + 7 = 3 =
   2 ^n-1-1

   (2^n-1-1) + (diff #2) =
   3 + (-7) = (-4) =
   -2^n-1

   (2 ^n-1-1) + (diff #2) =
   3 + (-7) = (-4) =
   -2 ^n-1

You may of course wish to adopt a more philosophical approach to this problem and conjecture as to why 2ⁿcyclically-sequential numbers would require more than 2ⁿcyclically-sequential differentials?

您当然可能希望对这个问题采用更哲学的方法，并推测为什么 2 ^{n 个}循环序列数需要超过 2 ^{n 个}循环序列微分？

Taliadon.

塔利亚顿。

回答by Taliadon

Boost 1.53 now includes multiprecision:

Boost 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;
}

Output:

输出：

./a.out
c: 340282366920938463463374607431768211456

回答by Ash

There is a lot of literature regarding large integer math. You can use one of the libraries freely available (see links) or you can roll your own. Although I should warn you, for anything more complicated than addition and subtraction (and shifts), you'll need to use non-trivial algorithms.

有很多关于大整数数学的文献。您可以使用免费提供的库之一（请参阅链接），也可以推出自己的库。尽管我应该警告您，对于比加法和减法（和移位）更复杂的任何事情，您都需要使用非平凡的算法。

To add and subtract, you can create a class/structure that holds two 64-bit integers. You can use simple school math to do the addition and subtraction. Basically, do what you do with a pencil and paper to add or subtract, with careful consideration to carries/borrows.

要进行加减运算，您可以创建一个包含两个 64 位整数的类/结构。您可以使用简单的学校数学进行加法和减法。基本上，做你用铅笔和纸做的加减法，仔细考虑携带/借用。

Search for large integer. Btw recent versions of VC++, IntelC++ and GCC compilers have 128-bit integer types, although I'm not sure they are as easily accessible as you might like (they are intended to be used with sse2/xmms registers).

搜索大整数。顺便说一句，最新版本的 VC++、IntelC++ 和 GCC 编译器具有 128 位整数类型，尽管我不确定它们是否像您喜欢的那样容易访问（它们旨在与 sse2/xmms 寄存器一起使用）。

• http://en.wikipedia.org/wiki/Arbitrary_precision_arithmetic
• http://orion.math.iastate.edu/cbergman/crypto/bignums.html
• http://www.mathgoodies.com/tutorial/

• http://en.wikipedia.org/wiki/Arbitrary_precision_arithmetic
• http://orion.math.iastate.edu/cbergman/crypto/bignums.html
• http://www.mathgoodies.com/tutorial/

回答by Sophie Alpert

TomsFastMathis a bit like GMP (mentioned above), but is public domain, and was designed from the ground up to be extremely fast (it even contains assembly code optimizations for x86, x86-64, ARM, SSE2, PPC32, and AVR32).

TomsFastMath有点像 GMP（上面提到过），但属于公共领域，并且从头开始设计得非常快（它甚至包含针对 x86、x86-64、ARM、SSE2、PPC32 和 AVR32 的汇编代码优化） .

回答by Armin Rigo

Also worth noting: if the goal is merely to improve the compression of a stream of numbers by preprocessing it, then the preprocessed stream doesn't have to be made of exactly arithmetic differences. You can use XOR (^) instead of +and -. The advantage is that a 128-bit XOR is exactly the same as two independent XORs on the 64-bit parts, so it is both simple and efficient.

还值得注意的是：如果目标只是通过预处理来改进数字流的压缩，那么预处理过的流不必完全由算术差异组成。您可以使用 XOR( ^) 代替+and -。优点是一个128位的异或与64位部分上的两个独立的异或完全一样，所以既简单又高效。