ある数のn次方のアルゴリズムを求めます(効率的です)

このアルゴリズムはある数のn次方を求める時間複雑度はlognしかなく,我々が普段使っているサイクル時間複雑度はo(n)である.

int power(int x,int n)
{
    int m=0;
    m=n;
    int t=1;
    while(m>0)
    {
        m/=2;
        t*=2;
    }
    m=n;
    int y=1;
    while(t>1)
    {
        t/=2;
        y*=y;

        if (m>=t)
        {
                y*=x;
                m-=t;
        }
    }
    return y;
}

げんり
一般的にはa(2 x+b)=a 2 x*a b
だからある
(b=0の場合):a 2 x+b=(ax)2;
(b=1の場合):a 2 x+b=(a x)2*a;
anに対して、まずnのバイナリ表現を書き出して、それではあります
an  = a (n1 n2 n3 n4 ..)(2) = …
左から右へは次の表のようになります(n=15の場合1111)
nのバイナリビット
1
1
1
1
累乗
a
a2 * a = a3
(a3)2 *a= a7
(a7)2 * a = a15