**source:**https://leetcode.com/problems/powx-n/**C/C++**

**Solution to LeetCode**problem

**50**.

**Pow(x, n)**.

## Problem

Implement `pow(x, n)`

, which calculates `x`

raised to the power `n`

(i.e., `x`

).^{n}

## Examples

**Example 1:**

Input:x = 2.00000, n = 10

Output:1024.00000

**Example 2:**

Input:x = 2.10000, n = 3

Output:9.26100

**Example 3:**

Input:x = 2.00000, n = -2

Output:0.25000

Explanation:2^{-2}= 1/2^{2}= 1/4 = 0.25

## Constraints

`-100.0 < x < 100.0`

`-2`

^{31}<= n <= 2^{31}-1`n`

is an integer.`-10`

^{4}<= x^{n}<= 10^{4}

## Solution

Instead of multiplying by `x`

`n-times`

we will optimize (reduce the amount of times we multiply) using the *right-shift* **bitwise** operation.

- We initialize our
`result = 1`

. - While
`n > 0`

(we use the absolute value of n). - If the last (LSB) of
`n`

is`1`

we multiply`result * x`

. - We multiply
`x`

by itself (`x * x`

). - And
`right-shift`

`n`

(`n >> 1`

). - Finally, if the original
`n<0`

, then the result will be`1/result`

otherwise`result`

.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
double myPow(double x, int n) {
double ans = 1.0;
bool neg = n < 0;
n = abs(n);
while (n > 0) {
if (n & 1)
ans = ans * x;
x = x * x;
n = n >> 1;
}
return neg ? 1 / ans: ans;
}
};