快速幂

所谓快速幂，理解其意思就是快速的求出一个数的指数。

其时间复杂度为 O(log?N)， 与朴素的O(N)（普通的求法）相比效率有了极大的提高。

该二进制数第i位的权为

因此，我们将a11转化为算

快速幂可以用位运算这个强大的工具实现


          功能函数使用

bshr1{就是去掉b的二进制最末位}

以下是几种方法的比较：

代码：

#include <iostream>
#include <cstdio>
using namespace std;

//常规的求幂方法
int pow1(int a, int b)
{
        int r = 1;
        while(b--)
            r *= a;
        return r;
}

//二分幂求幂方法
int pow2(int a, int b)
{
    int r = 1, base = a;
    while(b != 0)
    {
            if(b % 2)
                    r *= base;
            base *= base;
            b /= 2;
    }
    return r;
}


//快速幂方法（位操作）
int pow3(int a, int b)
{
    int r = 1, base = a;
    while(b != 0)
    {
            if(b & 1)
                    r *= base;
            base *= base;
            b >>= 1;
    }
    return r;
}


//快速求幂(位运算，与pow3函数的实际行为相同， 但是看起来复杂)
int pow4(int x, int n)
{
        if(n == 0)
                return 1;
        else
        {
            while((n & 1) == 0)
            {
                n >>= 1;
                x *= x;
            }
        }
        int result = x;
        n >>= 1;
        while(n != 0)
        {
                x *= x;
                if((n & 1) != 0)
                        result *= x;
                n >>= 1;
        }
        return result;
}
int main()
{
    cout<<pow1(2, 10)<<endl;
    cout<<pow2(2, 10)<<endl;
    cout<<pow3(2, 10)<<endl;
    cout<<pow4(2, 10)<<endl;
    return 0;
}

快速幂

原文：http://blog.csdn.net/u012965373/article/details/45147597