大量繁殖,如何捕捉溢出 [英] multiplication of large numbers, how to catch overflow
问题描述
我要寻找一个有效的(可选标准,优雅,易于实现的)解决方案,以繁殖比较大的数字,并将结果存储到一个或几个整数:
I am looking for an efficient (optionally standard, elegant and easy to implement) solution to multiply relatively large numbers,and store the result into one or several integers :
让说我有声明如下两个64位的整数:
Let say I have two 64 bits integers declared like this :
uint64_t a = xxx, b = yyy;
当我这样做 A * B
,我怎么能检测如果操作导致溢出,在这种情况下,店里进的地方?
When I do a*b
, how can I detect if the operation result in an overflow and in this case store the carry somewhere ?
请注意,我不希望因为我有我存储数字的方式限制使用任何大数量的库。
Please note that I don't want to use any large-number library since I have constraints on the way I store the numbers.
感谢
推荐答案
检测:
x = a * b;
if (a != 0 && x / a != b) {
// overflow handling
}
编辑:固定除数为0(!感谢马克)
Fixed division by 0 (thanks Mark!)
计算进是相当复杂。一种方法是将两个操作数分成半字,然后应用长乘法以半字
Computing the carry is quite involved. One approach is to split both operands into half-words, then apply long multiplication to the half-words:
uint64_t hi(uint64_t x) {
return x >> 32;
}
uint64_t lo(uint64_t x) {
return ((1 << 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;
}
要看到,没有一个部分和本身可以溢出,我们认为最坏的情况:
To see that none of the partial sums themselves can overflow, we consider the worst case:
x = s2 + hi(a) * hi(b) + hi(x)
让B = 1&LT;&LT; 32.然后我们有
Let B = 1 << 32. We then have
x <= (B - 1) + (B - 1)(B - 1) + (B - 1)
<= B*B - 1
< B*B
我相信这将工作 - 至少它处理Sjlver的测试用例。除此之外,它是未经测试(可能甚至不会编译,因为我没有手头C ++编译器了)。
I believe this will work - at least it handles Sjlver's test case. Aside from that, it is untested (and might not even compile, as I don't have a C++ compiler at hand anymore).
这篇关于大量繁殖,如何捕捉溢出的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!