在进行数学运算时,如何获取溢出的部分?
例如,假设使用32位整数:
unsigned int a = 0Xffffffff;
unsigned int b = 0xffffffff;
unsigned int c = a + b;
在这种情况下,c
是 0xfffffffe
,但答案应该是 0x1fffffffe
。我该如何获取溢出的1?
同样的,对于乘法,我该如何做到相同的效果?我可以将两个大数相乘并仅获取溢出部分吗?
bigint(大整数)库是如何管理这个的?
在进行数学运算时,如何获取溢出的部分?
例如,假设使用32位整数:
unsigned int a = 0Xffffffff;
unsigned int b = 0xffffffff;
unsigned int c = a + b;
在这种情况下,c
是 0xfffffffe
,但答案应该是 0x1fffffffe
。我该如何获取溢出的1?
同样的,对于乘法,我该如何做到相同的效果?我可以将两个大数相乘并仅获取溢出部分吗?
bigint(大整数)库是如何管理这个的?
@警告 不可移植@
示例:https://godbolt.org/z/NcyNzR
#include <stdio.h>
int main(void)
{
unsigned int res;
if(__builtin_uadd_overflow(0Xffffffff, 0Xffffffff, &res))
{
printf("Overflowed\n");
}
printf("Result: 0x%x\n", res);
}
bool cf = a+b<a;
或者
bool cf = a>-1-b;
这些内容不受需要使用的更大类型的存在影响。
乘法更加困难;如果没有更大的类型,就无法访问结果的上半部分。如果您有更大的类型,可以使用它。例如,如果您的操作数是uint32_t
,
uint32_t upper = ((uint64_t)a * b) >> 32;
uint32_t lower = a*b;
uint64_t a,b;
的情况。uint32_t al = a, ah = a>>32;
uint32_t bl = b, bh = b>>32;
然后结果的上半部分是ah*bh
加上al*bh
、ah*bl
和al*bl
的进位位。
Bigint库可以通过选择一个最多只有最大整数类型宽度一半的limb类型来避免这种痛苦。
我如何获取溢出的1?
为了便于移植(不要忘记unsigned int
可能只有16位),稍后可以这样做:
uint32_t a = 0Xffffffff;
uint32_t b = 0xffffffff;
uint32_t c_low = a + b;
uint32_t c_high;
if(c_low >= a) {
c_high = 0;
} else {
c_high = 1;
}
为了以便携的方式提前完成它(无需分支):
uint32_t a = 0Xffffffff;
uint32_t b = 0xffffffff;
uint32_t c_low;
uint32_t c_high;
c_high = (a&b) >> 31;
c_low = (a ^ (c_high<<31)) + b;
uint32_t a = 0Xffffffff;
uint32_t b = 0xffffffff;
uint64_t temp = (uint64_t)a * (uint64_t)b;
uint32_t c_low = temp;
uint32_t c_high = temp >> 32;
uint32_t a = 0Xffffffff;
uint32_t b = 0xffffffff;
uint32_t a_low = a & 0xFFFF;
uint32_t a_high = a >> 16;
uint32_t b_low = a & 0xFFFF;
uint32_t b_high = b >> 16;
uint32_t temp_0 = a_low * b_low;
uint32_t temp_16a = a_high * b_low;
uint32_t temp_16b = a_low * b_high;
uint32_t temp_32 = a_high * b_high;
uint32_t c_low = temp_0 + (temp16a << 16) + (temp16b << 16);
uint32_t c_high = (temp16a >> 16) + (temp16b >> 16) + temp_32;
adc
/sbb
、shld
/shrd
、mul
(带有双宽结果)/div
(带有双宽分子)以及可能的扩展(adcx
和adox
)。 xor edx,0
add eax,ebx ;c_low = a + b
adc edx,0 ;c_high = carry
...乘法可能看起来像这样:
mul ebx ;edx:eax = a * b
if(UINT_MAX - a < b) then handle_it()
。 - DCTID(unsigned long long int) a * b
来得出乘积,之后可以通过移位和掩码来提取低位和高位的 32 位。 - Eric Postpischil