首页 文章

如何检测整数溢出？

提问于
浏览 次
539

我在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访问过 .

c++ c integer-overflow

30 回答

  • 14

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

    你可能会发现这比你在你的例子中所做的更有效 .

    哦，它在C和C都有效（因为你用两者标记了问题） .

    刚刚看了glibc manual . 作为 SIGFPE 的一部分，提到了整数溢出陷阱（ FPE_INTOVF_TRAP ） . 除了手册中讨厌的内容之外，这将是理想的：

    FPE_INTOVF_TRAP整数溢出（在C程序中不可能，除非您以特定于硬件的方式启用溢出捕获） .

    真的有点遗憾 .

    回复于
  • 8

    对于无符号整数，只需检查结果是否小于其中一个参数：

    unsigned int r, a, b;
r = a+b;
if (r < a)
{
    // overflow
}

    对于有符号整数，您可以检查参数和结果的符号 . 不同符号的整数不能溢出，只有相同符号溢出的整数才会产生不同的符号：

    signed int r, a, b, s;
r = a+b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
    // overflow
}
    回复于
  • 0

    为了扩展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位无符号整数仍然可以正常工作 . 基本上，我创建了一个掩盖除了最重要的位之外的所有掩码 . 然后，我屏蔽两个整数，如果其中任何一个没有设置该位，那么添加是安全的 .

    如果你在某个构造函数中预先初始化蒙版，这会更快，因为它永远不会改变 .

    回复于
  • 18

    我看到你正在使用无符号整数 . 根据定义， in C （不知道C），无符号算术不会溢出...所以，至少对于C来说，你的观点是没有意义的:)

    对于有符号整数，一旦出现溢出，Undefined Behaviour已经发生并且您的程序可以执行任何操作（例如：渲染测试不确定） .

    #include <limits.h>
int a = <something>;
int x = <something>;
a += x;              /* UB */
if (a < 0) {         /* unreliable test */
  /* ... */
}

    要创建一个符合要求的程序，您需要测试溢出 before 产生所述溢出 . 该方法也可以与无符号整数一起使用

    // for addition
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x > 0) && (a > INT_MAX - x)) /* `a + x` would overflow */;
if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */;

    // for subtraction
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x < 0) && (a > INT_MAX + x)) /* `a - x` would overflow */;
if ((x > 0) && (a < INT_MIN + x)) /* `a - x` would underflow */;

    // for multiplication
#include <limits.h>
int a = <something>;
int x = <something>;
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;
// there may be need to check for -1 for two's complement machines
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */

    对于除法（除了 INT_MIN 和 -1 特殊情况），不可能超过 INT_MIN 或 INT_MAX .

    回复于
  • 160

    有些编译器可以访问CPU中的整数溢出标志，然后可以测试，但这不是标准的 .

    您还可以在执行乘法之前测试溢出的可能性：

    if ( b > ULONG_MAX / a ) // a * b would overflow
    回复于
  • 11

    使用汇编程序的另一种解决方案是外部程序 . 这个例子用于在linux x64下使用g和fasm进行无符号整数乘法 .

    此过程将两个无符号整数参数（32位）相乘（根据specification for 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

    回复于
  • 2

    @MSalters：好主意 .

    如果需要整数计算（对于精度），但浮点可用，则可以执行以下操作：

    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
    }
}
    回复于
  • 19

    clang 现在支持有符号和无符号整数的动态溢出检查 . 见-fsanitize=integer开关 . 目前，只有一个C编译器具有完全支持的动态溢出检查以用于调试目的 .

    回复于
  • 5

    试试这个宏来测试32位机器的溢出位（改编了Angel Sinigersky的解决方案）

    #define overflowflag(isOverflow){   \
size_t eflags;                      \
asm ("pushfl ;"                     \
     "pop %%eax"                    \
    : "=a" (eflags));               \
isOverflow = (eflags >> 11) & 1;}

    我将其定义为宏，否则溢出位将被覆盖 .

    后面是一个带有上面代码段的小应用程序：

    #include <cstddef>
#include <stdio.h>
#include <iostream>
#include <conio.h>
#if defined( _MSC_VER )
#include <intrin.h>
#include <oskit/x86>
#endif

using namespace std;

#define detectOverflow(isOverflow){     \
size_t eflags;                      \
asm ("pushfl ;"                     \
    "pop %%eax"                     \
    : "=a" (eflags));               \
isOverflow = (eflags >> 11) & 1;}

int main(int argc, char **argv) {

    bool endTest = false;
    bool isOverflow;

    do {
        cout << "Enter two intergers" << endl;
        int x = 0;
        int y = 0;
        cin.clear();
        cin >> x >> y;
        int z = x * y;
        detectOverflow(isOverflow)
        printf("\nThe result is: %d", z);
        if (!isOverflow) {
            std::cout << ": no overflow occured\n" << std::endl;
        } else {
            std::cout << ": overflow occured\n" << std::endl;
        }

        z = x * x * y;
        detectOverflow(isOverflow)
        printf("\nThe result is: %d", z);
        if (!isOverflow) {
            std::cout << ": no overflow ocurred\n" << std::endl;
        } else {
            std::cout << ": overflow occured\n" << std::endl;
        }

        cout << "Do you want to stop? (Enter \"y\" or \"Y)" << endl;

        char c = 0;

        do {
            c = getchar();
        } while ((c == '\n') && (c != EOF));

        if (c == 'y' || c == 'Y') {
            endTest = true;
        }

        do {
            c = getchar();
        } while ((c != '\n') && (c != EOF));

    } while (!endTest);
}
    回复于
  • 13

    mozilla::CheckedInt<T>为整数类型 T 提供溢出检查整数数学运算（使用clang上的编译器内在函数和可用的gcc） . 代码在MPL 2.0下，依赖于三个（IntegerTypeTraits.h，Attributes.h和Compiler.h）其他仅标头的非标准库头以及特定于Mozilla的assertion machinery . 如果导入代码，您可能希望替换断言机制 .

    回复于
  • -3

    您无法从C / C访问溢出标志 .

    有些编译器允许您将陷阱指令插入代码中 . 在海湾合作委员会，选项是-ftrapv（但我必须承认我从未使用它 . 将在发布后检查它） .

    唯一的便携式和编译器独立的事情是你自己检查溢出 . 就像你在你的例子中所做的那样 .

    Edit:

    刚检查：-ftrapv似乎在使用最新的GCC的x86上什么也没做 . 猜猜它是旧版本遗留下来的，或者特定于其他一些架构 . 我曾期望编译器在每次添加后插入INTO操作码 . 不幸的是，它没有这样做 .

    回复于
  • 7

    您无法从C / C访问溢出标志 .

    我不同意这一点 . 您可以编写一些内联asm并使用 jo （跳转溢出）指令，假设您在x86上捕获溢出 . 当然，您的代码将不再可移植到其他架构 .

    看看 info as 和 info gcc .

    回复于
  • 0

    警告：GCC可以在使用 -O2 进行编译时优化掉溢出检查 . 在某些情况下，选项 -Wall 会给你一个警告

    if (a + b < a) { /* deal with overflow */ }

    但不是在这个例子中：

    b = abs(a);
if (b < 0) { /* deal with overflow */ }

    唯一安全的方法是在它发生之前检查溢出，如CERT paper中所述，系统使用这将是非常繁琐的 .

    使用 -fwrapv 进行编译可以解决问题，但会禁用某些优化 .

    我们迫切需要一个更好的解决方案 . 我认为编译器在进行依赖溢出的优化时默认情况下会发出警告 . 目前的情况允许编译器优化掉溢出检查，这在我看来是不可接受的 .

    回复于
  • 120

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

    另外，任何两个操作数将导致（最多）比最大操作数的最高一位多一位 . 例如：

    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);
}

    （当然，替换目标整数的位数 . ）

    我不确定以最快的方式确定数字中最高的一位的位置，这是一种强力方法：

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

    它's not perfect, but that' ll会让你知道在执行操作之前是否有任何两个数字都会溢出 . 我不知道它是否比简单地按照你建议的方式检查结果更快，因为 highestOneBitPosition 函数中的循环，但它可能（特别是如果你事先知道操作数中有多少位） .

    回复于
  • 50

    如果您的数据类型大于您要测试的数据类型（假设您执行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 .

    NOTE ：这会捕获整数加法/减法溢出，我意识到你的问题涉及乘法 . 在这种情况下，划分可能是最好的方法 . 这通常是 calloc 实现确保params不会溢出的方式，因为它们相乘以获得最终大小 .

    回复于
  • 173

    要以可移植的方式执行无符号乘法而不溢出，可以使用以下内容：

    ... /* 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;
}
    回复于
  • 3

    x86指令集包括无符号乘法指令，用于将结果存储到两个寄存器 . 要使用C中的指令，可以在64位程序（gcc）中编写以下代码：

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

    对于32位程序，需要将结果设为64位，参数为32位 .

    另一种方法是使用编译器依赖本能来检查标志寄存器 . 溢出本能的GCC文档可以在https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html找到

    回复于
  • -3

    另一个有趣的工具：http://embed.cs.utah.edu/ioc/

    这是一个修补的 clang 编译器，它在编译时向代码添加检查 . 所以你得到的输出看起来像这样：

    CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow, 
BINARY OPERATION: left (int32): 2147483647 right (int32): 1
    回复于
  • 36

    一种干净的方法是覆盖所有操作符（特别是*）并在执行操作之前检查溢出 .

    回复于
  • 5

    这取决于你使用它 . 执行无符号长（DWORD）加法或乘法最佳解决方案是使用ULARGE_INTEGER .

    ULARGE_INTEGER是两个DWORD的结构 . 完整值可以作为“QuadPart”访问，而hi DWORD作为“HighPart”访问，低DWORD作为“LowPart”访问

    例如：

    DWORD我的加法（DWORD Value_A，DWORD Value_B）{ULARGE_INTEGER a，b;

    b.LowPart = Value_A;  // a 32 bit value(up to 32 bit)
   b.HighPart = 0;
   a.LowPart = Value_B;  // a 32 bit value(up to 32 bit)
   a.HighPart = 0;

   a.QuadPart += b.QuadPart;

   // if  a.HighPart
   // Then a.HighPart contains the overflow(carry)

   return (a.LowPart + a.HighPart)

    //任何溢出都存储在a.HighPart中（最多32位）

    回复于
  • 0

    这是问题的"non-portable"解决方案 . Intel x86和x64 CPU具有所谓的EFLAGS寄存器（http://en.wikipedia.org/wiki/EFLAGS），在每次整数算术运算后由处理器填充 . 我将在这里略过详细说明 . 相关标志是"Overflow"标志（掩码0x800）和"Carry"标志（掩码为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.此检查并不意味着任何进一步的计算，因此它应该非常快 .

    回复于
  • 0

    Catching Integer Overflows in C指出了比CERT讨论的解决方案更通用的解决方案（在处理类型方面更为通用），即使它需要一些GCC扩展（我不知道它们有多广泛支持） .

    回复于
  • -2

    对于浮点数，我需要回答同样的问题，其中位掩码和移位看起来并不乐观 . 我确定的方法适用于有符号和无符号，整数和浮点数 . 即使没有更大的数据类型可用于中间计算，它仍然有效 . 对于所有这些类型而言，它并不是最有效的，但因为它确实适用于所有这些类型，所以值得使用 .

    签名溢出测试，加法和减法：

    • 获取表示类型MAXVALUE和MINVALUE的最大和最小可能值的常量 .

    • 计算并比较操作数的符号 .

    一个 . 如果任一值为零，则加法和减法都不会溢出 . 跳过剩余的测试 .

    湾如果符号相反，则添加不能溢出 . 跳过剩余的测试 .

    C . 如果符号相同，则减法不能溢出 . 跳过剩余的测试 .

    • 测试MAXVALUE的正溢出 .

    一个 . 如果两个符号均为正且MAXVALUE - A <B，则加法将溢出 .

    湾如果B的符号为负且MAXVALUE - A <-B，则减法将溢出 .

    • 测试MINVALUE的负溢出 .

    一个 . 如果两个符号都是负数且MINVALUE - A> B，那么加法将溢出 .

    湾如果A的符号为负且MINVALUE - A> B，则减法将溢出 .

    • 否则，没有溢出 .

    签名溢出测试，乘法和除法：

    • 获取表示类型MAXVALUE和MINVALUE的最大和最小可能值的常量 .

    • 计算并比较操作数的大小（绝对值） . （下面，假设A和B是这些大小，而不是签名的原件 . ）

    一个 . 如果任一值为零，则乘法不会溢出，并且除法将产生零或无穷大 .

    湾如果任一值为1，则乘法和除法不会溢出 .

    C . 如果一个操作数的幅度低于1而另一个操作数的幅度大于1，则乘法不能溢出 .

    d . 如果幅度都小于1，则除法不能溢出 .

    • 测试MAXVALUE的正溢出 .

    一个 . 如果两个操作数大于1且MAXVALUE / A <B，则乘法将溢出 .

    湾如果B小于1且MAXVALUE * B <A，则除法将溢出 .

    • 否则，没有溢出 .

    注意：MINVALUE的最小溢出由3处理，因为我们采用了绝对值 . 但是，如果ABS（MINVALUE）> MAXVALUE，那么我们将会有一些罕见的误报 .

    下溢测试类似，但涉及EPSILON（最大正数大于零） .

    回复于
  • 6

    CERT开发了一种新方法，使用"as-if"无限范围（AIR）整数模型检测和报告有符号整数溢出，无符号整数包装和整数截断 . CERT发布了描述该模型的technical report，并基于GCC 4.4.0和GCC 4.5.0生成了一个工作原型 .

    AIR整数模型生成的值等于使用无限范围整数获得的值，或者导致运行时约束违规 . 与以前的整数模型不同，AIR整数不需要精确的陷阱，因此不会破坏或抑制大多数现有的优化 .

    回复于
  • 22

    内联汇编允许您直接检查溢出位 . 如果你打算使用C，你真的应该学习装配 .

    回复于
  • 15

    用双精度计算结果 . 他们有15位有效数字 . 你的要求在c的108上有一个硬上限 - 它最多可以有8位数 . 因此，如果它在范围内，结果将是精确的，否则它将不会溢出 .

    回复于
  • 22

    虽然已经有两年了，但我觉得我还可以添加我的penithworth，以便以极快的速度检测溢出，至少可以添加，这可能会带来乘法，除法和幂

    这个想法正是因为处理器只是让值回绕到零并且C / C要从任何特定的处理器中抽象出来，你可以：

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

    这两者都确保如果一个操作数为零而一个操作数不为，则溢出不会错误地检测到，并且明显快于之前建议的许多NOT / XOR / AND /测试操作 .

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

    uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < x; // Alternatively "value < y" should also work
    回复于
  • -1

    我看到很多人都回答了关于溢出的问题，但我想解决他原来的问题 . 他说问题是要找到ab = c这样所有数字都可以使用而不重复 . 好吧，'s not what he asked in this post, but I'仍然认为有必要研究问题的上限并得出结论他永远不需要计算或检测到溢出（注意：我不精通数学，所以我一步一步地做了，但最终的结果很简单，这可能有一个简单的公式） .

    重点是问题所需的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（非平凡）

    现在我们只需要表明没有其他解决方案是可能的，只有排列是有效的（然后打印它们的代码是微不足道的） . 我们回到上限 . 实际上，上限是c≤98.765.432 . 它是上限，因为它是8位数的最大数字（总共10位数，每个a和b为1） . 这个上限仅适用于c，因为a和b的界限必须低得多，因为我们可以计算出指数增长，b从2到上限变化：

    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)
    回复于
  • -2
    #include <stdio.h>
#include <stdlib.h>

#define MAX 100 

int mltovf(int a, int b)
{
    if (a && b) return abs(a) > MAX/abs(b);
    else return 0;
}

main()
{
    int a, b;

    for (a = 0; a <= MAX; a++)
        for (b = 0; b < MAX; b++) {

        if (mltovf(a, b) != (a*b > MAX)) 
            printf("Bad calculation: a: %d b: %d\n", a, b);

    }
}
    回复于
  • 29

    Clang 3.4+和GCC 5+提供已检查算术内置函数 . 它们为这个问题提供了一个非常快速的解决方案，特别是与比特测试安全检查相比 .

    对于OP问题中的例子，它可以这样工作：

    unsigned long b, c, c_test;
if (__builtin_umull_overflow(b, c, &c_test))
{
    // returned non-zero: there has been an overflow
}
else
{
    // return zero: there hasn't been an overflow
}

    如果发生溢出，Clang文档没有指定 c_test 是否包含溢出的结果，但是GCC文档说它确实存在溢出 . 鉴于这两者似乎是相容的，可以安全地假设这也是Clang的工作方式 .

    对于int大小，长大小和长long大小，每个算术运算都有 __builtin 可以溢出（加法，减法，乘法），有符号和无符号变量 . 名称的语法是 __builtin_[us](operation)(l?l?)_overflow ：

    • u 表示未签名或 s 表示已签名;

    • 操作是 add ， sub 或 mul 之一;

    • no l 后缀表示操作数为 int s;一个 l 表示 long ;两个 l s的意思 long long .

    因此，对于已检查的有符号长整数，它将是 __builtin_saddl_overflow . 完整列表可在Clang documentation page上找到 .

    GCC 5和Clang 3.8还提供了通用内置函数，它们无需指定值的类型即可工作： __builtin_add_overflow ， __builtin_sub_overflow 和 __builtin_mul_overflow . 这些也适用于小于 int 的类型 .

    内置版本降低到平台的最佳状态 . 在x86上，它们检查进位，溢出和符号标志 .

    Visual Studio 's cl.exe doesn' t具有直接等价物 . 对于无符号加法和减法，包括 <intrin.h> 将允许您使用 addcarry_uNN 和 subborrow_uNN （其中NN是位数，如 addcarry_u8 或 subborrow_u64 ） . 他们的签名有点迟钝：

    unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum);
unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff);

    c_in / b_in 是输入的进位/借位标志，返回值是输出的进位/借位 . 它似乎没有签名操作或乘法的等价物 .

    否则，Clang for Windows现在可以投入 生产环境 （对Chrome来说已经足够了），所以这也是一个选择 .

    回复于

相关问题