Pow(x, n) Solutions in C++

// Source : https://oj.leetcode.com/problems/powx-n/
// Author : Hao Chen
// Date   : 2014-06-25



#include <stdio.h>
#include <stdlib.h>

/*
 *   Basically, most people think this is very easy as below:
 *
 *      double result = 1.0;
 *      for (int i=0; i<n; i++){
 *           result *=x;
 *      }
 *   
 *   However, 
 *
 *     1) We need think about the `n` is negtive number.
 *
 *     2) We need more wisely deal with the following cases:
 *
 *         pow(1, MAX_INT);
 *         pow(-1,BIG_INT);
 *         pow(2, BIG_INT);
 *
 *        To deal with such kind case, we can use x = x*x to reduce the `n` more quickly
 *
 *        so, if `n` is an even number, we can `x = x*x`, and `n = n>>1;`
 *            if `n` is an odd number, we can just `result *= x;`
 *
 */
double pow(double x, int n) {

    bool sign = false;
    unsigned int exp = n;
    if(n<0){
        exp = -n;
        sign = true;
    }
    double result = 1.0;
    while (exp) {
        if (exp & 1){
            result *= x;
        }
        exp >>= 1;
        x *= x;
    }

    return sign ? 1/result : result;

}

int main(int argc, char** argv){
    double x=2.0;
    int n = 3;
    if (argc==3){
        x = atof(argv[1]);
        n = atoi(argv[2]);
    }
    printf("%f\n", pow(x, n));
    return 0;
}

#include <cmath> 

class Solution {
public:
    double pow(double x, int n) {
        if (!n) return 1;
        double tmp = pow(x, n/2);
        return n&0x1 ? n>0 ? x * tmp * tmp : tmp * tmp / x : tmp * tmp;
    }
};

/// Source : https://leetcode.com/problems/powx-n/
/// Author : liuyubobobo
/// Time   : 2018-12-20

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Classic Divide and Conquer to get power
/// Only deal with positive n
///
/// Time Complexity: O(logn)
/// Space Complexity: O(logn)
class Solution {
public:
    double myPow(double x, int n) {

        if(n == 0) return 1.0;

        double res = myPositivePow(x, abs((long long)n));
        if(n < 0) res = 1.0 / res;
        return res;
    }

private:
    double myPositivePow(double x, long long n){

        assert(n >= 0);
        if(!n) return 1.0;

        double t = myPositivePow(x, n / 2);
        double res = t * t;
        if(n % 2) res *= x;
        return res;
    }
};


int main() {

    cout << Solution().myPow(2.0, -2) << endl;
    // 0.25

    cout << Solution().myPow(-2.0, 2) << endl;
    // 4.0

    cout << Solution().myPow(34.00515, -3) << endl;
    // 3e-05

    cout << Solution().myPow(1.0, -2147483648) << endl;
    // 3e-05

    return 0;
}

/// Source : https://leetcode.com/problems/powx-n/
/// Author : liuyubobobo
/// Time   : 2018-12-20

#include <iostream>
#include <vector>

using namespace std;


/// Classic Divide and Conquer to get power
/// Deal with both positive and negative n correctly
///
/// Time Complexity: O(logn)
/// Space Complexity: O(logn)
class Solution {
public:
    double myPow(double x, int n) {

        if(n == 0) return 1.0;

        double t = myPow(x, n / 2);
        if(n % 2 == 0)
            return t * t;
        else if( n > 0)
            return t * t * x;
        return t * t / x;
    }
};


int main() {

    cout << Solution().myPow(2.0, -2) << endl;
    // 0.25

    cout << Solution().myPow(-2.0, 2) << endl;
    // 4.0

    cout << Solution().myPow(34.00515, -3) << endl;
    // 3e-05

    return 0;
}