0%

LeetCode: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?

方法一

  • 循环
1
2
3
4
5
6
7
bool isPowerOfFour(int num) {
if (num <= 0) return false;
while ((num % 4) == 0) {
num /= 4;
}
return num == 1;
}
1
2
3
4
5
6
7
bool isPowerOfFour(int num) {
if (num <= 0) return false;
while ((num & 0x3) == 0) {
num /= 4;
}
return num == 1;
}

方法二

  • 位运算。
    要求:
  1. 最高位为1,其余全部为0.num&(num-1)可以判断出左边第一位为1,后面全为零的数。
  2. 1的位置在奇数位。用0 != (num & 0x55555555)判断。注意$1=4^0$。
    1
    2
    3
    4
    5
    6
    class Solution {
    public:
    bool isPowerOfFour(int num) {
    return num > 0 && 0 == (num & (num-1)) && 0 != (num & 0x55555555);
    }
    };