使用二分法求整数幂

引言

在实际应用中，求幂是一种常用的运算。
那么在求幂时，我们是不是经常这样写：

int power(int x,  int n)
{
    int result = 1;
    while (n--)
        result *= x;
    return result;
}

这种写法简单直观，但时间复杂度较高。

解决思路

为了降低时间开销，我们可以使用二分法。

举个例子：求 2 的 8 次幂。

设结果为 result

result = 2^8
设result1 = 2^4，很容易推出 result  =  result1*result1
设result2 = 2^2，同理，result1 = result2*result2
......

再举个例子,result3 = 2^7
那么 result3 = result1 * 2^3
2^3 = 2^2 *2^1

规律就出来了，我们可以开始写程序了。

&和&&的区别

这里用到了一些不太常用的 C 语言知识，可能会比较晦涩难懂。
稳妥起见，这里再复习一下 C 的知识

&–按位与

举个例子：
7 的二进制是 0111，1 的二进制是 0001；
7 & 1 即 0111 & 0001 = 0001（二进制）= 1（十进制）；
再举个例子：
11 & 6 即 1011 & 0110 = 0010 = 2；

&&–逻辑与

这个很简单：只要两个数都不为 0，结果就是 1。
10 && 1 = 1；
1 & 0 = 0；

<<，>> 位左移和位右移

依旧举例，将 8 向左移两位：
8 >> 2 即为 1000（二进制）左移两位，结果就是 10（二进制），化为十进制就是 2；
P.S.：n >>= 2 与 n = n>>2 结果相同。
但在运算速度和内存占用上比后者好一些，这里就不展开解释了。

核心代码

int power(int x, int n)
{
    if (n == 0)
        return 1;
    int result = 1;
    while (n != 0)
    {
        if ((n & 1) != 0)
            result *= x;
        x *= x;
        n >>= 1;
    }
    return result;
}