frendguo's blog

【LeetCode】342. Power of Four

原文地址:https://leetcode.com/problems/power-of-four/#/description

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

这类题,首先需要找到4 的幂 有什么共同点。分析发现,4 的幂的二进制中只能有一个 ‘1’ ,而且 1 后面的 0 的个数必须是偶数。于是可以开始写代码了:

static bool IsPowerOfFour(int num)
{
	if (num == 0) return false;
	if (num == 1) return true;

	int mask = 1;
	int n = 0; 
	while ((mask & num) == 0)
	{
		++n;
		mask <<= 1;
	}

	return n > 0 && (mask == num) && (n & 1) == 0;
}

然后 已提交,居然都排出界面了😂

于是继续优化,然后想起了 n & (n - 1) 可以去掉最后一个 1 ,而我们需要的数里面只有一个 1 ,于是便有 不满足 (n & (n - 1)) == 0 的都不是满足要求的。

在到 1 后面 0 的个数是偶数下手,既然是偶数个 0 ,那么 1 的位置就可以确定在大致范围了,那么就有 (n & 0x55555555) != 0。

再加上 n 肯定是大于 0 的,1 除外。于是就有下面的代码了:

static bool IsPowerOfFour(int num)
{
	return  num == 1 || (num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555) != 0);
}

超级简单,一行搞定~

Happy Coding!o(* ̄▽ ̄*)o

Add comment

Loading