❓题目一
231. 2 的幂
难度：简单
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 `false 。
如果存在一个整数 x 使得 n = = 2 x n == 2^x n==2x ，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1
输出：true
解释：20 = 1
示例 2：
输入：n = 16
输出：true
解释：24 = 16
示例 3：
输入：n = 3
输出：false
示例 4：
输入：n = 4
输出：true
示例 5：
输入：n = 5
输出：false
提示：
- − 2 31 < = n < = 2 31 − 1 -2^{31} <= n <= 2^{31} - 1 −231<=n<=231−1
进阶： 你能够不使用循环/递归解决此问题吗？
💡思路：
基础知识必知：位运算基本原理
法一：数学
- 2 的幂次方，二进制表示只有一个 1 存在，因此可以使用数学除法判断。
法二：循环
- 使用位运算中的右移操作，循环判断 n 是否是2 的幂次方。
法三：判断是否只有一个1
- 使用位运算 n & (n - 1) 的性质去掉最后一个1 ，判断是否等于 0。
🍁代码：(Java、C++)
法一：数学
Java
class Solution { public boolean isPowerOfTwo(int n) { if(n == 1) return true; if(n <= 0 || n % 2 != 0) return false; return isPowerOfTwo(n / 2); }} C++
class Solution {public: bool isPowerOfTwo(int n) { if(n == 1) return true; if(n <= 0 || n % 2 != 0) return false; return isPowerOfTwo(n / 2); }}; 法二：循环
Java
class Solution { public boolean isPowerOfTwo(int n) { if(n <= 0) return false; while(n > 1){ if((n & 1) == 1) return false; n >>>= 1; } return true; }} C++
class Solution {public: bool isPowerOfTwo(int n) { if(n <= 0) return false; while(n > 1){ if((n & 1) == 1) return false; n >>= 1; } return true; }}; 法三：判断是否只有一个1
Java
class Solution { public boolean isPowerOfTwo(int n) { if(n <= 0) return false; return (n & (n - 1)) == 0; }} C++
class Solution {public: bool isPowerOfTwo(int n) { if(n <= 0) return false; return (n & (n - 1)) == 0; }}; 🚀 运行结果：
🕔 复杂度分析：
- 时间复杂度： O ( 1 ) O(1) O(1)，法三的时间复杂度为 O ( 1 ) O(1) O(1)。
- 空间复杂度： O ( 1 ) O(1) O(1)。
题目来源：力扣。
❓题目二
342. 4的幂
难度：简单
给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n = = 4 x n == 4^x n==4x。
示例 1：
输入：n = 16
输出：true
示例 2：
输入：n = 5
输出：false
示例 3：
输入：n = 1
输出：true
提示：
- − 2 31 < = n < = 2 31 − 1 -2^{31} <= n <= 2^{31} - 1 −231<=n<=231−1
进阶： 你能不使用循环或者递归来完成本题吗？
💡思路：
基础知识必知：一篇文章搞懂位运算
4 的幂次方，说明 n 用二进制表示，只有一个 1。
法一：数学
- 4 的幂次方，一定是 4 的倍数，因此可以使用数学除法判断。
- 使用 递归 迭代判断。
法二：循环
- 使用位运算中的 右移操作，循环判断 n 是否是4 的幂次方。
- n 和 3 (11) 按位与，如果不为 0 则一定不是 4 的幂。
法三：位运算
- 使用位运算 n & (n - 1) 的性质去掉最后一个1 ，判断是否等于 0，等于 0 则说明只有一个 1；
- 然后在和0x55555555（01010101 01010101 01010101 01010101）按位与，判断是否等于原数，相等则为 4 的幂。
🍁代码：(Java、C++)
法一：数学
Java
class Solution { public boolean isPowerOfFour(int n) { if(n == 1) return true; if(n <= 0 || n % 4 != 0) return false; return isPowerOfFour(n / 4); }} C++
class Solution {public: bool isPowerOfFour(int n) { if(n == 1) return true; if(n <= 0 || n % 4 != 0) return false; return isPowerOfFour(n / 4); }}; 法二：循环
Java
class Solution { public boolean isPowerOfFour(int n) { if(n <= 0) return false; while(n > 1){ if((n & 3) != 0) return false; n >>>= 2; } return true; }} C++
class Solution {public: bool isPowerOfFour(int n) { if(n <= 0) return false; while(n > 1){ if((n & 3) != 0) return false; n >>= 2; } return true; }}; 法三：位运算
Java
class Solution { public boolean isPowerOfFour(int n) { if(n <= 0) return false; return (n & (n - 1)) == 0 && (n & 0x55555555) == n; }} C++
class Solution {public: bool isPowerOfFour(int n) { if(n <= 0) return false; return (n & (n - 1)) == 0 && (n & 0x55555555) == n; }}; 🚀 运行结果：
🕔 复杂度分析：
- 时间复杂度： O ( 1 ) O(1) O(1)。
- 空间复杂度： O ( 1 ) O(1) O(1)。
题目来源：力扣。
放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我 leetCode专栏，每日更新！
