# 50 Pow(x, n)

## 50. [Pow(x, n)](https://leetcode.com/problems/powx-n/description/)

## 1. Question

Implement [pow(x,n)](http://www.cplusplus.com/reference/valarray/pow/).

**Example 1:**

```
Input: 2.00000, 10

Output: 1024.00000
```

**Example 2:**

```
Input: 2.10000, 3

Output: 9.26100
```

## 2. Implementation

**(1) 倍增法**

```java
class Solution {
    public double myPow(double x, int n) {
        if (x == 0) {
            return 0.0;
        }

        double res = 1.0;

        while (n != 0) {
            if ((n & 1) == 1) {
                if (n > 0) {
                    res *= x;
                }
                else {
                    res /= x;
                }
            }
            x *= x;
            n /= 2;
        }
        return res;
    }
}
```

## 3. Time & Space Complexity

**倍增法:** 时间复杂度O(logn), 空间复杂度O(1)
