After reading the question, you will point to offer 16 Integer power of numeric value

The finger of the sword Offer 16. Integer power of value

The question :

Realization pow(x, n) , Computation x Of n Power function （ namely ,xn）. Do not use library functions , At the same time, there is no need to consider the problem of large numbers .

Example 1：

 Input ：x = 2.00000, n = 10
 Output ：1024.00000

Example 2：

 Input ：x = 2.10000, n = 3
 Output ：9.26100

Example 3：

 Input ：x = 2.00000, n = -2
 Output ：0.25000
 explain ：2-2 = 1/22 = 1/4 = 0.25

Their thinking :

Premise : because x be equal to 2 Of 31 Power -1, So there is no solution with violence . Then we have to solve it by splitting

How to split ?

In fact, it is to change the base number , Because the base becomes larger, the index will correspondingly become smaller , and If your base number changes every time as a square , Then the index will be divided by each time 2. So the time complexity becomes log₂n

The point is to change the base number . Because according to the index , Changes are also different . also The index may be negative , So there are more cases .

Let's first discuss the case where the index is positive :

• If the exponent is even , So let's just Base squared ( base number * base number ), Then the exponent is divided by 2 that will do
• If the exponent is odd . We need to split , Take out a base number to make the index even . Then record the split number

Specific examples are shown in the figure below :

In the same way, we can divide the exponent by each time 2 To shrink .

In the end, the exponent may be equal to 1, It may also be equal to 2;

• be equal to 1 If so, let's just point to the number divided * The last base
• be equal to 2 So we have to square the base first and then * The number of splits

This part of the code is as follows :

// Greater than 2 In this case, we continue to divide the number of times by 2
while(n > 2)
{
    
    // If it's odd 
    if(n % 2 == 1)
    {
    
        // First split a base number 
        res *= index;
        // Let the index decrease 1
        n--;
    }
    // If the base number is even 
    else
    {
    
        // Base squared , Index divided by 2
        index = index * index;
        n = n / 2;
    }
}

// be equal to 2 Let's square the base first and then  *  The number of splits 
if(n == 2)
    return index * index * res;
// be equal to 1 It directly refers to the number split  *  The last base 
else
    return res * index;

Then we need to judge that it is less than 0 The situation of .

In fact, the whole is the same , Let's go first x Become the reciprocal , then n Take the absolute value to bring in the above code .

So the overall code is as follows :

class Solution {
    
public:
    double myPow(double x, int n)
    {
    
        // Index is 0 Or the base number is 1, Whatever else is 1
        if(n == 0 || x == 1.0)
            return 1;
        // Greater than 0 The situation of 
        else if(n > 0)
        {
    
            // Store the split number 
            double res = 1;
            // Record base 
            double index = x;
            while(n > 2)
            {
    
                if(n % 2 == 1)
                {
    
                    res *= index;
                    n--;
                }
                else
                {
    
                    index = index * index;
                    n = n / 2;
                }
            }
            if(n == 2)
                return res * index * index;
            else
                return res * index;
        }
        // Less than 0 The situation of 
        else
        {
    
            // Take the bottom 
            x = 1.0 / x;
            // base number 
            double index  = x;
            // Take the absolute value 
            n = abs(n);
            // Store the split number 
            double res = 1;
            while(n > 2)
            {
    
                if(n % 2 == 1)
                {
    
                    res *= index;
                    n--;
                }
                else
                {
    
                    index = index * index;
                    n = n / 2;
                }
            }
            // Return the result according to the situation 
            if(n == 2)
                return res * index * index;
            else
                return res * index;
        }

    }
};

summary

In fact, there are repetitive parts , Making a package may be more beautiful . But I didn't finish it when I was doing it . You can do it if you want . Just make a package for the repeated part ;