使用 32 位算术添加 64 位数字

Question

我们如何使用 32 位算术将两个 64 位数字相加？

Answer 1

首先添加最低有效字节，保留进位。考虑到 LSB 的进位，添加最高有效字节：

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

Answer 2

考虑如何使用一位数算术将两个两位数相加。

 42
+39
---

首先添加右列。 （“个”或“单位”）。 2+9 是 11。11“溢出”了您的 1 位算术，因此您必须“进位”10。

 1
 42
+39
---
  1

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

 1
 42
+39
---
 81

8 小于 10，所以没有进位。你完成了。

刚刚发生了什么？当你说一个数字是“42”（以 10 为基数）时，你真正的意思是

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。 （假设它是无符号的。）

因此，我们不要使用基数 10，而是使用基数 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

现在，以 2^32 为基数将它们相加，就像以 10 为基数相加一样，只是，而不是使用数字算术相加使用 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！

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

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。

Answer 4

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

c1 = a1 + b1

c2 = a2 + b2

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

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 位操作数。

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 中。