c - 如何正确添加/减去 128 位数字（作为两个 uint64_t）？

Question

我在 C 中工作，需要加减一个 64 位数字和一个 128 位数字。结果将保存在 128 位数字中。我正在使用一个整数数组来存储 128 位数字的上半部分和下半部分（即uint64_t bigNum[2]，bigNum[0]最低有效位在哪里）。

任何人都可以帮助使用可以接受 bigNum 并对其进行加/减 a 的加法和减法功能uint64_t吗？

我在网上看到了很多不正确的例子，所以考虑一下：

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

此时bigNum[0]应设置所有位，而bigNum[1]不应设置任何位。

score 1 · Accepted Answer

这应该适用于减法：

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 }，减去 2 将使其等于{ ~0UL, ~0UL }，这是表示 -1 的正确位模式。在这里，假设 UL 将整数提升为 64 位，这当然取决于编译器。

score 1 · Accepted Answer

在许多架构中，添加/减去任意长度的整数非常容易，因为有一个进位标志和带有标志的加/减指令。例如在 x86rdx:rax += r8:r9上可以这样做

add rax, r9
adc rdx, r8

在 C 中，无法访问此进位标志，因此您必须自己计算该标志。最简单的方法是检查无符号和是否小于这样的任何一个操作数。例如，a += b我们会这样做

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

score 0 · Accepted Answer

对于您减去的值小于或等于bignum[0]您不必触摸的情况bignum[1]。

如果不是 bignum[0]，无论如何，你从中减去它。此操作将环绕，但这是您在此处需要的行为。此外，您还必须从中减去 1 bignum[1]。

score 0 · Accepted Answer

0

大多数编译器本质上都支持__int128类型。

试试看，你可能会很幸运。

于 2011-01-21T10:00:16.230 回答

score 0 · Accepted Answer

在 1 年级或 2 年级，你应该已经学会了如何将 1 和 10 的加法分解为多个部分，将其拆分为多个单独的十和单位加法。在处理大数时，可以应用相同的原理来计算任意大数的算术运算，通过实现你的单位现在是 2^bits 单位，你的“十”是 2^bits 大等等。

5 回答 5