java - java(JDK 1.7)の効率的なベキ乗法

Question

プロジェクトに必要な Java で power(base,exponent) の最適なメソッドを作成したいのですが、基数と指数の両方の型が int で指数 <= 10^9 です。ただし、これは Java で行う必要がありますか? bitshift を使用できることを知っていますが、それ自体は java.Kindly で実装を提案します。

Answer 1

java.lang.BigIntegerクラスを使用するだけです。これには、かなり効率的な方法で必要なことを正確に実行するpow()メソッドがあります。

Answer 2

指数は int であるため、数値の 2 進数表現は既に得られています (コンピューターはそうしています)。したがって、基数、指数、および計算に使用する一時的な整数と、解に使用するもう 1 つの整数の 3 つの整数が必要です。あなたはこれから始めます：

unsigned int base;//you manage input for this and exponent like you wish, probably passed in as parameters
unsigned int exponent;
unsigned int temp = base;
unsigned int answer = 1;
while (exponent!=0){
    if (exponent%2 == 1){
        answer *= temp;
    }
    exponent>>1;
        temp<<1;
}

このアルゴリズムを試して、その仕組みを教えてください。while ルックは、指数の最大ビット長 (つまり 32 回) で実行されます。このコードは大きな数や負の数を処理しませんが、これが必要かどうかはわかりません。