Day 22 2021.1.17

A number raised to an integer power

  • Leetcode: leetcode-cn.com/problems/sh…
  • Difficulty: Medium
  • Methods: recursion, fast power, arithmetic shift, logical shift

The title

  • Implement POW (x, n), that is, compute x to the NTH power (that is, xn). Library functions should not be used and large numbers should not be considered.

The sample

  • Example 1
Input: x = 2.00000, n = 10 Output: 1024.00000Copy the code
  • Example 2
Input: x = 2.10000, n = 3 Output: 9.26100Copy the code
  • Example 3
Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25Copy the code

prompt

  • -100.0 < x < 100.0
  • -2^31 <= n <= 2^31-1
  • -10^4 <= x^n <= 10^4

expand

  • Arithmetic shift: the highest bit is a sign bit and stores signed integers.
    • Positive number: the highest bit is 0, the computer used to store positive numbers in the source code
    • Negative number: the highest bit is 1. The computer stores negative numbers with complement (the original code is inverse +1).
  • Logical shift: Stores unsigned integers without signed bits.
  • When the exponential is negative, there are two solutions
    1. Change the absolute value of the index to a positive number, namely:n = -n.xInvariant, and finally returns:1/ans
    2. Transformation basexfor1/x.nInvariant, return at lastans
  • useJSIn the>>Operator exists whenPit point:
    • >>Arithmetic shift, because the numbers they gave us, the negative numbers can be taken- 2 ^ 31, but when you convert it to a positive number, you exceed the maximum value of a signed integer2 ^ 31-1, thenjsThe internal will convert it to an unsigned integer for storage, and it will not exceed.butUse at this point>>The arithmetic shift operator will fail.
    • >>>Logical shift, the solution, using the logical shift operator.

solution

  • Recursive method:
    • N is odd -> x^ 2/n ^2 times x
    • N is even -> x^ 2/n ^2
    • N = 0 -> 1 (recursive termination return condition)
/ * * *@param {number} x
 * @param {number} n
 * @return {number}* /
var myPow = function(x, n) {
  // Use a fast power algorithm
  // The recursive idea
  // 1. Odd number a,n-1 * a
  // 2. Even a, n / 2
  // 3. a,0 1
  function fastPower (x,n) {
    if (n == 0) return 1;
    n = n < 0 ? -n : n;
    if (n % 2= =0) {
      / / even
      let record = fastPower(x,n / 2);
      return record * record;
    }else {
      / / odd
      return fastPower(x, n - 1) * x; }}if (n < 0) {
    // The exponent is negative
    return (1 / fastPower(x,n)).toFixed(5);
  }else {
    return fastPower(x,n).toFixed(5); }};Copy the code
  • Non-recursive methods: useThe while loopThe form of storage in the computer is binary, so you can determine whether you need to multiply to by each right shiftansIn the.
    • Why every roundx *= x, the reasons are as follows (for examplex = 3, n = 13),nbinary'1101', let’s write it the other way around for easy observation
      1 0 1 1
      3 3 * 3 = 9 9 * 3 = 27 27 * 3 = 81
      to Don’t to to
    • We know from observation that either1Or for0.XThey all have to multiply.
/ * * *@param {number} x
 * @param {number} n
 * @return {number}* /
var myPow = function(x, n) {
  // Fast powers of non-recursive practices
  if (x == 1 || n == 0) return 1;
  if (n == 1) return x;
  let ans = 1,flag = false;
  n > 0 ? flag = true : n = -n;
  while(n ! =0) {
    if (n & 1! =0) ans *= x;
    x *= x;
    / / can be replaced
    n >>>= 1;
    // Replace the statement
    n = Math.floor(n / 2);
  }
  if (flag) return ans;
  else return 1 / ans; 
};
Copy the code

The appendix

  • Shift operator>> >>>
  • An operator&: Determines the parity of the current value
  • Take fixed decimal place:toFixed(5)