start

Find the n-th power of x (just talk about n nonnegative first)

Violent solution

x n = x ⋅ x ⋅ x ⋅ ⋅ ⋅ x x^{n} = x · x · x ··· x xn=x ⋅ x ⋅ x ⋅ ⋅ x (multiply n x)

[violence solution] key steps

let result = 1
while(n > 0){
    result *= x
    n--
}

Cycle n times, time complexity is O(N)

Counting

Key steps of [fast power]

Let's take an example to find the 100th power of x

The solution to violence is

x 100 = x ⋅ x ⋅ x ⋅ ⋅ ⋅ x x^{100} = x · x · x ··· x x100=x ⋅ x ⋅ x ⋅ ⋅ x (multiply 100 x)

Because the binary of 100 is 1100100, so

100 = 0 ⋅ 2 0 + 0 ⋅ 2 1 + 1 ⋅ 2 2 + 0 ⋅ 2 3 + 0 ⋅ 2 4 + 1 ⋅ 2 5 + 1 ⋅ 2 6 100 = 0·2^0 + 0·2^1 + 1·2^2 + 0·2^3 + 0·2^4 + 1·2^5 + 1·2^6 100=0⋅20+0⋅21+1⋅22+0⋅23+0⋅24+1⋅25+1⋅26

that is

100 = 2 2 + 2 5 + 2 6 100 = 2^2 + 2^5 + 2^6 100=22+25+26

So we can simplify the solution formula

x 100 = x 2 2 ⋅ x 2 5 ⋅ x 2 6 x^{100} = x^{2^2} · x^{2^5} · x^{2^6} x100=x22⋅x25⋅x26

let result = 1
// When n === 0, there is no loop, and the result is result === 1
while (n > 0) {
    // Judge whether the current lowest order is 1
    if ((n & 1) === 1) result *= x
    x *= x
    n >>>= 1 // Move right without symbol to delete the lowest order
}

loop l o g 2 N log_2 N log2 ＾ N times, and the time complexity is O(logN)

LeetCode 50. Pow(x, n)

Let's look at a power problem on LeetCode 50. Pow(x, n)

The key step is the same, mainly considering the case of negative power

var myPow = function(x, n) {
    let result = 1

    let flag = false
    if(n < 0){
        flag = true
        n = -n
    }

    while (n > 0) {
        if ((n & 1) === 1) result *= x
        x *= x
        n >>>= 1
    }
    if(flag){
        result = parseFloat(1/result)
    }
    return result
};

There is also a more concise code. I named it preprocessing

var myPow = function(x, n) {
    let result = 1

    if(n < 0){
        x = parseFloat(1/x)
        n = -n
    }

    while (n > 0) {
        if ((n & 1) === 1) result *= x;
        x *= x
        n >>>= 1;
    }
    
    return result
};

Naturally, the first is post-processing. Find the positive solution, and then take a reciprocal at the end

It can be seen that the efficiency of post-processing is higher than that of first processing. This is the comparison when I submitted it for the first time, but I tried it again today

The result is like this. The efficiency of JS in LeetCode is really a mystery~
I won't discuss too much here. I have the opportunity to study it again

Find the last digit of the power of a large number

Let's increase the difficulty: the two non negative numbers passed in are strings, which may be very large numbers;
At the same time, simplify the topic again: just return the last digit of the result

[requirements] requirements a b a^b The last digit of ab, a and b may be very large

[analysis]
seek a b a^b The last digit of ab only requires the last digit. No matter how large a is, we only need to calculate the last digit of a and c c b c^b The result of cb is enough

let a = +str1[str1.length - 1];

The next step is the process of fast exponentiation

while (b > 0) { 
    if ((b & 1) === 1) result = (result * a) % 10; 
    a = (a * a) % 10; 
    b >>>= 1; 
}

Since only the last bit is required, the single digit is obtained by% 10 in the operation (result and a)

So the complete code is like this

function yk(str1, str2) {
  let a = +str1[str1.length - 1];
  let b = +str2;
  if (a === 0) return 0;
  let result = 1;

  while (b > 0) {
    if ((b & 1) === 1) result = (result * a) % 10;
    a = (a * a) % 10;
    b >>>= 1;
  }

  return result;
}

const res = yk("24979", "8");
console.log(res); // 1

String repeated n times

To expand, let's talk about a string str repeated count times. We use the idea of fast power

See my previous blog for more details
[youth training camp] teacher Yueying told me four skills for writing JavaScript code - style first

function repeat(str, count) {
  var result = "";
  while (count > 0) {
    if ((count & 1) == 1) result += str;
    count >>>= 1;
    str += str;
  }
  return result;
}
const res = repeat("*", 10)
console.log(res) // **********

summary

Using fast exponentiation can reduce the time complexity of exponentiation

The fast power has a unified form and can be expanded