Non-recursive C++ log(n) solution


  • 43
    G
    class Solution {
    public:
        double myPow(double x, int n) {
        	double ans = 1;
        	unsigned long long p;
        	if (n < 0) {
        		p = -n;
        		x = 1 / x;
        	} else {
        		p = n;
        	}
    		while (p) {
    			if (p & 1)
    				ans *= x;
    			x *= x;
    			p >>= 1;
    		}
    		return ans;
        }
    };

  • -4
    L

    Very clear logic. I wrote it in C#, while I don't think we need long long p.

    public double MyPow(double x, int n) {
        if(n < 0){ n = -n; x = 1 / x; }
        double result = 1;
        while(n > 0){
            if((n & 1) == 1) result *= x;
            x *= x;
            n >>= 1;
        }
        return result;
    }

  • 0
    S

    Hi. I think it's necessary to have long long p. For example ,if n=MIN_INT,then -n will oveflow if p is just int.


  • 2
    F

    Thanks for your sharing.
    There is a bug.
    When n = INT_MIN, "-n" is already overflow since -1 is int. The result of -n is still INT_MIN.
    Then p is therefore wrong since p is assigned from a negative but p is unsigned.
    However the result with this bug can still pass because the only test case with INT_MIN is (1.0, INT_MIN). "-n" should be change to "(-1LL) * n" and p can be either unsigned or signed long long.


  • 0
    Y

    Can you explain what does " if (p & 1) ans *= x;" mean?


  • 0

    Thank you for your sharing.
    It is advisible to use long long p.

    And I think it is better to change the code like this

    long long p = n;
    	if (n < 0)
    	{
    		p = -n;
    		x = 1 / x;
    	}
    	
    

  • 0
    D

    @yang121 means p is an odd number.


  • 0
    W

    Unsinged long ,helpful, thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.