首先21的二进制形式是10101
不难得出以下结论
3 ^ n（n为2、4、8、16）都可以由3 ^ 1累乘出来
每一个3 ^ n都有对应的二进制位
3 ^ 1对应二进制位的值是1，其实是二进制10101的最后1位
3 ^ 2对应二进制位的值是0，其实是二进制1010的最后1位
3 ^ 4对应二进制位的值是1，其实是二进制101的最后1位
3 ^ 8对应二进制位的值是0，其实是二进制10的最后1位
3 ^ 16对应二进制位的值是1，其实是二进制1的最后1位
如果3 ^ n对应二进制位的值是0，就不用乘进最终结果
比如3 ^ (8 * 0)、3 ^ (2 * 0)
因为它们最终的值都是3 ^ 0，也就是1
如果3 ^ n对应二进制位的值是1，就需要乘进最终结果
比如3 ^ (16 * 1)、3 ^ (4 * 1)、3 ^ (1 * 1)
所以，综合以上种种结论，可以总结出以下解题步骤
利用3 ^ 1，不断累乘出3 ^ n（n为2、4、8、16）
每当累乘出一个3 ^ n，就查看其对应二进制位的值是1还是0，来决定是否要将它乘进最终结果
int fastPower(int x, int n) { int result = 1; while (n != 0) { if ((n & 1) == 1) { result *= x; } x *= x; n >>= 1; } return result; }代入3和21，fastPower(3, 21)的执行流程如下
第1轮while循环第4行代码
n的二进制是10101（十进制是21）
x = 3 ^ 1, 其对应二进制位的值是1（n的最后一个二进制位）
所以需要执行第5行代码：将x乘进最终结果
result = 3 ^ 1
第7行代码
x = (3 ^ 1) * (3 ^ 1) = 3 ^ 2
第8行代码
n右移1位，其二进制变成了1010（对应的十进制是啥？不重要！！！）
第2轮while循环第4行代码
n的二进制是1010
x = 3 ^ 2, 其对应二进制位的值是0（n的最后一个二进制位）
所以不需要执行第5行代码：不需要将x乘进最终结果
result = 3 ^ 1
第7行代码
x = (3 ^ 2) * (3 ^ 2) = 3 ^ 4
第8行代码
n右移1位，其二进制变成了101（对应的十进制是啥？不重要！！！）
第3轮while循环第4行代码
n的二进制是101
x = 3 ^ 4, 其对应二进制位的值是1（n的最后一个二进制位）
所以需要执行第5行代码：将x乘进最终结果
result = (3 ^ 1) * (3 ^ 4)
第7行代码
x = (3 ^ 4) * (3 ^ 4) = (3 ^ 8)
第8行代码
n右移1位，其二进制变成了10（对应的十进制是啥？不重要！！！）
第4轮while循环第4行代码
n的二进制是10
x = 3 ^ 8, 其对应二进制位的值是0（n的最后一个二进制位）
所以不需要执行第5行代码：不需要将x乘进最终结果
result = (3 ^ 1) * (3 ^ 4)
第7行代码
x = (3 ^ 8) * (3 ^ 8) = 3 ^ 16
第8行代码
n右移1位，其二进制变成了1（对应的十进制是啥？不重要！！！）
第5轮while循环第4行代码
n的二进制是1
x = 3 ^ 16, 其对应二进制位的值是1（n的最后一个二进制位）
所以需要执行第5行代码：将x乘进最终结果
result = (3 ^ 1) * (3 ^ 4) * (3 ^ 16)
第7行代码
x = (3 ^ 16) * (3 ^ 16) = 3 ^ 32
第8行代码
n右移1位，其二进制变成了0
最后由于n = 0，所以退出while循环
最终result = (3 ^ 1) * (3 ^ 4) * (3 ^ 16)
复杂度分析
每执行一次while的循环体，n >>= 1, 会导致n的值减半
所以时间复杂度：O(logn)、空间复杂度：O(1)
Leetcode