題目：給定一個double類型的浮點數(shù)base和int類型的整數(shù)exponent丧枪。求base的exponent次方纹份。
方法一：
public class Solution {
public double Power(double base, int exponent) {
double result = 1;
int n = exponent;
if(exponent == 0){
return 1;
}else if(exponent < 0){
if(base == 0){
throw new RuntimeException();
}
exponent = -exponent;
}
while(exponent != 0){
if((exponent & 1) == 1){
result *= base;
}
base *= base;
exponent >>= 1;
}
return n >= 0 ? result : (1 / result);
}
}
方法二：
public class Solution {
public double Power(double base, int exponent) {
if(exponent == 0){
return 1;
}
double result = 1;
int keng = exponent;
if(exponent < 0){
if(base == 0){
throw new RuntimeException("分母不能為0");
}
exponent = -exponent;
}
while(exponent != 0){
if((exponent & 1) == 1){
result *= base;
exponent--;
}
if(exponent != 0){
result *= result;
}
exponent = exponent >> 1;
}
return keng >= 0 ? result : (1 / result);
}
}
這個題目主要考察了贷腕，數(shù)學(xué)中的一些坑，比如一個數(shù)的負(fù)數(shù)次方是正數(shù)次方的倒數(shù)殿较，如果一個數(shù)在分母處，他不能為0;
之后就是一些優(yōu)化了鸽粉，千萬不要直接從頭乘到尾，他的時間復(fù)雜度是O（n）抓艳。既然是算法触机，利用計算機(jī)求解，應(yīng)該合理的運用計算機(jī)的一些特性玷或，比如說二進(jìn)制儡首。一般情況下使用二進(jìn)制的特性都可以將一些運算的問題時間復(fù)雜度降為O(logn)
以上兩種方法都是利用二進(jìn)制分解exponent的值。
方法二是我一開始想到的偏友，用了幾個例子找規(guī)律找出來的蔬胯。
比如說exponent = 101 也就5
- 當(dāng)最低位為1的時候先將上一步運算（最開始為1）的結(jié)果乘base 然后將最低位的1變成0，既100位他。 也就是x^5 變?yōu)?x^4 相當(dāng)于累成x
- 之后就是移位氛濒，將100向右移動一位，這會導(dǎo)致4變成2鹅髓，所以在這之前要將上一部的結(jié)果平方舞竿。也就和對等了
- 最后的時候，這個exponent一定會變?yōu)?窿冯，由于exponent-1之后變成了0骗奖，這個時候只需要再乘一個base就行了，就不需要后面的平方了醒串。
方法一：
上面的方法二的思路是我自己想的执桌，所以這個算法步驟有些凌亂。
方法一是盼叨模客里的一個推薦答案仰挣。
首先看這樣的一個例子
如果exponent = 100101
設(shè)底數(shù)為x
那么結(jié)果可以拆分為 x^ (2^5) * x^(2 ^ 2) * x^ (2^0)
x的（2的5次冪）乘 x的（2的2次冪）乘 x的（2的0次冪）
所以我們可以通過移位來獲得
x^100000
x^100
x^1
然后乘在一起就可以了；
每次將exponent 向右移位就將base平方
然后遇到最低位為1的時候就將base乘到結(jié)果上缠沈。
設(shè)base = 3椎木；
exponent = 100101
初始化result = 1；
100101
最低位為1
result = result * base = 3博烂；
base = base * base = 9移位然后平方
10010
最低位為0
base = base * base = 81移位然后平方
1001
最低位為1
result = result * base = 243香椎；
base = base * base = 6561 移位然后平方
100
最低位為0
base = base * base = 。禽篱。畜伐。移位然后平方
10
最低位為0
base = base * base = 。躺率。玛界。移位然后平方
1
最低位為1
result = result * base = 結(jié)果万矾；
