231. Power of Two

今天我们一起挑战leetcode第231题Power of Two！

题目

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

Example 1:
Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:
Input: n = 16
Output: true
Explanation: 24 = 16

Example 3:
Input: n = 3
Output: false

Example 4:
Input: n = 4
Output: true

Example 5:
Input: n = 5
Output: false

今天这题要求也是相对单纯，题目想要我们检测他给我们的数，是否为2的幂次方，也就是包和2的0次方、2的1次方、2的2次方......。如果是，回传True，否则回传Flase。

decimal to binary and check

这题我们可以利用二进制来检验某一整数是否为二的幂，因为我们知道转换成二进制後，如果某个数是二的幂，那麽必然在二进制的表达中，只会有也恰好会有某一位数出现1，其余皆是零，才会是二的幂。例如2^3=8以二进制表示会是1000，64就会是1000000，而2^0=1，在二进制中也会是1。

根据上述方法，我们可以先把题目给我们的整数转换成二进制的字串，接着通过回圈走访每个数，如果走访完恰好看到只有某一位出现1，我们就能得知此数是二的幂。

以下是python的程序码

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n < 1: return False  # 负数不可能是2的幂，排除例外
        n = bin(n)  # python内建方法bin可从整数转换至二进制
        count = 0  # 计算看到几次1
        for i in n[2:]:
            if i == "1":
                count += 1
        return count == 1  # 如果恰好只有一个就会传true

以下是C++的程序码，我们透过自建的方法来达到十进制转二进制，整体思路与上述解法相同。

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n < 1)
            return false;
        string bins = toBinary(n);
        int count=0;
        for(char& c : bins) {
            if(c == '1')
                count++;
        }
    return count == 1;
    }
private:
    string toBinary(int n){
        string bins;
        while(n != 0){
            bins += (n % 2 == 0 ? "0": "1");
            n /= 2;
        }
    return bins;
    }
};