9

I'm trying to detect the overflow when adding a signed offset to an unsigned position

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

How can I check whether the result is overflow or underflow?

I have thought of an ugly way but not sure of its correctness.

  • underflow: offset < 0 && position + offset >= position
  • overflow: offset > 0 && position + offset <= position

And I'm also wondering if there's a more elegant way to do it.

Update:

What's the best solution if offset is long?

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

3 に答える 3

1

あなたのテストは正しいです。私は今のところ、よりエレガントな方法を見ていません。おそらくそうではありません。

条件が正しい理由: 算術オンuint32_tは算術モジュロ 2^32 です。int32_tからへの変換uint32_tは通常、ビットパターンの再解釈です (いずれにせよ、@caf が指摘したように、ここでは 2^32 を法とするリダクションであるため、確実に機能します)。positionとoffsetを任意精度の整数と見なします。の場合にのみ、オーバーフローが発生し
position + offset >= 2^32ます。しかしoffset < 2^31、ので、これは、モジュロ 2^32 に還元される次の値position + offset < position + 2^31よりも小さいので、次のようになります。一方、 と の場合、明らかにオーバーフローが発生しています。アンダーフローは、数学的な整数である場合にのみ発生します。以来、同様の推論は、 の場合にのみアンダーフローが発生したことを示しています。position + 2^32positionuint32_tposition + offset < positionoffset > 0position + offset < positionposition + offset < 0offset >= -2^31offset < 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 定数が符号なしの型であることを保証するためのものです (サフィックスのない 16 進定数は、値と、コンパイラが int、long、および long long を定義する方法に応じて、符号付きまたは符号なしにすることができます) したがって、 < の左側の式は無署名。必要ないかもしれませんが、そうでないかどうかを判断するのに少し疲れています。確かに痛くないです。

(uint32) キャストは、私たちが愚かなことをしていると考えるかもしれないコンパイラを黙らせるためのものです (signed と unsigned の比較)。

UPDATE : int32 に 2 の補数表現があり、オフセット = -0x80000000 の場合、式-offsetは実装定義のシグナルを発生させたり、C 標準ごとに未定義の動作を引き起こす可能性さえあります (セクション6.3.1.3 Signed and unsigned integersと7.20.6.1 The abs, labs and llabs functionsほとんどのプラットフォームでは、CPU で例外/割り込み/トラップ/イベントを発生させない単純な命令 (または少数) として否定が実装されており、追加のコードを生成する価値がほとんどないため、実際にはこれは発生しません。特に整数は 2 の補数コードで表され、-0x80000000 の絶対値はとにかく 0x80000000 であるため、このエッジ ケースを確認してください (絶対値の計算など)。CPU は符号付き整数をあまり気にせず、同じ加算と減算の命令を両方に使用します (これは 2 の補数の利点です)。整数オーバーフローはほとんど気にしません。生活。それを認識してください。

Microsoft のSafeInt for C++ ( Code、Intro、On MSDN、Video ) およびIntSafe for C ( Intro + Code、On MSDN )でこれらがどのように実装されているかを確認してください。

于 2011-11-03T11:03:13.180 に答える