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.


  • 3
    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!


  • 0
    S

    @forestwn You are right. The existing test case won't reveal this problem. One additional test case is needed here!


Log in to reply
 

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