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


当前回答

最简单的方法是将unsigned long转换为unsigned long,进行乘法运算,并将结果与0x100000000LL进行比较。

你可能会发现这比你在例子中做除法更有效。

哦,它在C和c++中都可以工作(因为你已经用这两种语言标记了问题)。


我在看glibc手册。这里提到了整数溢出陷阱(FPE_INTOVF_TRAP)作为SIGFPE的一部分。这将是理想的,除了手册中令人讨厌的部分:

FPE_INTOVF_TRAP 整数溢出(在C程序中不可能,除非您以特定于硬件的方式启用溢出捕获)。

真的有点遗憾。

其他回答

有一种方法可以确定一个操作是否可能溢出,使用操作数中最高位的位置和一些基本的二进制数学知识。

对于加法,任何两个操作数的结果(最多)比最大操作数的最高1位多1位。例如:

bool addition_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits<32 && b_bits<32);
}

对于乘法,任何两个操作数的结果(最多)是操作数的位数之和。例如:

bool multiplication_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits+b_bits<=32);
}

类似地,你可以像这样估计a的b次方结果的最大大小:

bool exponentiation_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a);
    return (a_bits*b<=32);
}

(当然,用比特数代替目标整数。)

我不确定确定数字中最高的1位位置的最快方法,这里有一个蛮力方法:

size_t highestOneBitPosition(uint32_t a) {
    size_t bits=0;
    while (a!=0) {
        ++bits;
        a>>=1;
    };
    return bits;
}

它不是完美的,但它能让你在做运算之前知道是否有两个数会溢出。我不知道它是否会比您建议的方式检查结果更快,因为highestOneBitPosition函数中的循环,但它可能会(特别是如果您事先知道操作数中有多少位)。

另一种使用汇编语言的解决方案是外部过程。下面是在Linux x64下使用g++和fasm进行无符号整数乘法的示例。

这个过程将两个无符号整数参数相乘(32位)(根据amd64的规范(第3.2.3节参数传递)。

如果类为INTEGER,则使用序列%rdi、%rsi、%rdx、%rcx、%r8和%r9的下一个可用寄存器

(edi和esi寄存器在我的代码)),并返回结果或0,如果发生溢出。

format ELF64

section '.text' executable

public u_mul

u_mul:
  MOV eax, edi
  mul esi
  jnc u_mul_ret
  xor eax, eax
u_mul_ret:
ret

测试:

extern "C" unsigned int u_mul(const unsigned int a, const unsigned int b);

int main() {
    printf("%u\n", u_mul(4000000000,2)); // 0
    printf("%u\n", u_mul(UINT_MAX/2,2)); // OK
    return 0;
}

将程序链接到asm对象文件。在我的例子中,在Qt Creator中将它添加到一个.pro文件中的LIBS中。

为了扩展Head Geek的答案,有一种更快的方法来执行addition_is_safe;

bool addition_is_safe(unsigned int a, unsigned int b)
{
    unsigned int L_Mask = std::numeric_limits<unsigned int>::max();
    L_Mask >>= 1;
    L_Mask = ~L_Mask;

    a &= L_Mask;
    b &= L_Mask;

    return ( a == 0 || b == 0 );
}

这使用了机器架构安全,64位和32位无符号整数仍然可以正常工作。基本上,我创建了一个掩码,它将屏蔽除最重要的位外的所有内容。然后,对两个整数进行掩码,如果其中任何一个没有设置该位,则加法是安全的。

如果在某个构造函数中预初始化掩码,这将更快,因为它永远不会改变。

要以一种可移植的方式执行无符号乘法而不溢出,可以使用以下方法:

... /* begin multiplication */
unsigned multiplicand, multiplier, product, productHalf;
int zeroesMultiplicand, zeroesMultiplier;
zeroesMultiplicand = number_of_leading_zeroes( multiplicand );
zeroesMultiplier   = number_of_leading_zeroes( multiplier );
if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow;
productHalf = multiplicand * ( c >> 1 );
if( (int)productHalf < 0 ) goto overflow;
product = productHalf * 2;
if( multiplier & 1 ){
   product += multiplicand;
   if( product < multiplicand ) goto overflow;
}
..../* continue code here where "product" is the correct product */
....
overflow: /* put overflow handling code here */

int number_of_leading_zeroes( unsigned value ){
   int ctZeroes;
   if( value == 0 ) return 32;
   ctZeroes = 1;
   if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; }
   if( ( value >> 24 ) == 0 ){ ctZeroes +=  8; value = value <<  8; }
   if( ( value >> 28 ) == 0 ){ ctZeroes +=  4; value = value <<  4; }
   if( ( value >> 30 ) == 0 ){ ctZeroes +=  2; value = value <<  2; }
   ctZeroes -= x >> 31;
   return ctZeroes;
}

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)