如何检测无符号整数乘法溢出？

Question

我在C++编写一个程序来找到所有的解决方案一^b = c ^,其中一个,b和c ^一起使用所有的数字0-9只出现一次.该方案在循环值一和b,并且在每次跑了数字计数程序一,b和一个^b以检查是否数字的条件感到满意.

然而,当可以产生伪解一个^b溢出整数限制.我最终使用以下代码检查:

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++中,签名 int溢出是未定义的行为,因此您必须在不实际导致它的情况下检测它.有关添加前的signed int overflow,请参阅在C/C++中检测带符号的溢出

Answer 1

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

对于有符号整数,一旦出现溢出,就会发生未定义的行为,并且您的程序可以执行任何操作(例如:渲染测试不确定). 

#include <limits.h>

int a = <something>;
int x = <something>;
a += x;              /* UB */
if (a < 0) {         /* Unreliable test */
  /* ... */
}

要创建符合要求的程序,您需要在生成溢出之前测试溢出.该方法也可以与无符号整数一起使用

// 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>;
// There may be a need to check for -1 for two's complement machines.
// If one number is -1 and another is INT_MIN, multiplying them we get abs(INT_MIN) which is 1 higher than INT_MAX
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */
// general case
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;

除法(除了INT_MIN和-1特殊情况)不存在去在可能性INT_MIN或INT_MAX.

Answer 2

有是一种方法来确定操作是否可能溢出,使用操作数的最显著一个位和一点点基本的二进制数学知识的位置.

另外,任何两个操作数将导致(最多)比最大操作数的最高一位多一位.例如:

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

它并不完美,但是在你做手术之前,这会让你知道任何两个数字是否会溢出.我不知道它是否比简单地以你建议的方式检查结果更快,因为highestOneBitPosition函数中的循环,但它可能(特别是如果你事先知道操作数中有多少位).

Answer 3

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
}

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

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

• u对于未签名或s对签名的 ;
• 操作是其中之一add,sub或mul;
• 没有l后缀意味着操作数是ints; 一个l手段long; 两个l意思是long long.

因此,对于已检查的带符号长整数,它将是__builtin_saddl_overflow.完整列表可以在Clang文档页面上找到.

GCC 5+和锵3.8+另外提供,如果没有指定值的类型工作的通用内建的:__builtin_add_overflow,__builtin_sub_overflow和__builtin_mul_overflow.这些也适用于小于的类型int.

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

Visual Studio的cl.exe没有直接的等价物.对于无符号加法和减法,包括<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来说已经足够了),所以这也是一个选择.

Answer 4

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

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

if ( b > ULONG_MAX / a ) // a * b would overflow

Answer 5

警告:GCC可以在编译时优化掉溢出检查-O2.-Wall在某些情况下,该选项会给您一个警告

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

但不是在这个例子中:

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

唯一安全的方法是在CERT文件中描述之前检查溢出,并且系统地使用这将是非常繁琐的.

编译与-fwrapv解决问题但禁用一些优化.

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

Answer 6

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

Answer 7

我看到很多人回答了关于溢出的问题,但我想解决他原来的问题.他说问题是要找到一个^b = c,这样所有数字都可以不重复使用.好吧,这不是他在这篇文章中提到的,但我仍然认为有必要研究问题的上限并得出结论他永远不需要计算或检测溢出(注意:我不熟练)在数学中所以我一步一步地做了这一点,但最终的结果是如此简单,以至于这可能有一个简单的公式).

重点是问题所需的a,b或c的上限是98.765.432.无论如何,首先将问题分解为琐碎和非平凡的部分:

• x ⁰ == 1(所有排列的9,8,7,6,5,4,3,2都是解决方案)
• x ¹ == x(无法解决)
• 0 ^b == 0(无法解决)
• 1 ^b == 1(无法解决)
• a ^b,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)

Answer 8

这是一个问题的"非便携式"解决方案.Intel x86和x64 CPU具有所谓的EFLAGS寄存器(http://en.wikipedia.org/wiki/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.此检查并不意味着任何进一步的计算,因此它应该非常快.

Answer 9

如果您的数据类型大于您要测试的数据类型(假设您执行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实现方式,确保params不会溢出,因为它们相乘以获得最终大小.

Answer 10

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

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

哦,它可以在C和C++中工作(因为你用两者标记了问题).

刚刚看了一下glibc手册.提到整数溢出陷阱(FPE_INTOVF_TRAP)作为其中的一部分SIGFPE.除了手册中讨厌的内容之外,这将是理想的:

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

真的有点遗憾.

Answer 11

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

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

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

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

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

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

Answer 12

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

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
}

Answer 13

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

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

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

编辑:

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

Answer 14

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

签名溢出测试,加法和减法:

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

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

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

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

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

3. 测试MAXVALUE的正溢出.

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

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

4. 测试MINVALUE的负溢出.

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

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

5. 否则,没有溢出.

签名溢出测试,乘法和除法:

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

2. 计算并比较操作数的大小(绝对值).(下面假设A和B是这些大小,而不是签名的原件.)

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

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

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

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

3. 测试MAXVALUE的正溢出.

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

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

4. 否则,没有溢出.

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

下溢测试类似,但涉及EPSILON(最大正数大于零).

Answer 15

CERT开发了一种新方法,使用"as-if"无限范围(AIR)整数模型检测和报告有符号整数溢出,无符号整数包装和整数截断.CERT发布了一份描述该模型的技术报告,并根据GCC 4.4.0和GCC 4.5.0制作了一个工作原型.

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

Answer 16

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

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

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

Answer 17

使用汇编程序的另一种解决方案是外部程序.这个例子用于在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

Answer 18

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

Answer 19

试试这个宏来测试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);
}