使用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

考虑如何使用1位数运算添加两个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"时,我的意思是"提升到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

现在你将它们添加到base 2 ^ 32中,就像你在base 10中添加它们一样 - 只是,而不是使用32位算术添加数字运算!

如何将64位数a分成两个32位数a_1和a_0？除以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，可以将64位操作数加到两个，32位操作。