Pow(x, n)

发表于 | 分类于

Pow(x, n)

题目描述：

给定一个数x,求得其n次方的结果。

例子：

具体描述见LeetCode50

解题思路：

这一题主要注意的地方有：我们的n可能是负数，所以需要判断是否对x取倒数；其次是p可能非常的大需要比较大的数来保存。另外因为用到了移位的位算法，所以我们需要将p定义为无符号的数。而后对于下面的移位操作简单进行说明。假设我们要计算3的11次方的结果；二进制表示为1011。第一次末尾为1，所以将结果乘以3，然后移位，然后乘数进行乘积变为9；二次移位也是1，所以继续乘以9，这时候结果是3次方；而后x继续乘积就是4次方，但是移位结果为0；所以不进行乘积；继续乘方为8次方，末尾为1.所以结果为11次方。程序结束。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    double myPow(double x, int n) {
        double ans = 1;
        unsigned long long p;
        if (n < 0){
            x = 1 / x;
            p = -n;
        }else{
            p = n;
        }
        while(p){
            if (p & 1){
                ans *= x;
            }
            x *= x;
            p >>= 1;
        }
        return ans;
        
    }
};