leetcode_ Power of Four

Problem description

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?

Credits:
Special thanks to @yukuairoy for adding this problem and creating all test cases.

Ideas

2 The power of contains 4 The power of , in other words 4 The power of must be 2 Power of Dan 2 The power of is not necessarily 4 The power of . Then you might as well calculate whether the input is 2 The power of , when 2 And then judge whether it is 4 The power of .

To judge whether the input is 2 The power of is simple , Just judge whether there is only 1 individual 1 that will do . That is, assume that the input is n, If n&(n-1)==0, be n Namely 2 The power of .

So how to judge whether it is 4 Power of ？ Take a chestnut .2 and 8 The binary code of is (0010) and (1000) These two numbers are 2 Power of, but not 4 The power of . and 4 and 16 The binary code of is (0100) and (10000). You can find a rule ,4 In the binary code of the power of 1 Will appear on odd digits （ From right to left ）, Instead of 4 In the binary code of the power of 1 Will appear in even digits . That is to say if 1 When it appears on odd digits, it is 4 The power of . To judge , A mask can be introduced (1010101010101010101010101010101) That is to say 0x55555555. then n And this mask bitwise AND , If the result is not 0, Namely 4 The power of .

Realization

class Solution {
public:
    bool isPowerOfFour(int num) {
        if(num<=0)
            return false;
        return ((num&(num-1))==0 && (num&0x55555555));
    }
};