342. 4的幂(简单)
方法一:二进制
思路
- 首先考虑一个数字是不是 2 的整数次方:如果一个数字 n 是 2 的整数次方,那么它的二进制一定是
0...010...0
这样的形式,将它和 -n 按位与的结果一定是它本身。如果n & (-n) == n
,说明这个数字是 2 的次方。 - 如果这个数字还是 4 的次方,那么 1 的位置一定是偶数(左边第一位数字的下标为 0),因此我们可以判断最高位的 1 的位置是不是偶数,如果是的话,说明这个数字是 4 的次方。
代码
class Solution {
public:bool isPowerOfFour(int n) {if(n <= 0 || (n & (-n)) != n) return false;int pos = 0;while(n){if((n & 1) && pos % 2 == 0) return true;n >>= 1;pos ++;}return false;}
};
方法二:二进制优化
思路
- 方法二和方法一思路差不多,但是方法一在判断最高位 1 的时候用到了循环,我们可以将其简化。
- 在确定了一个数是 2 的次方之后,如果它仍然是 4 的次方,那么 1 的位置一定是偶数(左边第一位数字的下标为 0)。由于题目保证了给定数字 n 一定是 32位的有符号整数,因此我们可以构造一个数 mask,它的所有偶数位都是 0 ,奇数位都是 1,即
1010...1010
,也就是0xaaaaaaaa
,如果将 mask 和 n 按位与,得到 0,说明这个数是 4 的次方。
代码
class Solution {
public:bool isPowerOfFour(int n) {return n > 0 && (n & (-n)) == n && (n & 0xaaaaaaaa) == 0;}
};