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