Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

One, foreword

Implement POW (x, n), that is, compute x to the NTH power (that is, XNX ^ NXN).

Pow(x, n).

Two, the title requirements

Sample 1

Input: x = 2.00000, n = 10 Output: 1024.00000Copy the code

The sample 2

Input: x = 2.10000, n = 3 Output: 9.26100Copy the code

inspection

1. Medium type of bit operation, fast power 2Copy the code

Third, problem analysis

17. If you do not know about bit operation, you can read the article in detail.

Day 45: Bit operation.

If you’ve read about bitwise operations, but you haven’t read about fast powers, you should read this

And then come back and do this problem and it’s pretty easy.

-23^1 <= n <= 2^31-1 <= n <= 2^31-1

Now, a little bit of caution here, because n could be less than 0, in which case we’re going to use the positive numbers, and we’re going to take the inverse.

When you finally submit the test, you find a couple of disgusting test cases that you can’t pass

Finally, I changed the n given by the problem, from int to long, and then I got confused.

Four, coding implementation

class Solution {
public:
    double myPow(double x, long n) {
        int flag=1;// Check n negative numbers
        double base=x,ans=1;/ / initialization
        if(n<0)
        {
            flag=0;
            n=abs(n);/ / take a positive number
        }
        while(n)// Fast power template
        {
            if(n&1)
                ans=ans*base;
            base*=base;
            n=n>>1;
        }
        if(flag)// Positive output results
            return ans;
        else// Take the reciprocal output
            return 1.0*1/ans; }};Copy the code

V. Test results

Sixth, summary and improvement

This is number 17 on the bit operations branch, number 2 on fast powers. Fast power control is not difficult, in the Internet for a long time, found 2 typical fast power operation, these two problems can be done fast power can basically master.