如何正确添加/减去128位编号（作为两个UINT64_T）？

Question

我在C中工作，需要添加和减去64位编号和128位编号。结果将在128位的数字中举行。我正在使用整数数组来存储128位数字的上半部分（即 uint64_t bigNum[2], ， 在哪里 bigNum[0] 是最不重要的）。

任何人都可以帮助可以接受bignum并添加/减法的加法和减法功能 uint64_t 它？

我在网络上看到了许多不正确的示例，因此请考虑以下内容：

bigNum[0] = 0;  
bigNum[1] = 1;  
subtract(&bigNum, 1);

在此刻 bigNum[0] 应该设置所有位，而 bigNum[1] 应该没有钻头。

Answer 1

在1年级或2级中，您应该没有通过将其分成多个单独的数十个和单元的单独添加来将1和10分成部分的添加。当处理大数字时，可以将相同的原理应用于任意大数的算术操作，通过意识到您的单位现在是2^位的单位，您的“ TENS”较大2^位更大，依此类推。

Answer 2

这应该适用于减法：

typedef u_int64_t bigNum[2];

void subtract(bigNum *a, u_int64_t b)
{
  const u_int64_t borrow = b > a[1];

  a[1] -= b;
  a[0] -= borrow;
}

添加非常相似。当然，以上的测试也可以表达出来，但我发现始终进行借用更加干净。优化作为练习。

为一个 bigNum 等于 { 0, 1 }, ，减去两个会使它平等 { ~0UL, ~0UL }, ，这是代表-1的适当位模式。在这里，UL被认为可以将整数促进64位，这当然是依赖编译器的。

Answer 3

对于您的减法值较小或等于 bignum[0] 你不必触摸 bignum[1].

如果不是，您从中减去 bignum[0], ，无论如何。此操作将缠绕，但这是您在这里需要的行为。另外，您必须从 bignum[1].

Answer 4

大多数编译器支持 __int128 本质上键入。

尝试一下，您可能很幸运。

Answer 5

在许多体系结构中，添加/减去任何任意长的整数非常容易，因为有一个随身携带标志和带有标志指令的添加/sub。例如在x86上 rdx:rax += r8:r9 可以这样做

add rax, r9
adc rdx, r8

在C中，无法访问此携带标志，因此您必须自己计算标志。最简单的方法是检查未签名的总和是否小于操作数的任何一个 像这样. 。例如去做 a += b 我们会喜欢的

aL += bL;
aH += bH + (aL < bL);

这是一些 示例组件输出