我用c++写了一个程序来寻找ab = C的所有解,其中a, b和C一起使用所有的数字0-9,只使用一次。程序循环遍历a和b的值,并每次对a、b和ab运行数字计数例程,以检查是否满足数字条件。
但是,当ab超出整数限制时,会产生伪解。我最终使用如下代码来检查这个:
unsigned long b, c, c_test;
...
c_test=c*b; // Possible overflow
if (c_test/b != c) {/* There has been an overflow*/}
else c=c_test; // No overflow
是否有更好的方法来测试溢出?我知道有些芯片有一个内部标志,在溢出发生时设置,但我从未见过通过C或c++访问它。
注意,有符号int溢出在C和c++中是未定义的行为,因此您必须在不实际引起它的情况下检测它。对于加法前的有符号整型溢出,请参见在C/ c++中检测有符号溢出。
我需要为浮点数回答同样的问题,在浮点数中位屏蔽和移位看起来没有希望。我确定的方法适用于有符号和无符号,整数和浮点数。即使没有更大的数据类型可以用于中间计算,它也可以工作。对于所有这些类型,它不是最有效的,但因为它确实适用于所有类型,所以值得使用。
有符号溢出测试,加减法:
Obtain the constants that represent the largest and smallest possible values for the type,
MAXVALUE and MINVALUE.
Compute and compare the signs of the operands.
a. If either value is zero, then neither addition nor subtraction can overflow. Skip remaining tests.
b. If the signs are opposite, then addition cannot overflow. Skip remaining tests.
c. If the signs are the same, then subtraction cannot overflow. Skip remaining tests.
Test for positive overflow of MAXVALUE.
a. If both signs are positive and MAXVALUE - A < B, then addition will overflow.
b. If the sign of B is negative and MAXVALUE - A < -B, then subtraction will overflow.
Test for negative overflow of MINVALUE.
a. If both signs are negative and MINVALUE - A > B, then addition will overflow.
b. If the sign of A is negative and MINVALUE - A > B, then subtraction will overflow.
Otherwise, no overflow.
签名溢出测试,乘法和除法:
Obtain the constants that represent the largest and smallest possible values for the type,
MAXVALUE and MINVALUE.
Compute and compare the magnitudes (absolute values) of the operands to one. (Below, assume A and B are these magnitudes, not the signed originals.)
a. If either value is zero, multiplication cannot overflow, and division will yield zero or an infinity.
b. If either value is one, multiplication and division cannot overflow.
c. If the magnitude of one operand is below one and of the other is greater than one, multiplication cannot overflow.
d. If the magnitudes are both less than one, division cannot overflow.
Test for positive overflow of MAXVALUE.
a. If both operands are greater than one and MAXVALUE / A < B, then multiplication will overflow.
b. If B is less than one and MAXVALUE * B < A, then division will overflow.
Otherwise, no overflow.
注意:MINVALUE的最小溢出由3处理,因为我们取的是绝对值。然而,如果
ABS(MINVALUE) > MAXVALUE,那么我们将会有一些罕见的假阳性。
下溢测试类似,但涉及EPSILON(大于零的最小正数)。
这里有一个“不可移植”的解决方案。Intel x86和x64 cpu有所谓的eflags寄存器,在每次整数算术运算后由处理器填充。我将跳过这里的详细描述。相关的标志是“溢出”标志(掩码0x800)和“携带”标志(掩码0x1)。为了正确地解释它们,应该考虑操作数是有符号类型还是无符号类型。
下面是一个从C/ c++中检查标志的实用方法。下面的代码可以在Visual Studio 2005或更新版本(32位和64位)上运行,也可以在GNU C/ c++ 64位上运行。
#include <cstddef>
#if defined( _MSC_VER )
#include <intrin.h>
#endif
inline size_t query_intel_x86_eflags(const size_t query_bit_mask)
{
#if defined( _MSC_VER )
return __readeflags() & query_bit_mask;
#elif defined( __GNUC__ )
// This code will work only on 64-bit GNU-C machines.
// Tested and does NOT work with Intel C++ 10.1!
size_t eflags;
__asm__ __volatile__(
"pushfq \n\t"
"pop %%rax\n\t"
"movq %%rax, %0\n\t"
:"=r"(eflags)
:
:"%rax"
);
return eflags & query_bit_mask;
#else
#pragma message("No inline assembly will work with this compiler!")
return 0;
#endif
}
int main(int argc, char **argv)
{
int x = 1000000000;
int y = 20000;
int z = x * y;
int f = query_intel_x86_eflags(0x801);
printf("%X\n", f);
}
如果操作数相乘而没有溢出,则query_intel_eflags(0x801)将得到0的返回值,即既没有设置进位标志,也没有设置溢出标志。在提供的main()示例代码中,发生溢出,并且两个标志都被设置为1。这个检查并不意味着任何进一步的计算,所以它应该相当快。
我需要为浮点数回答同样的问题,在浮点数中位屏蔽和移位看起来没有希望。我确定的方法适用于有符号和无符号,整数和浮点数。即使没有更大的数据类型可以用于中间计算,它也可以工作。对于所有这些类型,它不是最有效的,但因为它确实适用于所有类型,所以值得使用。
有符号溢出测试,加减法:
Obtain the constants that represent the largest and smallest possible values for the type,
MAXVALUE and MINVALUE.
Compute and compare the signs of the operands.
a. If either value is zero, then neither addition nor subtraction can overflow. Skip remaining tests.
b. If the signs are opposite, then addition cannot overflow. Skip remaining tests.
c. If the signs are the same, then subtraction cannot overflow. Skip remaining tests.
Test for positive overflow of MAXVALUE.
a. If both signs are positive and MAXVALUE - A < B, then addition will overflow.
b. If the sign of B is negative and MAXVALUE - A < -B, then subtraction will overflow.
Test for negative overflow of MINVALUE.
a. If both signs are negative and MINVALUE - A > B, then addition will overflow.
b. If the sign of A is negative and MINVALUE - A > B, then subtraction will overflow.
Otherwise, no overflow.
签名溢出测试,乘法和除法:
Obtain the constants that represent the largest and smallest possible values for the type,
MAXVALUE and MINVALUE.
Compute and compare the magnitudes (absolute values) of the operands to one. (Below, assume A and B are these magnitudes, not the signed originals.)
a. If either value is zero, multiplication cannot overflow, and division will yield zero or an infinity.
b. If either value is one, multiplication and division cannot overflow.
c. If the magnitude of one operand is below one and of the other is greater than one, multiplication cannot overflow.
d. If the magnitudes are both less than one, division cannot overflow.
Test for positive overflow of MAXVALUE.
a. If both operands are greater than one and MAXVALUE / A < B, then multiplication will overflow.
b. If B is less than one and MAXVALUE * B < A, then division will overflow.
Otherwise, no overflow.
注意:MINVALUE的最小溢出由3处理,因为我们取的是绝对值。然而,如果
ABS(MINVALUE) > MAXVALUE,那么我们将会有一些罕见的假阳性。
下溢测试类似,但涉及EPSILON(大于零的最小正数)。