没有进位标志的大整数加法 [英] big integer addition without carry flag

问题描述

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

解决方案

您可以使用 nails （来自GMP的术语）：表示数字时，不要使用 uint64_t 的全部64位，而应仅使用63位，且最高位为零。这样，您可以通过简单的移位检测溢出。您甚至可能希望少于63。

或者，您可以执行半字运算。如果可以执行64位算术运算，则将您的数字表示为 uint32_t s的数组（或等效地，将64位字分成上下32位块）。然后，当对这些32位整数进行算术运算时，您可以先将其上的算术提升为64位，然后再转换回去。这样可以检测进位，如果没有乘高指令，则对乘法也很有用。

如另一个答案所示，您可以检测到溢出

  uint64_t sum = a + b; 
 uint64_t进位=和<一个; 
  

顺便说一句，尽管在实践中这也适用于带符号算术，但您有两个问题： / p>

• 更复杂


• 从技术上讲，溢出有符号整数是未定义的行为

所以通常最好还是保留未签名的数字。

In assembly languages, there is usually an instruction that adds two operands and a carry. If you want to implement big integer additions, you simply add the lowest integers without a carry and the next integers with a carry. How would I do that efficiently in C or C++ where I don't have access to the carry flag? It should work on several compilers and architectures, so I cannot simply use inline assembly or such.

解决方案

You can use "nails" (a term from GMP): rather than using all 64 bits of a uint64_t when representing a number, use only 63 of them, with the top bit zero. That way you can detect overflow with a simple bit-shift. You may even want less than 63.

Or, you can do half-word arithmetic. If you can do 64-bit arithmetic, represent your number as an array of uint32_ts (or equivalently, split 64-bit words into upper and lower 32-bit chunks). Then, when doing arithmetic operations on these 32-bit integers, you can first promote to 64 bits do the arithmetic there, then convert back. This lets you detect carry, and it's also good for multiplication if you don't have a "multiply hi" instruction.

As the other answer indicates, you can detect overflow in an unsigned addition by:

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.

这篇关于没有进位标志的大整数加法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！