# 【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++`