27

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

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

有人对有效地做到这一点有任何想法吗？

4

7 回答 7

40

如果您只需要加法和减法，并且您已经拥有二进制形式的 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;
};
于 2009-04-12T06:43:13.530 回答
16

看看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
于 2009-04-12T05:42:58.060 回答
8

完全偶然地偶然发现了这篇相对较旧的帖子，我认为有必要详细说明沃尔特先前的猜想，以使没有经验的读者受益。

首先，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 正整数，算术溢出总是确保任何两个n位数字之间的最近距离总是在 0 到 2 n的范围内- 1，因此隐含 -2 n -1到 2 n -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 n -1：

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

由于当两个n位数字相加导致 ( n +1) 位结果时发生循环溢出，因此可以得出以下结论：将这些数字中的任何一个与其数字补码 + 1 相加总是会产生 0：

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

因此我们可以说 [ n的补码] + 1 = - n，因此n + [ n的补码] + 1 = n + (- n ) = 0。此外，如果我们现在知道n + [ n的补码] + 1 = 0，则n + [ n - x的补码 ] + 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 n n位模式，可以无缝地为正 0 到 2 n -1 和负 0 到 -(2 n )-1 范围在需要时。事实上，所有现代处理器都采用这样的系统来实现加法和减法运算的通用 ALU 电路。当 CPU 遇到i1 - i2减法指令时，它会在内部执行 [complement + 1] 运算，i2然后通过加法电路处理操作数，以便计算i1+ [complement ofi2] + 1。除了一个额外的进位/符号异或门控溢出标志外，有符号和无符号加法以及隐含减法都是隐式的。

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

差异 #1：
   (2 n -1 -1) - (-2 n -1 ) =
   3 - (-4) = 3 + 4 =
   (-1) = 7 = 111b

差异 #2：
   (-2 n -1 ) - (2 n -1 -1) =
   (-4) - 3 = (-4) + (5) =
   (-7) = 1 = 001b

从我们的种子 -2 n -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 个循环序列数需要超过 2 n 个循环序列微分？

塔利亚顿。

于 2010-05-29T15:44:15.397 回答
8

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

输出：

./a.out
c: 340282366920938463463374607431768211456
于 2013-04-25T15:28:48.270 回答
4

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

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

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

于 2009-04-12T06:06:35.100 回答
2

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

于 2009-04-12T06:04:35.887 回答
0

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

于 2013-11-08T09:45:31.390 回答