3

在汇编语言中，通常有一条指令添加两个操作数和一个进位。如果要实现大整数加法，只需添加不带进位的最低整数和带进位的下一个整数。在我无法访问进位标志的 C 或 C++ 中，我将如何有效地做到这一点？它应该适用于多个编译器和架构，所以我不能简单地使用内联汇编等。

4

4 回答 4

6

您可以使用“钉子”（GMP 中的一个术语）：uint64_t在表示数字时，不要使用 a 的所有 64 位，而是仅使用其中的 63 位，最高位为零。这样，您可以通过简单的位移检测溢出。你甚至可能想要少于 63 个。

或者，您可以进行半字运算。如果您可以进行 64 位算术运算，请将您的数字表示为 s 数组uint32_t（或等效地，将 64 位字拆分为高 32 位块和低 32 位块）。然后，在对这些 32 位整数进行算术运算时，可以先提升到 64 位，然后再转换回来。这可以让你检测进位，如果你没有“乘法”指令，它也有利于乘法。

正如另一个答案所示，您可以通过以下方式检测无符号加法中的溢出：

uint64_t sum = a + b;
uint64_t carry = sum < a;

As an aside, while in practice this will also work in signed arithmetic, you have two issues:

  • It's more complex
  • Technically, overflowing a signed integer is undefined behavior

so you're usually better off sticking to unsigned numbers.

于 2012-06-09T09:33:15.103 回答
3

您可以通过以下事实来计算进位：如果通过添加两个数字溢出，结果将始终小于其他两个值中的任何一个。

换句话说，如果a + b小于a，则溢出。这当然是为了积极的价值观，a但那b是你几乎肯定会在 bignum 库中使用的东西。

不幸的是，进位引入了一个额外的复杂性，因为将最大可能值加上一个进位将给您与开始时相同的值。因此，您必须将其作为特殊情况处理。

就像是：

carry = 0
for i = 7 to 0:
    if a[i] > b[i]:
        small = b[i], large = a[i]
    else:
        small = a[i], large = b[i]
    if carry is 1 and large is maxvalue:
        c[i] = small
        carry = 1
    else:
        c[i] = large + small + carry
        if c[i] < large:
            carry = 1
        else
            carry = 0

实际上，您可能还需要考虑不使用数组元素中的所有位。

我过去实现过库，其中最大“数字”小于或等于它可以容纳的最大值的平方根。因此，对于 8 位（八位字节）数字，您可以存储从 0 到 15 的值 - 这样，将两位数字相乘并添加最大进位将始终与八位字节匹配，从而使溢出检测没有意义，尽管以一些存储为代价。

同样，16 位数字的范围为 0 到 255，因此它不会在 65536 处溢出。

事实上，我有时将其限制为更多，确保人工换行值是 10 的幂（所以一个八位字节将包含 0 到 9，16 位数字将是 0 到 99，32 位数字从 0通过 9999，依此类推。

这在空间上有点浪费，但可以非常容易地与文本（例如打印您的数字）进行转换。

于 2012-06-09T09:16:33.767 回答
2

您可以通过检查来检查无符号类型的进位，结果是否小于操作数（任何操作数都可以）。

只需从进位 0 开始。

于 2012-06-09T09:13:11.273 回答
0

如果我理解正确，您想为自己的大整数类型编写自己的加法。

你可以用一个简单的函数来做到这一点。无需担心第一次运行时的进位标志。只需从右到左，逐位添加进位标志（在该函数内部），从进位 0 开始，并将结果设置为 (a+b+carry) %10 并将进位设置为 (a+ b+进位）/ 10。

这个 SO 可能是相关的： how to implement big int in c

于 2012-06-09T09:25:14.797 回答