Bil*_*eal 23 c++ integer 128-bit
我正在为128位数字的长流写一个压缩器.我想将数字存储为差异 - 仅存储数字之间的差异而不是数字本身,因为我可以将差异打包在更少的字节中,因为它们更小.
但是,对于压缩,我需要减去这些128位值,对于解压缩,我需要添加这些值.我的编译器的最大整数大小是64位宽.
任何人有任何想法有效地做到这一点？
Mar*_*som 38
如果您只需要加法和减法,并且已经有二进制形式的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;
};
Cha*_*ens 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
我完全偶然地偶然发现了这个相对较老的帖子,我认为有必要详细说明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正整数,算术溢出总是确保任何两个n位数之间的最近距离总是在0到2 n的范围内-因此,隐含地为-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的负数(2)n)-1范围,当需要时.事实上,所有现代处理器都采用这样的系统,以便为加法和减法操作实现通用的ALU电路.当CPU遇到i1 - i2减法指令时,它在内部执行[patch + 1]操作i2,然后通过加法电路处理操作数,以便计算i1+ [补码i2] + 1.除了附加的进位/符号XOR门控溢出标志外,有符号和无符号加法以及暗示减法都是隐含的.
如果我们将上表中输入序列[-2 ñ -1,2 ñ -1 -1,-2 ñ -1 ]在VoLTE的最初的答复提出,我们现在能够计算如下n位的差别:
差异#1:
(2 n -1 -1) - (-2 n -1)=
3 - ( - 4)= 3 + 4 =
( - 1)= 7 = 111b
DIFF#2:
(-2 Ñ -1) - (2- Ñ -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个循环序列差分？
Taliadon.
小智 8
Boost 1.53现在包括multiprecision:
#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