C二乗法による累乗の実装

Question

私はCで "累乗法による累乗"アルゴリズムを実装しようとしましたが、私のプログラムは奇妙な動作をします。私は関数を呼び出す場合

long long fast_power_1(long long base, long long power){ 
    long long result = 1; 
    while (power > 0) 
    { 
     if (power % 2 == 0) 
     { 
      power = power/2; 
      base = base * base; 
     } 
     else 
     { 
      power = power - 1; 
      result = (result*base); 
      power = power/2; 
      base = (base * base); 
     } 
    } 
return result;} 

：まず、ここに小さなコードスニペットです

printf("%d\n",fast_power_1(2,100)); 

私は出力が976371285のようなものであることを期待していますが、結果は0であると私はしないでください理由をよく理解している。

Answer 1

long longは、%lld形式指定子を使用して印刷する必要があります。それ以外の場合は、未定義動作です。 powerの大きな値の場合にもオーバーフローが発生しています。これは、長い長さのカントが2^100（今のところ32または64ビットシステムの場合、128ビットシステムの場合はもちろん可能です）を保持しているためです。

今のところあなたのコードで指数の値が大きすぎず、printf("%lld",..)を使用すると有効な結果が得られます。

おそらく、モジュラ演算を使用したいと思うかもしれません。 （一般的な要件では、いくつかの大きなプライムのモジュロのように、つまり10^9+7）。