題目:

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 == 2^x.

給定一數,判斷它是否是2的次方

這題有許多解法,我們先從最直觀的開始

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n<=0: #0和負數不在討論範圍
            return False
            
        while n%2==0:
            n=n/2
        return n==1

將一數不斷除二直到不能整除
看最後結果是不是1,就知道該數是不是2的次方了
最後執行時間36ms(faster than 87.16%)

也有位元運算的解法

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        count=0
        
        while n>0:
            count=count+(n&1)
            n=n>>1
        return count==1

我們可以發現2次方數在二進位表示時有共同的性質
1(1),10(2),100(4),1000(8),10000(16)......
那就是只有一位是1,其餘都是0
所以我用191.的方法,用&1和>>數出該數二進位表示有幾個1
若只有一個1,則該數是2的次方
最後執行時間27ms(faster than 98.57%)

不用迴圈的解法也是有的

import math
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n<=0:
            return False
        return (math.log10(n)/math.log10(2))%1==0

import math讓我們可以用log函數
透過log的性質,我們可以知道log2(2的次方數)會是整數
且log10(n)/log10(2)=log2(n)
所以我們只要計算log10(n)/log10(2)再用%1判斷是不是整數即可
最後執行時間33ms(faster than 92.75%)

那我們下題見