不带进位标志的大整数加法

Question

不带进位标志的大整数加法

c++cadditionarbitrary-precisioncarryflag

3

在汇编语言中，通常有一条指令可以将两个操作数和一个进位相加。如果你想要实现大整数加法，你只需要将最低位的整数不带进位相加，下一个整数带上进位即可。那么，在C或C++中，如何高效地实现这个功能呢？由于没有进位标志，因此不能简单地使用内联汇编等方法。该方法应该能够在多种编译器和架构上工作。

- fredoverflow

什么是大整数？它们是否像整数一样，无法适应任何标准 int 类型？ - Tony The Lion

@TonyTheLion，对于一个256位整数，请考虑使用unsigned x[8];。 - fredoverflow

@FredOverflow：当您有特定的位大小时，应使用uintN_t类型（例如uint32_t）。 - user1084944

2

@Hurkyl：没有编译器提供uint256_t。 - Puppy

@DeadMG：但是不同的编译器确实为“unsigned int”提供了不同的大小。 - user1084944

可能是以下讨论串的重复：在C/C++中检测整数溢出的最佳方法 - Oliver Charlesworth

4个回答

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，依此类推）。

这在空间上有点浪费，但使得转换为和从文本（如打印数字）中变得非常容易。

- paxdiablo

说实话，那是伪代码。我认为for语句无效。但是Python（或者至少接近它）对于伪代码来说是 _太棒了_，只要你远离那些lambda和map等奇怪的东西 :-) 我实际上使用Python的一个子集来教授基本的编程技能。 - paxdiablo

1

你的代码有一个错误：如果 b[i] 具有最大值且 carry 为1，则 c[i] == a[i]。 - user1084944

哦。另外，你没有明确地写出模运算，所以除非这些类型溢出并环绕，否则“c[i] < a[i]”是不可能的。 - Potatoswatter

1

@Potatoswatter，这正是问题所询问的（类似于C中的“unsigned”整数）。 - huon

Hurkyl，发现得好，已经修复了这个bug。至于另一个问题，dbaupp是正确的。换行符已经内置在数据类型中，不需要显式地进行操作。 - paxdiablo

2

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

只需从进位0开始即可。

- Cheers and hth. - Alf

2

任何操作数都可以 - 在某种程度上，它仅适用于二进制（2操作数）加法。因此，任何一个操作数都可以。 - Potatoswatter

对于第一次加法，最大结果为2 *（2 ^ n-1）= 2 ^（n + 1）-2，这意味着可以设置的最高位是位n，这意味着最大进位为1。对于下一次加法，2 *（2 ^ n-1）+1 = 2 ^（n + 1）-1，同样的道理。依此类推。 - Cheers and hth. - Alf

嗯，所有的加法（除了第一个）都将有三个操作数（a + b + 进位）。我的直觉告诉我，有几个边角案例潜伏着。 - fredoverflow

@Fred：这就是分析中的“+1”的含义。 - Cheers and hth. - Alf

0

如果我理解得正确的话，您想为自己的大整数类型编写自己的附加程序。

您可以使用一个简单的函数来完成此操作。在第一次运行中不需要担心进位标志。只需从右到左依次相加数字和进位标志（在该函数内部），从进位0开始，并将结果设置为(a+b+carry)%10和进位设置为(a+b+carry)/10。

这个SO可能是相关的：如何在C语言中实现大整数

- Mare Infinitus

好的，抱歉没有在问题中阅读到这一点。但链接显示了一个基于x的实现。 - Mare Infinitus

@MareInfinitus 那个问答是“作为一个编程练习”。这是汇编语言的替代品。 - Potatoswatter

什么意思？OP想完成他的作业？我们为什么不帮助他呢？ - Mare Infinitus

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1084944 · Accepted Answer

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

或者，您可以使用半字算术。如果您可以进行64位算术运算，请将数字表示为uint32_t数组（或等效地将64位字拆分为上下32位块）。然后，在对这些32位整数进行算术运算时，您可以首先提升到64位，然后在那里执行算术运算，然后转换回来。这使您可以检测进位，并且如果您没有“乘法hi”指令，则对于乘法也很好。

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

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

顺便提一下，虽然在实践中这也适用于有符号算术，但你会遇到两个问题：

它更加复杂
从技术上讲，有符号整数的溢出是未定义行为

因此，通常最好使用无符号数字。