当前位置： 文江博客话题详情

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

发布于 2024-11-15 20:30:52 字数 825 浏览 4 评论 0原文

我正在用 C++ 编写一个程序来查找 ab = c 的所有解，其中 a 、b 和 c 一起使用所有数字 0-9 一次。该程序循环遍历 a 和 b 的值，并且每次对 a、b 运行数字计数例程em> 和 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++ 访问。

请注意，signed int 溢出是 C 和 C++ 中未定义的行为，因此您必须检测它而不是实际导致它。对于加法之前的有符号 int 溢出，请参阅检测 C/C++ 中的有符号溢出 。

原文

I was writing a program in C++ to find all solutions of ab = c, where a, b and c together use all the digits 0-9 exactly once. The program looped over values of a and b, and it ran a digit-counting routine each time on a, b and ab to check if the digits condition was satisfied.

However, spurious solutions can be generated when ab overflows the integer limit. I ended up checking for this using code like:

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

Is there a better way of testing for overflow? I know that some chips have an internal flag that is set when overflow occurs, but I've never seen it accessed through C or C++.

Beware that signed int overflow is undefined behaviour in C and C++, and thus you have to detect it without actually causing it. For signed int overflow before addition, see Detecting signed overflow in C/C++.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（30）

清风疏影 2024-11-22 20:30:53

这是该问题的“不可移植”解决方案。 Intel x86 和 x64 CPU 有所谓的 EFLAGS-register，由每次整数算术运算后的处理器。我将在这里跳过详细描述。相关标志是“溢出”标志（掩码 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。此检查并不意味着任何进一步的计算，因此它应该相当快。

Here is a "non-portable" solution to the question. The Intel x86 and x64 CPUs have the so-called EFLAGS-register, which is filled in by the processor after each integer arithmetic operation. I will skip a detailed description here. The relevant flags are the "Overflow" Flag (mask 0x800) and the "Carry" Flag (mask 0x1). To interpret them correctly, one should consider if the operands are of signed or unsigned type.

Here is a practical way to check the flags from C/C++. The following code will work on Visual Studio 2005 or newer (both 32 and 64 bit), as well as on GNU C/C++ 64 bit.

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

If the operands were multiplied without overflow, you would get a return value of 0 from query_intel_eflags(0x801), i.e. neither the carry nor the overflow flags are set. In the provided example code of main(), an overflow occurs and the both flags are set to 1. This check does not imply any further calculations, so it should be quite fast.

回复 原文
dawn曙光 2024-11-22 20:30:53

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

它基于此页面上解释的概念：https://www.cs.umd.edu/~meesh/cmsc311/clin-cmsc311/Lectures/lecture22/overflow.pdf
(https://web.archive.org/web/20170121033813/http://www.cs.umd.edu:80/class/spring2003/cmsc311/Notes/Comb/overflow.html 回程机)

对于 32 位示例，0xFF 变为 0xFFFFFFFF 并且0x80 变为 0x80000000，最后 uint16_t 变为 uint64_t。

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

If you have a datatype which is bigger than the one you want to test (say you do a 32-bit add and you have a 64-bit type), then this will detect if an overflow occurred. My example is for an 8-bit add. But it can be scaled up.

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

It is based on the concepts explained on this page: https://www.cs.umd.edu/~meesh/cmsc311/clin-cmsc311/Lectures/lecture22/overflow.pdf
(https://web.archive.org/web/20170121033813/http://www.cs.umd.edu:80/class/spring2003/cmsc311/Notes/Comb/overflow.html wayback machine)

For a 32-bit example, 0xFF becomes 0xFFFFFFFF and 0x80 becomes 0x80000000 and finally uint16_t becomes a uint64_t.

NOTE: this catches integer addition/subtraction overflows, and I realized that your question involves multiplication. In which case, division is likely the best approach. This is commonly a way that calloc implementations make sure that the parameters don't overflow as they are multiplied to get the final size.

回复 原文
白色秋天 2024-11-22 20:30:53

最简单的方法是将 unsigned long 转换为 unsigned long long，进行乘法，然后将结果与 0x100000000LL 进行比较。

您可能会发现这比在示例中进行除法更有效。

哦，它适用于 C 和 C++（因为您已经用两者标记了问题）。

刚刚查看了 glibc 手册。其中提到了作为 SIGFPE 一部分的整数溢出陷阱 (FPE_INTOVF_TRAP)。除了手册中令人讨厌的部分之外，这将是理想的：

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

确实有点可惜。

The simplest way is to convert your unsigned longs into unsigned long longs, do your multiplication, and compare the result to 0x100000000LL.

You'll probably find that this is more efficient than doing the division as you've done in your example.

Oh, and it'll work in both C and C++ (as you've tagged the question with both).

Just been taking a look at the glibc manual. There's a mention of an integer overflow trap (FPE_INTOVF_TRAP) as part of SIGFPE. That would be ideal, apart from the nasty bits in the manual:

FPE_INTOVF_TRAP
Integer overflow (impossible in a C program unless you enable overflow trapping in a hardware-specific fashion).

A bit of a shame really.

回复 原文
盛装女皇 2024-11-22 20:30:53

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

某些编译器允许您在代码中插入陷阱指令。在 GCC 上，选项是 -ftrapv。

您可以做的唯一可移植且独立于编译器的事情就是自行检查溢出。就像您在示例中所做的那样。

然而，-ftrapv 似乎在使用最新 GCC 的 x86 上没有任何作用。我猜这是旧版本的遗留物或特定于其他架构的。我原以为编译器会在每次添加后插入一个 INTO 操作码。不幸的是它不这样做。

You can't access the overflow flag from C/C++.

Some compilers allow you to insert trap instructions into the code. On GCC the option is -ftrapv.

The only portable and compiler independent thing you can do is to check for overflows on your own. Just like you did in your example.

However, -ftrapv seems to do nothing on x86 using the latest GCC. I guess it's a leftover from an old version or specific to some other architecture. I had expected the compiler to insert an INTO opcode after each addition. Unfortunately it does not do this.

回复 原文
[旋木] 2024-11-22 20:30:53

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

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
}

For unsigned integers, just check that the result is smaller than one of the arguments:

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

For signed integers you can check the signs of the arguments and of the result.

Integers of different signs can't overflow, and integers of the same sign overflow only if the result is of a different sign:

signed int r, a, b, s;
r = a + b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
    // Overflow
}
回复 原文
憧憬巴黎街头的黎明 2024-11-22 20:30:53

我需要针对浮点数回答同样的问题，其中位掩码和移位看起来不太有希望。我选择的方法适用于有符号和无符号、整数和浮点数。即使没有更大的数据类型可以升级为中间计算，它也可以工作。对于所有这些类型来说，它并不是最有效的，但因为它确实适用于所有类型，所以值得使用。

有符号溢出测试，加法和减法：

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

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

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

    b.如果符号相反，则加法不会溢出。跳过剩余的测试。

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

  3. 测试 MAXVALUE 是否正溢出。

    a.如果两个符号均为正且 MAXVALUE - A < B、那么加法就会溢出。

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

  4. 测试 MINVALUE 的负溢出。

    a.如果两个符号均为负且 MINVALUE - A > B、那么加法就会溢出。

    b.如果 A 的符号为负且 MINVALUE - A > B、则减法会溢出。

  5. 否则，不会溢出。

有符号溢出测试、乘法和除法：

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

  2. 计算操作数的大小（绝对值）并将其与 1 进行比较。 （下面假设 A 和 B 是这些量级，而不是签名的原件。）

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

    b.如果任一值为 1，乘法和除法就不会溢出。

    c.如果一个操作数的大小小于 1，而另一个操作数的大小大于 1，则乘法不会溢出。

    d.如果大小都小于 1，则除法不会溢出。

  3. 测试 MAXVALUE 是否正溢出。

    a.如果两个操作数都大于 1 并且 MAXVALUE / A < B、则乘法会溢出。

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

  4. 否则，不会溢出。

注意：MINVALUE 的最小溢出由 3 处理，因为我们采用绝对值。然而，如果
ABS(最小值)> MAXVALUE，那么我们将会出现一些罕见的误报。

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

I needed to answer this same question for floating point numbers, where bit masking and shifting does not look promising. The approach I settled on works for signed and unsigned, integer and floating point numbers. It works even if there is no larger data type to promote to for intermediate calculations. It is not the most efficient for all of these types, but because it does work for all of them, it is worth using.

Signed Overflow test, Addition and Subtraction:

  1. Obtain the constants that represent the largest and smallest possible values for the type,
    MAXVALUE and MINVALUE.

  2. 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.

  3. 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.

  4. 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.

  5. Otherwise, no overflow.

Signed Overflow test, Multiplication and Division:

  1. Obtain the constants that represent the largest and smallest possible values for the type,
    MAXVALUE and MINVALUE.

  2. 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.

  3. 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.

  4. Otherwise, no overflow.

Note: Minimum overflow of MINVALUE is handled by 3, because we took absolute values. However, if
ABS(MINVALUE) > MAXVALUE, then we will have some rare false positives.

The tests for underflow are similar, but involve EPSILON (the smallest positive number greater than zero).

回复 原文
ㄖ落Θ余辉 2024-11-22 20:30:53

另一个有趣的工具是IOC：C/C++ 整数溢出检查器。

这是一个经过修补的 Clang 编译器，它在编译时添加了对代码的检查。

您会得到如下所示的输出：

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

Another interesting tool is IOC: An Integer Overflow Checker for C/C++.

This is a patched Clang compiler, which adds checks to the code at compile time.

You get output looking like this:

CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1
回复 原文
℡Ms空城旧梦 2024-11-22 20:30:53

CERT 开发了一种新方法，使用“as-if”无限范围 (AIR) 整数模型来检测和报告有符号整数溢出、无符号整数包装和整数截断。 CERT 发布了一份描述该模型的技术报告，并制作了一份工作报告基于GCC 4.4.0和GCC 4.5.0的原型。

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

CERT has developed a new approach to detecting and reporting signed integer overflow, unsigned integer wrapping, and integer truncation using the "as-if" infinitely ranged (AIR) integer model. CERT has published a technical report describing the model and produced a working prototype based on GCC 4.4.0 and GCC 4.5.0.

The AIR integer model either produces a value equivalent to one that would have been obtained using infinitely ranged integers or results in a runtime constraint violation. Unlike previous integer models, AIR integers do not require precise traps, and consequently do not break or inhibit most existing optimizations.

回复 原文
海风掠过北极光 2024-11-22 20:30:53

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

此过程将两个无符号整数参数（32 位）相乘（根据 amd64 的规范（部分3.2.3 参数传递）。

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

（我的代码中的 edi 和 esi 寄存器））并返回结果，如果发生溢出。

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 中，将其添加到 LIBS 中.pro 文件。

Another variant of a solution, using assembly language, is an external procedure. This example for unsigned integer multiplication using g++ and fasm under Linux x64.

This procedure multiplies two unsigned integer arguments (32 bits) (according to specification for amd64 (section 3.2.3 Parameter Passing).

If the class is INTEGER, the next available register of the sequence %rdi, %rsi, %rdx, %rcx, %r8, and %r9 is used

(edi and esi registers in my code)) and returns the result or 0 if an overflow has occured.

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

Test:

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

Link the program with the asm object file. In my case, in Qt Creator, add it to LIBS in a .pro file.

回复 原文
锦爱 2024-11-22 20:30:53

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

Calculate the results with doubles. They have 15 significant digits. Your requirement has a hard upper bound on c of 108 — it can have at most 8 digits. Hence, the result will be precise if it's in range, and it will not overflow otherwise.

回复 原文
起风了 2024-11-22 20:30:53

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

Try this macro to test the overflow bit of 32-bit machines (adapted the solution of Angel Sinigersky)

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

I defined it as a macro because otherwise the overflow bit would have been overwritten.

Subsequent is a little application with the code segement above:

#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);
}
回复 原文
岁月流歌 2024-11-22 20:30:53

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

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

查看 info as 和 info gcc。

You can't access the overflow flag from C/C++.

I don't agree with this. You could write some inline assembly language and use a jo (jump overflow) instruction assuming you are on x86 to trap the overflow. Of course, your code would no longer be portable to other architectures.

Look at info as and info gcc.

回复 原文
若有似无的小暗淡 2024-11-22 20:30:53

Catching Integer Overflows in C 指出了一种比 CERT 讨论的更通用的解决方案（它更一般就处理类型而言），即使它需要一些 GCC 扩展（我不知道它们的支持范围有多大）。

Catching Integer Overflows in C points out a solution more general than the one discussed by CERT (it is more general in term of handled types), even if it requires some GCC extensions (I don't know how widely supported they are).

回复 原文
孤云独去闲 2024-11-22 20:30:53

mozilla::CheckedInt为整数类型 T 提供溢出检查整数数学（使用 clang 和 gcc 上可用的编译器内在函数）。该代码位于 MPL 2.0 下，依赖于三个 (IntegerTypeTraits.h< /code>，Attributes.h 和 Compiler.h) 其他仅包含头文件的非标准库头加上 Mozilla 特定的 断言机制。如果导入代码，您可能想要替换断言机制。

mozilla::CheckedInt<T> provides overflow-checked integer math for integer type T (using compiler intrinsics on clang and gcc as available). The code is under MPL 2.0 and depends on three (IntegerTypeTraits.h, Attributes.h and Compiler.h) other header-only non-standard library headers plus Mozilla-specific assertion machinery. You probably want to replace the assertion machinery if you import the code.

回复 原文
孤独患者 2024-11-22 20:30:53

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 位。

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

The x86 instruction set includes an unsigned multiply instruction that stores the result to two registers. To use that instruction from C, one can write the following code in a 64-bit program (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;
}

For a 32-bit program, one needs to make the result 64 bit and parameters 32 bit.

An alternative is to use compiler-dependent intrinsic to check the flag register. GCC documentation for overflow intrinsic can be found from 6.56 Built-in Functions to Perform Arithmetic with Overflow Checking.

回复 原文
救赎№ 2024-11-22 20:30:53

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

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

To expand on Head Geek's answer, there is a faster way to do the 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 );
}

This uses machine-architecture safe, in that 64-bit and 32-bit unsigned integers will still work fine. Basically, I create a mask that will mask out all but the most significant bit. Then, I mask both integers, and if either of them do not have that bit set, then addition is safe.

This would be even faster if you pre-initialize the mask in some constructor, since it never changes.

回复 原文
轮廓§ 2024-11-22 20:30:53

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

A clean way to do it would be to override all operators (+ and * in particular) and check for an overflow before performing the operations.

回复 原文
抱着落日 2024-11-22 20:30:53

MSalter的答案是个好主意。

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

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

MSalter's answer is a good idea.

If the integer calculation is required (for precision), but floating point is available, you could do something like:

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
    }
}
回复 原文
抠脚大汉 2024-11-22 20:30:53

这取决于你用它做什么。
执行无符号长整型 (DWORD) 加法或乘法，最佳解决方案是使用 ULARGE_INTEGER。

ULARGE_INTEGER 是两个 DWORD 的结构。全部价值
可以在访问高位 DWORD 时作为“QuadPart”进行访问
作为“HighPart”，低位 DWORD 作为“LowPart”访问。

例如：

DWORD
My Addition(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)

    // Any overflow is stored in a.HighPart (up to 32 bits)

It depends what you use it for.
Performing unsigned long (DWORD) addition or multiplication, the best solution is to use ULARGE_INTEGER.

ULARGE_INTEGER is a structure of two DWORDs. The full value
can be accessed as "QuadPart" while the high DWORD is accessed
as "HighPart" and the low DWORD is accessed as "LowPart".

For example:

DWORD
My Addition(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)

    // Any overflow is stored in a.HighPart (up to 32 bits)
回复 原文
小情绪 2024-11-22 20:30:53

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

... /* 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;
}

To perform an unsigned multiplication without overflowing in a portable way the following can be used:

... /* 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;
}
回复 原文
清晰传感 2024-11-22 20:30:53
#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);

    }
}

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

    }
}
回复 原文
长不大的小祸害 2024-11-22 20:30:53

测试溢出的简单方法是通过检查当前值是否小于先前值来进行验证。例如，假设您有一个循环来打印 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 溢出标志的情况下获得的移植性差不多（这将需要内联汇编代码，从而使您的代码无论如何都不可跨实现移植）。

The simple way to test for overflow is to do validation by checking whether the current value is less than the previous value. For example, suppose you had a loop to print the powers of 2:

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

Adding overflow checking the way that I described results in this:

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

It works for unsigned values as well as both positive and negative signed values.

Of course, if you wanted to do something similar for decreasing values instead of increasing values, you would flip the <= sign to make it >=, assuming the behaviour of underflow is the same as the behaviour of overflow. In all honesty, that's about as portable as you'll get without access to a CPU's overflow flag (and that would require inline assembly code, making your code non-portable across implementations anyway).

回复 原文
说不完的你爱 2024-11-22 20:30:52

我发现您正在使用无符号整数。根据定义，在 C 中（我不知道 C++），无符号算术不会溢出...所以，至少对于 C，你的观点是没有意义的:)

对于有符号整数，一旦有已经溢出，未定义行为（UB）已经发生，并且您的程序可以执行任何操作（例如：渲染测试尚无定论）。

#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 (x != 0 && a > INT_MAX / x) // `a * x` would overflow
if (x != 0 && a < INT_MIN / x) // `a * x` would underflow

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

I see you're using unsigned integers. By definition, in C (I don't know about C++), unsigned arithmetic does not overflow ... so, at least for C, your point is moot :)

With signed integers, once there has been overflow, undefined behaviour (UB) has occurred and your program can do anything (for example: render tests inconclusive). 

#include <limits.h>

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

To create a conforming program, you need to test for overflow before generating said overflow. The method can be used with unsigned integers too:

// 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 (x != 0 && a > INT_MAX / x) // `a * x` would overflow
if (x != 0 && a < INT_MIN / x) // `a * x` would underflow

For division (except for the INT_MIN and -1 special case), there isn't any possibility of going over INT_MIN or INT_MAX.

回复 原文
心如狂蝶 2024-11-22 20:30:52

从 C23 开始，标准标头 提供了以下三个类似函数的宏：

bool ckd_add(type1 *result, type2 a, type3 b);
bool ckd_sub(type1 *result, type2 a, type3 b);
bool ckd_mul(type1 *result, type2 a, type3 b);

其中 type1、type2 和 type3 是任何整数类型。这些函数分别以任意精度对 a 和 b 进行加、减或乘，并将结果存储在 *result 中。如果type1无法准确表示结果，则该函数返回true（“计算已溢出”）。 （任意精度是一种错觉；计算速度非常快，自 20 世纪 90 年代初以来几乎所有可用的硬件都可以仅用一两条指令来完成。）

重写 OP 的示例：

unsigned long b, c, c_test;
// ...
if (ckd_mul(&c_test, c, b))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

c_test 包含在所有情况下可能溢出的乘法结果。

早在 C23 之前，GCC 5+ 和 Clang 3.8+ 就已构建-ins 的工作方式相同，只是结果指针最后传递而不是最先传递：__builtin_add_overflow、__builtin_sub_overflow 和__builtin_mul_overflow。这些也适用于小于 int 的类型。

unsigned long b, c, c_test;
// ...
if (__builtin_mul_overflow(c, b, &c_test))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

Clang 3.4+ 引入了具有固定类型的算术溢出内置函数，但是它们的灵活性要差得多，而 Clang 3.8 已经推出很长时间了。尽管有更方便的更新替代方案，但如果您需要使用此功能，请查找 __builtin_umull_overflow。

Visual Studio 的 cl.exe 没有直接等效项。对于无符号加法和减法，包含 将允许您使用 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 来说已经足够好了），所以这也可以是一个选择。

Starting with C23, the standard header <stdckdint.h> provides the following three function-like macros:

bool ckd_add(type1 *result, type2 a, type3 b);
bool ckd_sub(type1 *result, type2 a, type3 b);
bool ckd_mul(type1 *result, type2 a, type3 b);

where type1, type2 and type3 are any integer type. These functions respectively add, subtract or multiply a and b with arbitrary precision and store the result in *result. If the result cannot be represented exactly by type1, the function returns true ("calculation has overflowed"). (Arbitrary precision is an illusion; the calculations are very fast and almost all hardware available since the early 1990s can do it in just one or two instructions.)

Rewriting OP's example:

unsigned long b, c, c_test;
// ...
if (ckd_mul(&c_test, c, b))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

c_test contains the potentially-overflowed result of the multiplication in all cases.

Long before C23, GCC 5+ and Clang 3.8+ offer built-ins that work the same way, except that the result pointer is passed last instead of first: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow. These also work on types smaller than int.

unsigned long b, c, c_test;
// ...
if (__builtin_mul_overflow(c, b, &c_test))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

Clang 3.4+ introduced arithmetic-overflow builtins with fixed types, but they are much less flexible and Clang 3.8 has been available for a long time now. Look for __builtin_umull_overflow if you need to use this despite the more convenient newer alternative.

Visual Studio's cl.exe doesn't have direct equivalents. For unsigned additions and subtractions, including <intrin.h> will allow you to use addcarry_uNN and subborrow_uNN (where NN is the number of bits, like addcarry_u8 or subborrow_u64). Their signature is a bit obtuse:

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 is the carry/borrow flag on input, and the return value is the carry/borrow on output. It does not appear to have equivalents for signed operations or multiplications.

Otherwise, Clang for Windows is now production-ready (good enough for Chrome), so that could be an option, too.

回复 原文
剑心龙吟 2024-11-22 20:30:52

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

对于加法，任何两个操作数都会导致（至多）比最大操作数的最高一位多一位。例如：

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 函数中的循环，我不知道它是否比简单地按照您建议的方式检查结果更快，但它可能会（特别是如果您知道预先操作数）。

There is a way to determine whether an operation is likely to overflow, using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge.

For addition, any two operands will result in (at most) one bit more than the largest operand's highest one-bit. For example:

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

For multiplication, any two operands will result in (at most) the sum of the bits of the operands. For example:

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

Similarly, you can estimate the maximum size of the result of a to the power of b like this:

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

(Substitute the number of bits for your target integer, of course.)

I'm not sure of the fastest way to determine the position of the highest one-bit in a number, here's a brute-force method:

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

It's not perfect, but that'll give you a good idea whether any two numbers could overflow before you do the operation. I don't know whether it would be faster than simply checking the result the way you suggested, because of the loop in the highestOneBitPosition function, but it might (especially if you knew how many bits were in the operands beforehand).

回复 原文
厌倦 2024-11-22 20:30:52

某些编译器提供对 CPU 中整数溢出标志的访问，然后您可以对其进行测试，但这不是标准的。

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

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

Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn't standard.

You could also test for the possibility of overflow before you perform the multiplication:

if ( b > ULONG_MAX / a ) // a * b would overflow
回复 原文
荒人说梦 2024-11-22 20:30:52

警告：使用 -O2 编译时，GCC 可以优化溢出检查。
在某些情况下，选项 -Wall 会向您发出警告，

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

但在本示例中并非如此：

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

唯一安全的方法是在溢出发生之前检查溢出，如 CERT论文，系统地使用它会非常乏味。

使用 -fwrapv 编译可以解决问题，但会禁用一些优化。

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

Warning: GCC can optimize away an overflow check when compiling with -O2.
The option -Wall will give you a warning in some cases like

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

but not in this example:

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

The only safe way is to check for overflow before it occurs, as described in the CERT paper, and this would be incredibly tedious to use systematically.

Compiling with -fwrapv solves the problem, but disables some optimizations.

We desperately need a better solution. I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring. The present situation allows the compiler to optimize away an overflow check, which is unacceptable in my opinion.

回复 原文
云雾 2024-11-22 20:30:52

Clang 现在支持有符号和无符号整数的动态溢出检查。请参阅 -fsanitize=integer 开关。目前，它是唯一完全支持用于调试目的的动态溢出检查的 C++ 编译器。

Clang now supports dynamic overflow checks for both signed and unsigned integers. See the -fsanitize=integer switch. For now, it is the only C++ compiler with fully supported dynamic overflow checking for debug purposes.

回复 原文
天涯离梦残月幽梦 2024-11-22 20:30:52

这是一种非常快速的方法，可以检测至少加法的溢出，这可能会导致乘法、除法和断电。

这个想法是，正是因为处理器会让值回绕到零，并且 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

检测乘法溢出的更有效且更便宜的方法是：

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

Here is a really fast way to detect overflow for at least additions, which might give a lead for multiplication, division and power-of.

The idea is that exactly because the processor will just let the value wrap back to zero and that C/C++ is to abstracted from any specific processor, you can:

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

This both ensures that if one operand is zero and one isn't, then overflow won't be falsely detected and is significantly faster than a lot of NOT/XOR/AND/test operations as previously suggested.

As pointed out, this approach, although better than other more elaborate ways, is still optimisable. The following is a revision of the original code containing the optimisation:

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

A more efficient and cheap way to detect multiplication overflow is:

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;

This results in either UINT32_MAX on overflow, or the result of the multiplication. It is strictly undefined behaviour to allow the multiplication to proceed for signed integers in this case.

Of note, this uses the partial Karatsuba method multiplicative decomposition to compute the high 32 bits of the 64-bit multiplication to check if any of them should become set to know if the 32-bit multiplication overflows.

If using C++, you can turn this into a neat little lambda to compute overflow so the inner workings of the detector get hidden:

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};
回复 原文
安静 2024-11-22 20:30:52

我看到很多人回答了关于溢出的问题，但我想解决他原来的问题。他说问题是找到 ab=c 使得所有数字都被使用而不重复。好吧，这不是他在这篇文章中问的问题，但我仍然认为有必要研究问题的上限并得出结论，他永远不需要计算或检测溢出（注意：我不精通）在数学上，所以我一步一步地做了这个，但最终结果非常简单，这可能有一个简单的公式）。

要点是问题要求 a、b 或 c 的上限是 98.765.432。无论如何，首先将问题分为琐碎和非琐碎的部分：

  • x0 == 1 （9、8、7、6、5、4、3、2 的所有排列都是解决方案）
  • x 1 == x（无解）
  • 0b == 0（无解）
  • 1b == 1 (无解)
  • ab, a > 1、b＞ 1（不平凡）

现在我们只需要证明没有其他解决方案是可能的，并且只有排列是有效的（然后打印它们的代码是平凡的）。我们回到上限。实际上上限是 c ≤ 98.765.432。它是上限，因为它是 8 位数字的最大数字（a 和 b 总共 10 位数字减 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)

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).

The main point is that the upper bound that the problem requires for either a, b or c is 98.765.432. Anyway, starting by splitting the problem in the trivial and non trivial parts:

  • x0 == 1 (all permutations of 9, 8, 7, 6, 5, 4, 3, 2 are solutions)
  • x1 == x (no solution possible)
  • 0b == 0 (no solution possible)
  • 1b == 1 (no solution possible)
  • ab, a > 1, b > 1 (non trivial)

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

Notice, for example the last line: it says that 1.97^27 ~98M. So, for example, 1^27 == 1 and 2^27 == 134.217.728 and that's not a solution because it has 9 digits (2 > 1.97 so it's actually bigger than what should be tested). As it can be seen, the combinations available for testing a and b are really small. For b == 14, we need to try 2 and 3. For b == 3, we start at 2 and stop at 462. All the results are granted to be less than ~98M.

Now just test all the combinations above and look for the ones that do not repeat any digits:

    ['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)

None of them matches the problem (which can also be seen by the absence of '0', '1', ..., '9').

The example code that solves it follows. Also note that's written in Python, not because it needs arbitrary precision integers (the code doesn't calculate anything bigger than 98 million), but because we found out that the amount of tests is so small that we should use a high level language to make use of its built-in containers and libraries (also note: the code has 28 lines).

    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)
回复 原文
~没有更多了~

关于作者

热鲨

暂无简介

0 文章
0 评论
24 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

離殇

文章 0 评论 0

小姐丶请自重

文章 0 评论 0

Aik

文章 0 评论 0

国产ˉ祖宗

文章 0 评论 0

猥琐帝

文章 0 评论 0

半仙

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文