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?

题目非常easy， 推断一个数是否是 4 的 N 次方。

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

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

bool isPowerOfFour(int num)

{

    if(num == 1) return true;

    if(num <= 0) return false;

    if(num & 0x03) return false;

    return isPowerOfFour(num / 4);

}

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

bool isPowerOfFour(int num)

{

    if(num < 0) return false;

    do

    {

        if(num == 1) return true;

        if(num & 3) return false;

        num = num >> 2;

    }while (num);

    return false;

}

假设不用循环和递归。也是能够做的。比方穷举全部 4 的 N 次方。

尽管这个代码看起来非常丑陋，可是确实也满足题目的要求。

bool isPowerOfFour(int num)

{

    switch(num)

    {

    case 0x01:

    case 0x04:

    case 0x10:

    case 0x40:

    case 0x100:

    case 0x400:

    case 0x1000:

    case 0x4000:

    case 0x10000:

    case 0x40000:

    case 0x100000:

    case 0x400000:

    case 0x1000000:

    case 0x4000000:

    case 0x10000000:

    case 0x40000000:

        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 <= 0) return false;

    if(num & (num - 1)) return false; // 先推断是否是 2 的 N 次方

    if(num & 0x55555555) return true; // 再将不是 4 的 N 次方的数字去掉

    return false;

}