LeetCode 342. Power of Four

题目

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

Example 1:

Input: 16
Output: true
Example 2:

Input: 5
Output: false

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

解析

题目中要求不用循环来解决问题，那这个题就是一道纯数学题了。
首先，如果是4的幂，那么他也是2的幂；
其次，如果n是4的幂，则n-1一定可以被3整除，即n-1是3的倍数。

1. 第一个命题就显而易见了，4=2x2。但是，判断一个数是否为2的幂数，可以用位运算来做，如果n为2的幂数，那么n一定为10000...这种形势，那么n-1则为011111，很显然，n&n-1=0。
2. 第二个命题的证明可以使用数学归纳法。

证明：
当n=4时，显然(n-1)%3=0，命题成立；
假设当n=m时，m为4的幂数，m-1可以被3整除，即证明当n=4m时，4m-1可以被3整除。
(4m-1) % 3 = (4m-4+3) % 3 
           = (4(m-1) + 3) % 3 
           = 4(m-1) % 3 + 3 % 3        // 取余运算满足分配率
           = 0
命题得证

代码（C语言）

bool isPowerOfFour(int num) {
    if (num < 0)
        return false;
    
    return ((num & (num - 1)) == 0) && (num - 1) % 3 == 0;
}