342. 4的幂

发表于 分类于 阅读次数： Waline： 本文字数： 166 阅读时长 ≈ 1 分钟

考点

  • n & (n - 1)技巧
  • 掩码技巧

题解

1
2
3
4
5
6
class Solution {
	public:
		bool isPowerOfFour(int n) {
			return n > 0 && !(n & (n - 1)) && (n & 0x55555555);
		}
};

时间复杂度：\(O\left( 1 \right)\)

空间复杂度：\(O\left( 1 \right)\)

思路

4的幂，实际上就是2的幂次的平方；故而肯定大于零且只存在一个1比特位，满足这两个条件后继续找规律：

4的零次幂为0001

4的一次幂为0100

4的二次幂为0001 0000

4的三次幂为0100 0000

组合在一起就是0101 0101，十六进制表达即为55

故而制作掩码0x55555555与原数做与运算，不为0即为4的幂次