如何使用32位算术加法计算两个64位数字的和?
首先加上最不重要的字节,保留进位。接着加上最重要的字节时要考虑来自最不重要字节的进位:
; x86 assembly, Intel syntax
; adds ecx:ebx to edx:eax
add eax, ebx
adc edx, ecx
考虑如何使用一位数的算法相加两个两位数。
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!
所有这些都假定您正在执行无符号算术,但从这里处理符号很容易。
unsigned a1, b1, a2, b2, c1, c2;
c1 = a1 + b1;
c2 = a2 + b2;
if (c1 < a1)
c2++;
c1 = a1 + b1
c2 = a2 + b2
if (c1 < a1 || c1 < b1)
c2 += 1
它看起来像这样
/* 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;
}
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 中。
add eax, 0xFFFFFFFF
,其效果与sub eax, 1
相同。请注意,这不会改变eax寄存器的值。 - BenW