数据结构算法技巧2. m的n次方

2. m 的 n 次方

如果让你解 2 的 n 次方，而你又不能使用系统内置函数 pow，你会怎么做？该怎么办？这并不简单。连续乘以n m 即可。代码如下：

int pow(int n){
    int tmp = 1;
    for(int i = 1; i <= n; i++) {
        tmp = tmp * m;
    }
    return tmp;
}

但是如果你做到了，只有我能做到哈哈，时间复杂度是O(n)，恐怕连小学生都能做到！如果要求您为此使用按位运算，您会怎么做？

让我举个例子。例如n = 13，则n的二进制表示为1101，则m的13次方可分解为：

m^1101 = m^0001 * m^0100 * m^ 1000。

Mi通过&1和>>1可以逐位读取1101。当为1时，将该位所代表的乘数与最终结果相加。看看代码，很容易理解：

int pow(int n){
    int sum = 1;
    int tmp = m;
    while(n != 0){
        if(n & 1 == 1){
            sum *= tmp;
        }
        tmp *= tmp;
        n = n >> 1;
    }

    return sum;
}

时间复杂度几乎是O(logn)，看起来很棒。

作者：美丽的土地
来源：知乎