2022/10/15

快速幂

通常做幂运算，例如 2**3，就是运算 2 * 2 * 2，这种方式在幂次 n 很高的情况下，效率就很低，需要做 n 次乘法运算。

快速幂是用移位思想，例如 2**9，就是把幂次 9 看做二进制 1001 ，从最低位开始，若为1，则让结果 ans 乘以当前 x （底数的位数次方）。

显然的，1001 最低位为 1 ，则 ans = 1 * 2 = 2，右移 1001 为 100，最低位不为 1，无需改变 ans，但 x 仍需要自乘。最终将得到 ans = (2) * (2**8)

ts

// n 为正整数
function quickPow(x: number, n: number): number {
  let ans = 1
  while (n > 0) {
    if (n & 1) {
      ans = ans * x
    }
    x = x * x
    n = n >>> 1
  }
  return ans
}

快速幂的时间复杂度相较于暴力乘算是很低的，可以想见，对 n 进行右移逼近循环终止 0 ，与对 n 进行递减逼近 0 要快得多。

js 移位

js 中数字的最大范围是2的53次方，而在移位运算中，就是 js 仅支持 32 位整型数，也即从-2147483648 到+2147483647 之间的整数。

在处理 2147483648 移位时将溢出，所以可以使用 >>> 代替 >>

判断对象为空

Object.keys(obj).length === 0
JSON.stringify(obj) === '{}'