剣指offerの数値の整数次方C++解法

剣指offerの数値の整数次方C++解法
doubleタイプの浮動小数点数baseとintタイプの整数exponentを指定します.baseのexponent次数を求めます.
高速べき乗ab、素朴なアルゴリズム、すなわちa連乗b回の時間複雑度はO(b)すなわちO(n)であり、高速べき乗はO(logn)を行うことができ、原理は以下の通りである:bをバイナリに分解し、このバイナリ数i位の重みは2 i-1であり、例えばb=11の場合、そのバイナリは1011であり、a 11=a^(20+21+23)=a 1*a 2*a 8であるため、11回計算されたが、現在は3回しか計算されていない.この3つはビット演算を用いて高速計算を行うことができる.ビット演算は、1.バイナリビット取り操作:number&1はnumberバイナリの最下位ビットを取ります.2.パリティの判断:number&1=0は偶数、number&1=1は奇.

class Solution {
public:
    double Power(double base, int exponent) {
        int p = abs(exponent);
        double ans = 1.0; //  ans     
        while(p){
            if(p&1)
                ans *= base;
            base*=base;
            p>>=1;
        }
        return exponent<0? 1/ans:ans; // exponent   ，     exponent         
    }
};

バイナリ指数exponentについては、右に移動するたびに末尾が1であるかどうかをチェックし、1であればansをansに現在のbaseを乗じて更新し、exponentバイナリ数の各ビットはbaseに対応し、base*=baseの目的は累乗され、ansにいつでも貢献できるようにします.例:

exponentが1の場合、バイナリは1つしかありません.この場合、ansは初期値1.0で、baseは元のbaseです.すなわち、ans=ans*base=1.0*base=baseで、baseは一度にbase 2に乗算され、exponentは1ビット右に移動して0になり、ループが終了します.この場合、ans=baseです.

exponentが2である場合、バイナリが10であり、現在の末尾がif条件を満たしていないため、baseは一度自乗してbase 2になり、次に右にシフトしてif条件を満たすと、ansは初期値1.0、baseはbase 2、ans=1.0*base 2=base 2となる.

すなわち、指数bについては、そのバイナリがnビット(先頭の0を除く)であると仮定する.nビット目がa 1 n−1ビットに対応してa 2 n−2ビットに対応してa 4が…iビット目が1である場合、その対応するa 2^(n−i)を前ステップの積に累乗し、exponentが0で終わるまでループし、結果を返す.