整数のラップアラウンドをCで

Question

私はかなりの時間からcでプログラミングしています。しかし、整数ラップアラウンドが発生するプログラムでは決して働きませんでした。整数が4バイト割り当てられている場合、整数の範囲は-2,147,483,648から2,147,483,647になります。私たちが限界を超えれば、それはただラップアラウンドします。

ラップアラウンドがどのように起こるかを調べるために、次のプログラムで作業していました。

#include <stdio.h> 

int main() { 
int n = 4, s = 2; 

for (int i = 0; i < n; ++i) 
{ 
    for (int j = 0; j < n; ++j) 
    { 
     for (int k = 0; k < n; ++k) 
     { 
      s = 2 * s + 1; 

     } 
    } 
} 
printf("%d\n", s); 
return 0; 
} 

私はgdbを使って変数sの値を調べていました。私は、30回目の最内ループを実行しているときにsの値が負になる、つまり-1073741825になることを発見しました。次に、次の反復では2147483647になり、32回目の反復では-1になります。

それでは-1のままです。私の疑問は、値が-1になった後にラップアラウンドが起こらなかった理由です。私はバイナリでのsの値がすべて1であるか、または16進数でFFFFFFFFであることを知っています。そして、それは永遠に変わることはありません（内部的に更新していますが、最後の32ビットしか見ることができないので-1です）。しかし、このラップアラウンドは今度は画像に入っていませんか？コンパイラに依存していますか？あるいは、gccはラップアラウンドを1回だけ許可しますか？ どんな種類の助けにも感謝します。ありがとう

Answer 1

厳密に言えば、符号付き整数のオーバーフローはundefined behaviorです。しかし実際には、ほとんどの実装で整数の2の補数表現が使用され、折り返しが記述方法に影響します。

これを念頭に置いて、ここで何が起こるかを見てみましょう。

ループが進むにつれて、最終的にsの値は1610612735になります。これまでは何も異常はありません。今度は2を掛けて1を加えます。この時点で、結果はオーバーフローします。これらの数値の16進表現を見てみましょう。

1610612735d = 0101 1111 1111 1111 1111 1111 1111 1111 b = 0x5FFFFFFF 
0x5FFFFFFF * 2 = 0xBFFFFFFE 
0xBFFFFFFE + 1 = 0xBFFFFFFF 
0xBFFFFFFE = 1011 1111 1111 1111 1111 1111 1111 1111 b = -1073741825d 

バイナリ観点から、2を乗算する。この操作は、あなたの負の値を与え、符号ビットに値を移動する1の左シフトと等価です。

次の操作では、2を掛けてもう一度オーバーフローします。この時間は、乗算は符号変化が再びそこに1が以前あったので、符号ビットに0をシフト：

0xBFFFFFFF * 2 = 0x7FFFFFFE 
0x7FFFFFFE + 1 = 0x7FFFFFFF 
0x7FFFFFFF = 0111 1111 1111 1111 1111 1111 1111 1111 b = 2147483647 

次の反復にも溢れて：

0x7FFFFFFF * 2 = 0xFFFFFFFE 
0x7FFFFFFE + 1 = 0xFFFFFFFF 
0xFFFFFFFF = 1111 1111 1111 1111 1111 1111 1111 1111 b = -1 

は、今、私たちは持っている-1。

-1 * 2 = -2 
-2 + 1 = -1 

ここ進でも同じことだ：あなたが倍増-1と1を追加すると、あなたは再び-1与え見ることができるので、なぜそれそれだと

0xFFFFFFFF * 2 = 0xFFFFFFFE 
0xFFFFFFFE + 1 = 0xFFFFFFFF 

ここからが、オーバーフローはありません繰り返す。これはまた、2の乗算と1の左シフトが一致しています。