P342 4的幂
暴力解法
- 比较所有4的幂
- 因为指数增长很快,在有限的范围内也不会太花时间
- 在当前范围内4的幂最大值为1073741824
1 |
|
时间复杂度 | 空间复杂度 |
---|---|
O(log(n)) | O(1) |
解法2
- 根据P231学会了如何判断2的幂
- 观察可知,4的幂是在2的幂基础上,1只出现在奇数位上

- 可以先判断是否是2的幂,然后构造一个偶数位全为1的数进行&运算,结果为0就是4的幂
1 |
|
时间复杂度 | 空间复杂度 |
---|---|
O(1) | O(1) |
解法3
- 在2的幂基础上mod3==1

1 |
|
时间复杂度 | 空间复杂度 |
---|---|
O(1) | O(1) |
不过看起来求模运算不是什么好主意