leetcode342——Power of Four（C++），leetcode342four

leetcode342——Power of Four（C++），leetcode342four

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.

個人博客：http://www.cnblogs.com/wdfwolf3/

這道題本身沒有難度，這裡只是介紹兩種思路，當我們判斷出它二進制只有1個1的時候，即必為2的冪時，如何進一步判斷它是不是4的冪。

1.  8ms

class Solution {
public:
    bool isPowerOfFour(int num) {
        if(num<=0)
            return false;
        if((num&(num-1))!=0)          //判斷是不是2的冪，或者說二進制是否只有1個1
            return false;
        if((num-1)%3==0)　　　　　　　　//判斷這個1的位置，來判斷是不是4的冪
            return true;
        return false;
    }
};

為什麼要利用num-1後能不能整除3判斷，很多人各種數學證明，其實從二進制角度很好理解證明。num減1後得到的數字末尾全為1，3的二進制是……11，那麼從最低位算起有偶數個1的數字都能整除3，奇數個不能整除。自然4的冪減1後為偶數個1。

2.  8ms

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

這裡利用了一個數字0x55555555，它是01010101……01010101。4的冪二進制中的1的位置一定出現在0x55555555二進制1的位置，那麼按位與操作後等於0說明位置不對，那就不是4的冪。