轉載自?玻璃貓 程序員小灰

?
?
?
?
小灰陷入回憶當中。。。。?
?
?
?
題目：實現一個方法，判斷一個正整數是否是2的乘方（比如16是2的4次方，返回True；18不是2的乘方，返回False）。要求性能盡可能高。?
?
?
解法一：?
創建一個中間變量Temp，初始值是1。然后進入一個循環，循環中每次讓Temp和目標整數比較，如果相等，則說明目標整數是2的乘方；如果不相等，則讓Temp增大一倍，繼續循環比較。當Temp大于目標整數時，說明目標整數不是2的乘方。

如果目標整數的大小是N，則此方法的時間復雜度是O（LogN）。?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
解法二：?
非常有趣也非常簡單的解法。因為2的乘方都符合一個規律，即 N&N-1 等于 0，所以直接用這個規律判斷即可。該算法時間復雜度是O（1）。?
?
?
?
思考題：?
實現一個方法，求出一個正整數轉換成二進制后的數字“1”的個數。要求性能盡可能高。?

哈哈哈，這個思考題挺簡單的，我的第一個想法很簡單，利用移位運算，在while判斷中，如果滿足條件則讓count++,最后輸出即可。第二個想法是利用上面的位運算，每當進行一次上面的位運算，我們總是可以將最右邊的1化為0，所以在while中判斷，滿足條件則count++ 。

代碼：?
int sum(int n)?
{ int count = 0;?
while (n != 0)?
{?
n = n & (n - 1);?
count++;?
}?
}?
return count;?
有興趣的讀者朋友歡迎留言探討最優解哦

?

總結

以上是生活随笔為你收集整理的漫画算法：判断2的乘方的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。