我用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++中检测有符号溢出。


当前回答

salter先生的回答是个好主意。

如果整数计算是必需的(为了精度),但浮点数是可用的,你可以这样做:

uint64_t foo(uint64_t a, uint64_t b) {
    double dc;

    dc = pow(a, b);

    if (dc < UINT_MAX) {
       return (powu64(a, b));
    }
    else {
      // Overflow
    }
}

其他回答

I see that a lot of people answered the question about overflow, but I wanted to address his original problem. He said the problem was to find ab=c such that all digits are used without repeating. Ok, that's not what he asked in this post, but I'm still think that it was necessary to study the upper bound of the problem and conclude that he would never need to calculate or detect an overflow (note: I'm not proficient in math so I did this step by step, but the end result was so simple that this might have a simple formula).

重点是问题要求的a b c的上限是98.765.432。不管怎样,先把问题分成琐碎部分和非琐碎部分:

X0 == 1(9、8、7、6、5、4、3、2的所有排列都是解) X1 == x(无解) 0b == 0(不可能解) 1b == 1(无解) Ab, a > 1, b > 1(非平凡)

Now we just need to show that no other solution is possible and only the permutations are valid (and then the code to print them is trivial). We go back to the upper bound. Actually the upper bound is c ≤ 98.765.432. It's the upper bound because it's the largest number with 8 digits (10 digits total minus 1 for each a and b). This upper bound is only for c because the bounds for a and b must be much lower because of the exponential growth, as we can calculate, varying b from 2 to the upper bound:

    9938.08^2 == 98765432
    462.241^3 == 98765432
    99.6899^4 == 98765432
    39.7119^5 == 98765432
    21.4998^6 == 98765432
    13.8703^7 == 98765432
    9.98448^8 == 98765432
    7.73196^9 == 98765432
    6.30174^10 == 98765432
    5.33068^11 == 98765432
    4.63679^12 == 98765432
    4.12069^13 == 98765432
    3.72429^14 == 98765432
    3.41172^15 == 98765432
    3.15982^16 == 98765432
    2.95305^17 == 98765432
    2.78064^18 == 98765432
    2.63493^19 == 98765432
    2.51033^20 == 98765432
    2.40268^21 == 98765432
    2.30883^22 == 98765432
    2.22634^23 == 98765432
    2.15332^24 == 98765432
    2.08826^25 == 98765432
    2.02995^26 == 98765432
    1.97741^27 == 98765432

注意,例如最后一行:它说1.97^27 ~98M。因此,例如,1^27 == 1和2^27 == 134.217.728,这不是一个解决方案,因为它有9位数字(2 > 1.97,所以它实际上比应该测试的要大)。可以看到,用于测试a和b的组合非常小。对于b == 14,我们需要尝试2和3。对于b == 3,我们从2开始,到462结束。结果均小于~98M。

现在只需测试以上所有的组合,找出不重复任何数字的组合:

    ['0', '2', '4', '5', '6', '7', '8'] 84^2 = 7056
    ['1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481
    ['0', '1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481 (+leading zero)
    ['1', '2', '3', '5', '8'] 8^3 = 512
    ['0', '1', '2', '3', '5', '8'] 8^3 = 512 (+leading zero)
    ['1', '2', '4', '6'] 4^2 = 16
    ['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
    ['1', '2', '4', '6'] 2^4 = 16
    ['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
    ['1', '2', '8', '9'] 9^2 = 81
    ['0', '1', '2', '8', '9'] 9^2 = 81 (+leading zero)
    ['1', '3', '4', '8'] 3^4 = 81
    ['0', '1', '3', '4', '8'] 3^4 = 81 (+leading zero)
    ['2', '3', '6', '7', '9'] 3^6 = 729
    ['0', '2', '3', '6', '7', '9'] 3^6 = 729 (+leading zero)
    ['2', '3', '8'] 2^3 = 8
    ['0', '2', '3', '8'] 2^3 = 8 (+leading zero)
    ['2', '3', '9'] 3^2 = 9
    ['0', '2', '3', '9'] 3^2 = 9 (+leading zero)
    ['2', '4', '6', '8'] 8^2 = 64
    ['0', '2', '4', '6', '8'] 8^2 = 64 (+leading zero)
    ['2', '4', '7', '9'] 7^2 = 49
    ['0', '2', '4', '7', '9'] 7^2 = 49 (+leading zero)

没有一个匹配问题(这也可以通过缺少'0','1',…“9”)。

下面是解决该问题的示例代码。还要注意,这是用Python编写的,不是因为它需要任意精确整数(代码不会计算任何大于9800万的数字),而是因为我们发现测试的数量非常少,所以我们应该使用高级语言来利用其内置的容器和库(还要注意:代码有28行)。

    import math

    m = 98765432
    l = []
    for i in xrange(2, 98765432):
        inv = 1.0/i
        r = m**inv
        if (r < 2.0): break
        top = int(math.floor(r))
        assert(top <= m)

        for j in xrange(2, top+1):
            s = str(i) + str(j) + str(j**i)
            l.append((sorted(s), i, j, j**i))
            assert(j**i <= m)

    l.sort()
    for s, i, j, ji in l:
        assert(ji <= m)
        ss = sorted(set(s))
        if s == ss:
            print '%s %d^%d = %d' % (s, i, j, ji)

        # Try with non significant zero somewhere
        s = ['0'] + s
        ss = sorted(set(s))
        if s == ss:
            print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji)

如果您有一个比您想要测试的数据类型大的数据类型(比如您做了一个32位的添加,而您有一个64位的类型),那么这将检测是否发生溢出。我的例子是一个8位的添加。但它可以放大。

uint8_t x, y;    /* Give these values */
const uint16_t data16    = x + y;
const bool carry        = (data16 > 0xFF);
const bool overflow     = ((~(x ^ y)) & (x ^ data16) & 0x80);

它基于本页解释的概念:http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html

对于一个32位的例子,0xFF变成0xFFFFFFFF, 0x80变成0x80000000,最后uint16_t变成uint64_t。

注意:这捕获整数加法/减法溢出,我意识到你的问题涉及乘法。在这种情况下,分裂可能是最好的办法。这通常是calloc实现确保参数在相乘以获得最终大小时不会溢出的一种方式。

这里有一个非常快速的方法来检测溢出,至少是加法,这可能会为乘法、除法和乘方提供线索。

其思想是,正是因为处理器会让值归零,而C/ c++是从任何特定的处理器抽象出来的,你可以:

uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);

这既确保了如果一个操作数为零,另一个操作数为零,则不会错误地检测到溢出,而且比前面建议的许多NOT/XOR/ and /test操作要快得多。

正如所指出的,这种方法虽然比其他更精细的方法更好,但仍然是可优化的。以下是包含优化的原始代码的修订:

uint32_t x, y;
uint32_t value = x + y;
const bool overflow = value < x; // Alternatively "value < y" should also work

一种更有效、更廉价的检测乘法溢出的方法是:

uint32_t x, y;
const uint32_t a = (x >> 16U) * (y & 0xFFFFU);
const uint32_t b = (x & 0xFFFFU) * (y >> 16U);
const bool overflow = ((x >> 16U) * (y >> 16U)) +
    (a >> 16U) + (b >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;

这将导致UINT32_MAX溢出,或乘法的结果。在这种情况下,允许对有符号整数进行乘法运算是严格未定义的行为。

值得注意的是,这使用部分Karatsuba方法乘法分解来计算64位乘法的高32位,以检查是否应该设置它们中的任何一个,以了解32位乘法是否溢出。

如果使用c++,你可以把这个转换成一个简洁的小lambda来计算溢出,这样检测器的内部工作就被隐藏了:

uint32_t x, y;
const bool overflow
{
    [](const uint32_t x, const uint32_t y) noexcept -> bool
    {
        const uint32_t a{(x >> 16U) * uint16_t(y)};
        const uint32_t b{uint16_t(x) * (y >> 16U)};
        return ((x >> 16U) * (y >> 16U)) + (a >> 16U) + (b >> 16U);
    }(x, y)
};
uint32_t value{overflow ? UINT32_MAX : x * y};

x86指令集包括一个无符号乘法指令,它将结果存储到两个寄存器中。要使用C中的指令,可以在64位程序(GCC)中编写以下代码:

unsigned long checked_imul(unsigned long a, unsigned long b) {
  unsigned __int128 res = (unsigned __int128)a * b;
  if ((unsigned long)(res >> 64))
    printf("overflow in integer multiply");
  return (unsigned long)res;
}

对于32位程序,需要使结果为64位,参数为32位。

另一种方法是使用依赖于编译器的intrinsic来检查标志寄存器。关于溢出的GCC文档可以从6.56内置函数执行溢出检查算术中找到。

测试溢出的简单方法是通过检查当前值是否小于前一个值来进行验证。例如,假设你有一个循环输出2的幂:

long lng;
int n;
for (n = 0; n < 34; ++n)
{
   lng = pow (2, n);
   printf ("%li\n", lng);
}

添加溢出检查的方式,我描述的结果如下:

long signed lng, lng_prev = 0;
int n;
for (n = 0; n < 34; ++n)
{
    lng = pow (2, n);
    if (lng <= lng_prev)
    {
        printf ("Overflow: %i\n", n);
        /* Do whatever you do in the event of overflow.  */
    }
    printf ("%li\n", lng);
    lng_prev = lng;
}

它既适用于无符号值,也适用于正负符号值。

当然,如果您想对递减值而不是递增值执行类似的操作,您可以将<=符号翻转,使其为>=,假设下溢的行为与溢出的行为相同。坦率地说,这是在不访问CPU溢出标志的情况下所获得的可移植性(这将需要内联汇编代码,使您的代码在实现之间无法移植)。