有符号数与无符号数相加时如何判断溢出

Question

我试图在将有符号偏移量添加到无符号位置时检测溢出

uint32 position;
int32 offset;  // it could be negative
uint32 position = position+offset;

如何检查结果是上溢还是下溢？

我想到了一个丑陋的方法，但不确定它的正确性。

• 下溢：偏移量< 0 &&位置+偏移>=位置
• 溢出：偏移> 0 && position + offset <=position

我也想知道是否有更优雅的方法来做到这一点。

更新：

如果偏移量很长，最好的解决方案是什么？

uint32 position;
long offset;  // it could be negative
uint32 position = position+offset;

Answer 1

您的测试是正确的。我现在没有看到更优雅的方式，也许没有。

为什么条件是正确的：uint32_t 上的算术是模 2^32 的算术。从 int32_t 到 uint32_t 的转换通常是位模式的重新解释（无论如何，正如 @caf 指出的那样，这里它是模 2^32 的减少，所以它肯定是作品）。将 position 和 offset 视为任意精度整数。溢出当且仅当
位置 + 偏移量 >= 2^32。但是 offset < 2^31，所以位置+偏移量position + 2^31，小于 position + 2^32，即减少到 position 模 2^32 的下一个值，因此 uint32_t，然后位置+偏移量位置。另一方面，如果 offset > 0 和 位置 + 偏移量 位置，显然发生了溢出。当且仅当位置 + 偏移量 时才会发生下溢。 0 作为数学整数。由于offset >= -2^31，类似的推理表明当且仅当offset <= -2^31 时才会发生下溢。 0 &&位置+偏移量>位置。

Answer 2

以下函数在将 int32_t 添加到 uint32_t 时检查上溢/下溢。它还包含一些测试用例作为正确性的证据。

#include <stdint.h>
#include <assert.h>

int is_overflow (uint32_t position, int32_t offset)
{
    if (offset > 0 && offset > UINT32_MAX - position) {
        // really we checked (offset + position > UINT32_MAX)
        // overflow
        return 1;
    }
    else if (offset < 0 && (uint32_t)offset <= UINT32_MAX - position) {
        // really we checked  (position + (uint32_t)offset <= UINT32_MAX)
        // the (uint32_t)offset maps negative offset to [2^31, UINT32_MAX]
        // underflow
        return -1;
    }

    // no over/underflow
    return 0;
}

uint32_t abs_of_negative_int32 (int32_t offset)
{
    assert(offset < 0);

    return ((UINT32_MAX - (uint32_t)offset) + 1);
}

int main (int argc, char *argv[])
{
    int r;

    r = is_overflow(0, 0);
    assert(r == 0);

    r = is_overflow(0, 1);
    assert(r == 0);

    r = is_overflow(0, INT32_MAX - 1);
    assert(r == 0);

    r = is_overflow(0, INT32_MAX);
    assert(r == 0);

    r = is_overflow(0, -1);
    assert(r == -1);

    r = is_overflow(0, INT32_MIN + 1);
    assert(r == -1);

    r = is_overflow(0, INT32_MIN);
    assert(r == -1);

    r = is_overflow(UINT32_MAX, 0);
    assert(r == 0);

    r = is_overflow(UINT32_MAX, 1);
    assert(r == 1);

    r = is_overflow(UINT32_MAX - 1, 1);
    assert(r == 0);

    r = is_overflow(UINT32_MAX - 1, 2);
    assert(r == 1);

    r = is_overflow(UINT32_MAX - 1, INT32_MAX);
    assert(r == 1);

    r = is_overflow(UINT32_MAX - INT32_MAX, INT32_MAX);
    assert(r == 0);

    r = is_overflow(UINT32_MAX - INT32_MAX + 1, INT32_MAX);
    assert(r == 1);

    r = is_overflow(abs_of_negative_int32(INT32_MIN), INT32_MIN);
    assert(r == 0);

    r = is_overflow(abs_of_negative_int32(INT32_MIN) - 1, INT32_MIN);
    assert(r == -1);

    return 0;
}

Answer 3

具体方法如下：

uint32 addui(uint32 position, int32 offset, int* overflow)
{
  *overflow = (((offset >= 0) && (0xFFFFFFFFu - position < (uint32)offset)) ||
               ((offset < 0) && (position < (uint32)-offset)));
  return position + offset;
}

u 后缀是为了确保 0xFFFFFFFF 常量是无符号类型（没有后缀的十六进制常量可以是有符号的或无符号的，具体取决于值以及编译器如何定义 int、long 和 long long），因此< 左侧的表达式是未签名的。可能不需要，但我有点厌倦弄清楚是否不需要。肯定不会痛。

(uint32) 强制转换是为了关闭编译器，因为编译器可能认为我们正在做一些愚蠢的事情（比较有符号与无符号）。

更新：如果 int32 具有 2 的补码表示形式且 offset = -0x80000000，则允许表达式 -offset 引发实现定义的信号，甚至可能导致未定义的行为C 标准（请参阅 6.3.1.3 有符号和无符号整数 和 7.20.6.1 abs、labs 和 llabs 函数 C99），但实际上这种情况永远不会发生，因为在大多数平台上，否定是作为一个简单的指令（或几个指令）实现的，不会在 CPU 中引发任何异常/中断/陷阱/事件，并且生成额外的代码没有什么价值检查这种边缘情况，特别是因为整数用 2 的补码表示，并且 -0x80000000 的绝对值无论如何都是 0x80000000，这可能很方便（例如对于绝对值计算）。 CPU 不太关心有符号整数，甚至对两者使用相同的加法和减法指令（这是 2 的补码的好处），并且很少关心整数溢出，因为它们在软件中经常发生，并且是一种生活。请注意这一点，但不要担心。

请了解这些是如何在 Microsoft 的 SafeInt for C++ 中实现的（代码，简介，在 MSDN 上，视频）和 C 版 IntSafe （简介 + 代码，在 MSDN 上）。