LeetCode 第 342 题（Power of Four）

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 的 N 次方。

难点在于后面的附加条件：不能用循环和递归。

首先先给个用递归的解法。

bool isPowerOfFour(int num)
{
    if(num == ) return true;
    if(num <= ) return false;
    if(num & ) return false;

    return isPowerOfFour(num / );
}
           

然后再给一个用循环的解法：

bool isPowerOfFour(int num)
{
    if(num < ) return false;
    do
    {
        if(num == ) return true;
        if(num & ) return false;
        num = num >> ;
    }while (num);
    return false;
}
           

如果不用循环和递归，也是可以做的。比如穷举所有 4 的 N 次方。虽然这个代码看起来很丑陋，但是确实也满足题目的要求。

bool isPowerOfFour(int num)
{
    switch(num)
    {
    case :
    case :
    case :
    case :
    case :
    case :
    case :
    case :
    case :
    case :
    case :
    case :
    case :
    case :
    case :
    case :
        return true;
    default:
        return false;
    }
}
           

讲了这么多，该说说正题了。这个题目其实考察的是这么一个小知识点。 一个数 num，如果是 2 的 N 次方，那么有：

num & (num - 1) = 0

一个数 num 如果是 4 的 N 次方必然也是 2 的 N 次方。所以可以先判断 num 是否是 2 的 N 次方。然后再将 2 的 N 次方中那些不是 4 的 N 次方的数去掉。因此就有了下面的代码。

bool isPowerOfFour(int num)
{
    if(num <= ) return false;
    if(num & (num - )) return false; // 先判断是否是 2 的 N 次方
    if(num & ) return true; // 再将不是 4 的 N 次方的数字去掉
    return false;
}