オーバーフローを繰り返したときの挙動

質問

#include <stdio.h>

int function(int x){
if(x==1) return 1;
else return x*function(x-1);
}

int main(){
int x;

x = function(50);

printf("%d\n",x);
}

50!を計算するプログラムを作成し、VC++とgccでそれぞれコンパイルして実行したところ結果は0と表示されました。
途中でオーバーフローしているのは分かるのですが、数回オーバーフローを繰り返した後にfunctionの戻り値が-2^31に収束し、最終的に0になります。
何故このような挙動をするのでしょうか？

回答No.1

kmee · ベストアンサー

階乗の性質と、二進数の性質を考えればわかります。

階乗は、1つ置きに偶数倍されます。つまり、2のn乗(n>=1の整数)倍になります。
1
1*2=2 : 2^1倍
2*3=6
6*4=24 : 2^2倍
...

2^n倍は、二進数では、左にn桁シフトするのと同じことになります
6 * 4=24 : 二進数では 110 を左に2桁シフト → 11000

十進数では、下が0の数に、どの整数を掛けても、下の桁は0にしかなりません。
20*1=20 : 一番下は0
20*123=2460 : 一番下は0
...
二進数でも同じで、下の桁が0なら、どんな整数を掛けても、0のままです。

この二つより、階乗では、どんどん下の0の桁が増えていきます。
(ちなみに、十進数でも、下の0の桁がどんどん増えていきます)

Cの整数演算では、オーバーフローを起すと、上位の溢れた値は無視されます。
上記のように、0が増えて、整数の幅を越えると、変数には0しか残らなくなります。
以降は 0 * i となり、0にしかなりません。

-2^31になるのは、下から繰り上がってきた1が、正負の符号を表わしているビットを1にしてしまっているからです。
具体的なことは「2の補数表現」を調べてください。
なお、unsigend int にすれば、負の値にはなりません。

お礼

なるほど、単にオーバーフローを繰り返したら不味いから途中で0になるのかと思ってましたが、階乗の性質だったんですね。
丁寧に解説していただきありがとうございました。

回答No.2

Ogre7077

階乗の計算結果を素因数分解をすると、2の乗数が多く含まれていることがわかります。

5! = 2^3 * 3^1 * 5^1
10! = 2^8 * 3^4 * 5^2 * 7^1
15! = 2^11 * 3^6 * 5^3 * 7^2 * 11 * 13

計算機が扱う数は基本的に2進数ですので、
2のn乗(2^n) は 左シフトn回(1 << n) と同義です。
左シフトされるということは、下位nビットは必ず0ということです。

50! を素因数分解すると因数 2 の乗数は 32 以上なので、
下位32ビットはすべて 0 であり、
それより上位ビットはオーバーフローなので切り捨てられるので、
最終的な答えは 0 となります。

お礼

回答ありがとうございました。