使用32位算术运算来加法计算64位数字

Question

如何使用32位算术加法计算两个64位数字的和？

- Light_handle

Answer 1

首先加上最不重要的字节，保留进位。接着加上最重要的字节时要考虑来自最不重要字节的进位：

; x86 assembly, Intel syntax
; adds ecx:ebx to edx:eax
add eax, ebx
adc edx, ecx

- Mehrdad Afshari

---

二进制补码算术的一个特点是，有符号数不需要特殊处理。例如，在Intel语法中，我可以使用add eax, 0xFFFFFFFF，其效果与sub eax, 1相同。请注意，这不会改变eax寄存器的值。 - BenW

Answer 2

考虑如何使用一位数的算法相加两个两位数。

 42
+39
---

首先，您需要添加正确的列（“ ones”或“ units”）。2+9等于11。 11“溢出”了您的1位算术，因此您必须“进位”到10。

 1
 42
+39
---
  1

现在您需要将左侧的“十位”列相加，包括进位。1+4+3=8。

 1
 42
+39
---
 81

8比10小，所以不需要进位。你完成了。

刚才发生了什么？当你说一个数字是“42”（在十进制中），你实际上指的是

4*10+2

或者，等价地说，

4*10^1+2*10^0

(当我说 "a^b"，比如 "10^1"，我的意思是 "a 的 b 次方"：a 乘以自己 b 次。10^0 等于 1。10^1 等于 10。10^2 等于 10*10=100...)

当你将 "42" 和 "39" 相加时，就是在说

4*10+2+3*10+9

哪一个等于

(4+3)*10+(2+9)*1
(4+3)*10+(11)*1
(4+3)*10+(1*10+1)*1

由于"11"不是有效的个位数，因此您需要从个位数中借位10，将其转换为十位上的数字1。

(4+3)*10+(1)*10+(1)*1
(4+3+1)*10+(1)*1
(8)*10+(1)*1

这是81。

那么，为什么我一直在讲这个而不是你关于64位数字和32位算术的问题呢？因为它们实际上完全相同！

一个数字的范围从0到9。一个“32位数”范围从0到2^32-1。（假设它是无符号的。）

因此，我们不需要使用十进制，而是使用基于2^32的计数系统。在基于2^32的计数系统中，我们将2^32表示为10。如果您用基于2^32的计数系统写一个64位数字，它应该是：

(x)*10+y

x和y是表示在0到2^32-1范围内的数字的符号。这些符号是比特串。

如果要将两个64位数字相加，请将它们分解为2 ^ 32进制:

 a_1*10+a_0
+b_1*10+b_0

现在你需要用32位算术相加，而不是使用数字算术，以基数2^32相加二进制数，与十进制相加的方式完全相同！

如何将64位数字a拆分为两个32位数字a_1和a_0？将a除以2 ^ 32。不是使用浮点数，而是整数方式--其中您得到被除数和余数。被除数是a_1，余数是a_0。

不幸的是，这需要64位算术运算。但是，通常a_1是a的“最高有效半部分”，因此，在C风格的语法中：

a_1=(a >> 32)
a_0=(a & 0xFFFFFFFF)

其中 >> 表示右移位运算符，& 表示按位与运算符。

通常情况下，如果无法进行 64 位加法，一个“64 位数字”实际上将由两个 32 位数字 a_1 和 a_0 组成。如果无法执行 uint64_t 算术，则不会有 uint64_t！

所有这些都假定您正在执行无符号算术，但从这里处理符号很容易。

- Captain Segfault

Answer 3

之前发布的C代码过于冗长：

unsigned a1, b1, a2, b2, c1, c2;

c1 = a1 + b1;
c2 = a2 + b2;

if (c1 < a1)
    c2++;

在“if”语句中，“a1”也可以替换为“b1”。 溢出时，“c1”将小于“a1”和“b1”。

- AndyV

Answer 4

如果64位数字为(a₂,a₁)和(b₂,b₁),其中x₂表示无符号的高32位，x₁表示无符号的低32位，则两个数字的总和如下所示。

c1 = a1 + b1

c2 = a2 + b2

if (c1 < a1 || c1 < b1)
   c2 += 1

- DigitalRoss

---

确保a1、b1、c1为无符号数，以便比较能够正确执行。 - Keith Randall

顺便问一下，如果我们只有两个64位的数字，a1、b1、a2和b2分别是什么？ - Light_handle

各位，感谢您们的评论。我已经尽力填写了答案。 - DigitalRoss

Answer 5

它看起来像这样

/* break up the 64bit number into smaller, 16bit chunks */
struct longint { 
    uint16 word0; 
    uint16 word1;
    uint16 word2;
    uint16 word3;
};

uint16 add(longint *result, longint *a, longint *b)
{
    /* use an intermediate large enough to hold the result
       of adding two 16 bit numbers together. */
    uint32 partial;

    /* add the chunks together, least significant bit first */
    partial = a->word0 + b->word0;

    /* extract thie low 16 bits of the sum and store it */
    result->word0 = partial & 0x0000FFFF;

    /* add the overflow to the next chunk of 16 */
    partial = partial >> 16 + a->word1 + b->word1;
    /* keep doing this for the remaining bits */
    result->word1 = partial & 0x0000FFFF;
    partial = partial >> 16 + a->word2 + b->word2;
    result->word2 = partial & 0x0000FFFF;
    partial = partial >> 16 + a->word3 + b->word3;
    result->word3 = partial & 0x0000FFFF;
    /* if the result overflowed, return nonzero */
    return partial >> 16;
}

实际的硬件并不会一次性使用32位来加上16位，只需一个额外的进位位即可进行加法运算。几乎所有的CPU都有一个进位状态标志，用于表示加法操作是否溢出。因此，如果您正在使用一个32位的CPU，您可以通过两个32位的操作来添加64位的操作数。

- SingleNegationElimination

Answer 6

几乎每个处理器都有进位位和带进位操作，只有在汇编语言编程时才需要关注。如果使用高级语言，则编译器会输出完全相同的带进位操作。我的AVR-GCC在将两个16位数字相加时给出了这个结果——AVR是8位的——但相同的概念也适用于更高级的处理器。

假设数字存储在寄存器R1:R2和R3:R4中：

ADD R2,R4 ; first add the two low-bytes, result stored into R2
ADC R1,R3 ; then the two high-bytes and the carry bit, into R1

结果被存储在 R1:R2 中。

- Nick T

---

为什么在使用扩展的64位寄存器时，需要利用32位数字进行64位算术运算？ - Cole Tobin