【LeetCode】 231. Power of Two

Description

Given an integer, write a function to determine if it is a power of two.

給予一正整數，寫一函式判斷它是否為二的冪次方。

Example:

Example 1:

Input: 1
Output: true 
Explanation: 20 = 1


Example 2:

Input: 16
Output: true
Explanation: 24 = 16


Example 3:

Input: 218
Output: false

Solution

• 最先想到是利用二進位制中，二的冪次方會有的特性：
  • 1 = 1、2 = 10、4 = 100、8 = 1000…
  • 最高位元為1，其餘為零。
• 所以我就用了一個迴圈從最低位元去判斷，一路檢查至最高位元。
  • 利用& 1去得到最低位元；利用>> 1捨棄最低位元。
  • 用一個flag去紀錄是否出現過1：
    • 如果出現過1，判斷是否為最高位元了。
    • 如果每一位元都跑過了，回傳flag。

---

• 寫完之後看了一下討論區，果然有非常精簡的寫法。
• 基本概念和上面一樣，換成二進制去思考，只是它換了一個方法去判斷是否只有最高位元為1這件事情：n & (n - 1)
• 當你只有最高位元是1的時候遇到減1，必定會需要連環借位，因而導致整組數字0 1相反。
• 因為bool除了0為false其餘皆為true，因此只須回傳n & (n - 1)和n > 0即可。

Code

• 方法一

class Solution {
public:
    bool isPowerOfTwo(int n) {
        bool f = false;
        while(n != 0)
        {
            if(f)
                return false;
            else
                f = n & 1;
            n = n >> 1;        
        }
        return f;
    }
};

• 方法二

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

tags: LeetCode C++