LeetCode:Power of Four

Posted on In Disqus:

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);
        }
    };