LeetCode: Pow(x, n)

Implement pow(x, n).

---

We can use divide and conquer for this question. Divide the exponent by 2 each time until to 1. I implemented iterative version in C++, recursive version in Python.

C++ Code:

/*
 * func: pow
 * goal: implement pow(x, n)
 * @param x: base
 * @param n: exponent
 * return: result
 */
double pow(double x, int n){
    unsigned int m = abs(static_cast<long>(n));
    double result = 1;
    for(; m; x *= x, m >>= 1){
        //If the current bit is set
        if(m & 1){
            result *= x;
        }
    }
    return (n < 0) ? (1.0 / result) : result;
}

Python Code:

# func: implement pow(x, n)
# @param x: base
# @param n: exponent
# @return: result
def pow_t(x, n):
    if n < 0:
        return 1/pow_t(x, -n)
    elif n == 0:
        return 1
    elif n & 1:
        tmp = pow_t(x, n/2)
        return tmp * tmp * x
    else:
        tmp = pow_t(x, n/2)
        return tmp * tmp

Reference Link:

[closed] Pow(x, n) - LeetCode: http://discuss.leetcode.com/questions/228/powx-n