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

One, foreword

Exponentiation by Squaring (Exponentiation by squaring) is a simple and effective small algorithm that can calculate Exponentiation of time complexity. Not only are fast powers themselves very common, but many algorithms use fast powers.

Ii. Problem analysis

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

Day 45: Bit operation.

Let’s start with a question: how fast is 7 to the 11th?

1. Common solution

Isn’t the 11th power just 11 sevens times each other?

We need to do this 11 times, but it takes a lot of time.

2. The power quickly

If we convert 11 to binary, it’s 1011

7 11 = 78 74 ∗ ∗ 717 ^ ^ 8 * 7 7 ^ ^ 4 * 178 ∗ ∗ 74 71

If binary is 0, skip it.

When binary is 1, the power is equal to the decimal number corresponding to the current binary 1, and the fast power is computed only three times.

Let’s take n to the m as an example:

Define base as the power corresponding to the current binary of 1, and ans as the resulting value of m shifted to the right. If the current bit is 1, then ans= ANS *base; Base =base*base, because we're counting the ten digits of binary and when m is zero, we're printing out the resultCopy the code

Three, coding implementation

typedef long long ll;// Define long long
ll quick_pow(ll n,ll m)// Compute n to the m
{
	ll ans=1,base=n;/ / initialization
	while(m! =0)/ / m not 0
	{
	    if(m&1)// The current value is 1
		ans=ans*base;/ / multiplied
	    base=base*base;/ / count
	    m=m>>1;// Shift to the right
	}
	return ans;// Output the result
}
Copy the code