Pow(x, n)

最朴素的写法：把 x 连乘 n 次。可 n 最大约 21 亿，连乘 21 亿次必然超时，O(n) 走不通。

关键观察：13 的二进制是 1101，所以 x 的 13 次方 = x¹ × x⁴ × x⁸。只要逐位扫 n，遇到 1 就把当前这块乘进答案。

灵魂帧 · 用 2 的 13 次方慢放：先看清 13 的二进制 1101：从低位到高位，第 0、2、3 位是 1，这三位决定哪些 base 要乘进答案。下面每一轮都拆成『看最低位、决定乘不乘』和『base 平方、n 减半』两帧，节奏全程一致。

初始：ans=1, base=2, n=13：开局三个变量：答案 ans 从 1 起步，base 就是 x（这里是 2），指数 n=13。每轮只盯 n 的最低位。

第 0 轮 · 看最低位：是 1，ans 乘 base：第 0 轮先看最低位：n=13 最低位是 1，把当前 base=2 乘进答案，ans 从 1 变成 2。这一帧只做这一件事——乘答案，base 还没动。

第 0 轮 · 收尾：base 平方，n 减半：本轮收尾固定两步：base 自己平方（2 变 4，代表 x²），n 右移一位（13 变 6）。base 翻倍指数，对应二进制往高位走。

第 1 轮 · 看最低位：是 0，跳过乘法：进入第 1 轮，base 此刻是 4（上一轮平方而来，代表 x²）。看最低位：n=6 最低位是 0，说明 x² 这一项不要，ans 保持 2 不动。这一帧只是『看一眼、不乘』。

第 1 轮 · 收尾：base 平方，n 减半：和每轮一样收尾：base 平方（4 变 16，代表 x⁴），n 减半到 3。注意——base 在每轮结尾都恰好平方一次，时序固定，别数多也别数漏。

第 2 轮 · 看最低位：是 1，ans 乘 16：第 2 轮先看最低位：n=3 最低位是 1，此刻 base=16 正好代表 x 的 4 次方，乘进答案，ans 从 2 变 32。这一帧 base 仍是 16，还没平方。

第 2 轮 · 收尾：base 平方，n 减半：本轮收尾照旧：base 平方（16 变 256，代表 x⁸），n 减半到 1。记住这一步——256 是在第 2 轮结尾才长出来的，下一轮直接拿来用，不会再平方第二次。

第 3 轮 · 看最低位：是 1，ans 乘 256：最后一轮，base 此刻正是 256（上一轮已由 16 平方而来，代表 x⁸），最低位仍是 1，直接 ans = 32 × 256 = 8192。这里没有任何『再平方』动作——256 是上轮收尾就备好的。

第 3 轮 · 收尾：n 减半归 0，循环结束：收尾仍是同两步：base 再平方成 65536（但 n 已为 0，这个值用不上了），n 减半归 0。while 退出，ans=8192 正是 2 的 13 次方。每轮结尾平方一次，全程数下来 base 恰好平方了 4 次。

负指数：开头先倒数：遇到负指数别在循环里特判。开头统一把 x 变成它的倒数、n 取相反数变成正数，后面主循环完全一样。

一句话本质：n 的二进制每个为 1 的位，对应的 base 恰好是 x 的那一段，乘进去就还原了 x 的 n 次方。

边界三连：边界比主体更容易拉分：n=0 要返回 1，负指数要倒数，而 32 位最小值取负这一步若不用 long 会直接溢出成负数。

面试追问：面试三连：递归写法、浮点容差、整数边界。把 long 防溢出这点主动讲出来，最加分。

同一套「遇 1 就乘、每轮平方」可迁移：把 base 换成矩阵，就能 O(log n) 求斐波那契、数图上长度为 n 的路径数。