【Leetcode】231. Power of two

來源: Leetcode
難度: easy
題目: 231. Power of two

解法一(遞迴)

檢查一個數字 n 是不是 2 的 x 次方，就是看他有沒有 1 和 2 以外的因數。所以只要把 n 不斷除以 2 ，看看最後結果是不是 1 就知道了。剛好之前在 CS50 課程有學過遞迴的概念，這題剛好可以拿來用!

要使用遞迴必須要設定停止條件，要不然函式會無止境的呼叫自己繼續執行下去。這邊設定的停止條件是 n === 1，也就是上層傳進來的參數 (n / 2) === 1 (除了 2 之外只有 1 這個因數)。另外檢查 n 為非正整數情況須一律傳回 false 。

var isPowerOfTwo = function(n) {
  if (n <= 0) return false
  if (n === 1) return true
  return isPowerOfTwo(n / 2)
}

解法二(位元運算子)

解題方式參考: tmleyncodes 分享的題解

這題因為是檢查 2 的次方，所以還有另一種特別的解法。電腦語言是用「二進位」來書寫的，所以可以利用二進位的特性，使用位元運算子來解題。

數字	二進位
8	1000
7	0111
& 結果	0000

位元運算子 & 會回傳兩個運算元對於每個 bit 做 AND 的結果。如下表表示， & 會比較每一個 bit ，如果兩者都是 1 會回傳 1，如果有一方不是 1 則會回傳 0。

var isPowerOfTwo = function(n) {
    if (n <= 0) return false
    return (n & (n - 1)) === 0
}

文章內容如有錯誤，歡迎留言討論！