Implementing pow(x,n)

I solved this leetcode problem.

The question is.


Implement pow(x, n).

This is my solution.

class Solution {
public:
    double doPow(double x, unsigned int n)
    {
        double result = 1;
        while(n > 0)
        {
            if(n & 1) // if bit is set
            {
                result = result * x;
            }
            n = n >> 1;
            x = x * x;
        }
        return result;
    }
    double myPow(double x, int n) {
        unsigned int temp = abs(n);
        if(n < 0)
        {
            return 1/doPow(x, temp);
        }
        return doPow(x,n);
    }

};

Although this solution gets accepted, it converts n to unsigned to make sure that INT_MIN doesn't overflow when it is converted to it's positive values and then computed.

Is there a better way to handle negative exponents?

Extracting the unsigned calculation just to solve the possible overflow problem is unnecessary. Of course, having an unsigned version of the function may be useful for other reasons in "real" code, but that would be a different motivation.

You can handle your problem here with a simple variable, and not a whole function:

double myPow(double x, int n) {
    unsigned int p = abs(n);
    double result = 1;
    while(p > 0)
    {
        if(p & 1) // if bit is set
        {
            result = result * x;
        }
        p = p >> 1;
        x = x * x;
    }

    if(n < 0)
    {
        return 1/result;
    }
    return result;
}

Changing the unsigned part to use the unsigned int p instead of n, and then using n to test for the negative later is just fine.

Now, a more general review...

Your comment (the only one), is not great, the code here is obvious:

if(p & 1) // if bit is set

I would remove the comment, or change it to // for odd powers

I needed to take some time to figure out how you did the algorithm, and how it works out to \$O(\log{p})\$ (where p is the power) complexity. It's an "advanced" solution, and in that respect you can be proud of it. I am trying to figure out how to make the algorithm more obvious though. It's complicated that the result is only set on odd-powers in the shifting. Comments on your algorithm would help, but I am sure there's a way to make the process more obvious in the code... I'm still thinking.

Regardless, the code style is good, your variable names are not great, but are not horrible for 1-letter names either.

Overall, with a better description of the mechanics of the solution as comments in the code, I would call it good.

StackExchange Code Review Q#156618, answer score: 5