9

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

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

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

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

  • 下溢：offset < 0 && position + offset >= position
  • 溢出：offset > 0 && position + offset <= position

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

更新：

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

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

3 回答 3

1

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

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

于 2011-11-03T09:28:44.303 回答
1

将 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;
}
于 2011-11-03T11:00:08.043 回答
0

以下是您的操作方法：

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 的补码表示且偏移量 = -0x80000000，-offset则允许该表达式引发实现定义的信号，甚至可能根据 C 标准导致未定义的行为（请参阅部分6.3.1.3 Signed and unsigned integers和7.20.6.1 The abs, labs and llabs functionsC99 的），但实际上这从未发生过，因为在大多数平台上，否定是作为一个简单指令（或几个）实现的，不会在 CPU 中引发任何异常/中断/陷阱/事件，并且生成额外代码的价值很小检查这种边缘情况，特别是因为整数用 2 的补码表示，并且 -0x80000000 的绝对值无论如何都是 0x80000000，这可能很方便（例如，用于绝对值计算）。CPU 不太关心有符号整数，甚至对两者都使用相同的加法和减法指令（这是 2 的补码的好处），它很少关心整数溢出，因为它们在软件中经常发生并且是一种生活。意识到这一点，但不要出汗。

请查看 Microsoft 的SafeInt for C++（代码、介绍、On MSDN、视频）和IntSafe for C（介绍 + 代码、On MSDN）如何实现这些。

于 2011-11-03T11:03:13.180 回答