50. Pow(x, n)

Implement pow(x, n): x raised to the integer power n (n may be negative).

Write n in binary. Square x at every step; whenever the current bit of n is 1, multiply that power of x into the result. x^13 = x^8 · x^4 · x^1.

1function myPow(x: number, n: number): number {
2  let e = Math.abs(n), res = 1;
3  while (e > 0) {
4    if (e & 1) res *= x;
5    x *= x;
6    e = Math.floor(e / 2);
7  }
8  return n < 0 ? 1 / res : res;
9}

x^(2^k) = 2res = 1k = 0

|n| in binary

|n| = 13 = 1101₂.

1 / 0

Space: play/pause · ←/→: step