我正在寻找一种有效(可选标准、优雅且易于实现)的解决方案来乘以相对较大的数字,并将结果存储为一个或多个整数:
假设我有两个这样声明的 64 位整数:
uint64_t a = xxx, b = yyy;
当我执行 a * b
时,如何检测该操作是否导致溢出并在这种情况下将进位存储在某处?
请注意,我不想使用任何大数库,因为我对存储数字的方式有限制。
最佳答案
<强>1。检测溢出:
x = a * b;
if (a != 0 && x / a != b) {
// overflow handling
}
编辑:固定除以0
(感谢马克!)
<强>2。计算进位非常复杂。一种方法是将两个操作数拆分为半字,然后应用 long multiplication到半字:
uint64_t hi(uint64_t x) {
return x >> 32;
}
uint64_t lo(uint64_t x) {
return ((1ULL << 32) - 1) & x;
}
void multiply(uint64_t a, uint64_t b) {
// actually uint32_t would do, but the casting is annoying
uint64_t s0, s1, s2, s3;
uint64_t x = lo(a) * lo(b);
s0 = lo(x);
x = hi(a) * lo(b) + hi(x);
s1 = lo(x);
s2 = hi(x);
x = s1 + lo(a) * hi(b);
s1 = lo(x);
x = s2 + hi(a) * hi(b) + hi(x);
s2 = lo(x);
s3 = hi(x);
uint64_t result = s1 << 32 | s0;
uint64_t carry = s3 << 32 | s2;
}
为了确保部分和本身不会溢出,我们考虑最坏的情况:
x = s2 + hi(a) * hi(b) + hi(x)
让B = 1 << 32
.那么我们有
x <= (B - 1) + (B - 1)(B - 1) + (B - 1)
<= B*B - 1
< B*B
我相信这会奏效——至少它可以处理 Sjlver 的测试用例。除此之外,它未经测试(甚至可能无法编译,因为我手边没有 C++ 编译器)。
关于在两个大整数相乘期间捕获并计算溢出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51019606/