如果我的编译器不支持 C 或 C++ 中的 128 位整数加法和减法？

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

  •  09-09-2019
  •  | 
  •  

题

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

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

有人有什么想法可以有效地做到这一点吗？

有帮助吗？

解决方案

如果你需要的是加减法，你已经有了以二进制形式的128位值，图书馆可能会很方便，但不是绝对必要的。这个数学琐细的做自己。

我不知道你的编译器使用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;
};

其他提示

看一看 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 如最初规定。

其次，由于有限算术的循环性质两个128位的数字之间的最大需要差速器-2 127 2 127 -1，其中有一个的128位，129不虽然（2 127 -1）存储先决条件 - （-2 127 ）= 2 128 -1其中是比我们的最大显然更大的2 127 -1的正整数，算术溢出总是确保之间的最近距离的任何两个名词的比特数总是的范围内0至2 名词的 -1并且因此隐含地-2 名词的-1 2 名词 -1 -1。

为了澄清，让我们首先检查一个假设的3位处理器将如何实现二进制加法。作为一个例子，考虑下面的表，它示出了一个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）

由于其中发生循环溢出时在增加了两个名词的比特数的结果（名词的1）位的结果，因此如下，添加任何这些数字与其数字补体+ 1将总是产生0：

010B（2）+ 110B（[补2] + 1）= 000B（0）

因此，我们可以说，[补名词的] + 1 = - 名词的，以便名词的+ [的补体的 ñ的] + 1 = 名词的+（ - 名词的）= 0。此外，如果我们现在知道，名词的+ [补的名词的] + 1 = 0，则名词的的+ [补名词的 - 的 X 的] + 1必须= 名词的 - （名词的 - 的 X 的）。= X 的

将此应用于我们原来的3位表收率：

0 = 000B = + 1 = 0，点击[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 名词的 名词比特模式，其可以无缝服务正0至2 名词的 -1和负0到 - （2 名词的） - 在有需要时1个范围。就事实而言，所有的现代处理器采用了这样的系统，以实现两个加法和减法操作的通用ALU电路。当CPU遇到i1 - i2减法指令时，它在内部执行上i2一个[补充+ 1]操作，并随后处理通过所述加法电路操作数，以便计算+ 1 i1 + [的i2补]以一个附加的例外携带/登录XOR门控溢出标志，符号和无符号此外，和通过暗示减法，各自是隐式的。

如果我们应用上表中的输入序列[-2 名词的-1 2 名词的-1 -1，-2 名词的-1 ]如VoLTE的的原始的应答给出，我们现在能够共同mpute下面n比特差：

DIFF＃1：结果 （2 名词的-1 -1） - （-2 名词的-1 ）=结果 3 - （-4）= 3 + 4 =，点击 （-1）= 7 = 111B

DIFF＃2：结果 （-2 名词的-1 ） - （2- 名词的-1 -1）=结果 （-4） - 3 =（-4）+（5）=，点击 （-7）= 1 = 001B

与我们的种子开始-2 名词的-1 ，我们现在能够通过应用上述各差分的顺序以再现原始输入序列：

（-2 名词的-1 ）+（差异＃1）=结果 （-4）+ 7 = 3 =，点击 2 名词的-1 -1

（2 名词的-1 -1）+（差异＃2）=结果 3 +（-7）=（-4）=结果 -2 名词的-1

您当然可以希望采取更哲学的方法解决这个问题和猜想，为什么2 名词 循环顺序号将需要超过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

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

要进行加法和减法，您可以创建一个包含两个 64 位整数的类/结构。您可以使用简单的学校数学来进行加法和减法。基本上，就像用铅笔和纸一样进行加法或减法，并仔细考虑进位/借位。

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

TomsFastMath 是有点像GMP（如上所述），但是公共领域，并且是从地面到极快设计（它甚至包含汇编代码优化用于x86，X86-64，ARM，SSE2，PPC32，和AVR32）。

另外值得注意的：如果目标是仅通过预处理它来改善数字流的压缩，然后经过预处理的数据流不必进行准确的算术差。您可以使用XOR（^），而不是+和-。的优点是，一个128位的XOR是完全一样的64位部分的两个独立异或，因此它的结构简单，效率更高。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top