作者cuteSquirrel (可愛的小松鼠)
看板Math
標題Re: [其他] 二進位與二的平方
時間Mon Jun 10 01:25:10 2024
整數n 在 K進位的數字 可以寫成下列形式
n = Ci * K^i + Ci-1 * K^i-1 + ... + C1 * K^1 + C0 * K^0
令K=2 就變成二進位的表達式
n = Ci * 2^i + Ci-1 * 2^i-1 + ... + C1 * 2^1 + C0 * 2^0
如果n 是 power of 2，那係數裡面一定只會有一個是1
十進位 1 = 二進位 000 .... 001
十進位 2 = 二進位 000 .... 010
十進位 4 = 二進位 000 .... 100
...
2^i = 二進位 100 .... 000
如果是要用程式檢驗，可以用一個 AND運算子的小技巧來檢查
n & (n-1) 必等於0，如果 n 是 power of 2
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n <= 0:
return False
# note:
# power of 2 in binary = b' 1000 ... 0
# power of 2 minus 1 in binary = b' 0111 ... 1
# bitwise AND of n and (n-1) must be 0 if n is power of 2
return ( n & ( n-1 ) ) == 0
對應到 Leetcode #231 Power of Two 這題測驗題
※ 引述《sluggard (~Halcyon Days~)》之銘言：
: 今天看到一個解題的影片提到要快速知道一個數是否為2的平方數
: 可以把那個數轉為二進位，
: 然後在看轉成二進位後，是不是只有一個1
: 例如:
: 2^0 = 1 ==> 00001
: 2^1 = 2 ==> 00010
: 2^2 = 4 ==> 00100
: 2^3 = 8 ==> 01000
: 2^4 = 16 ==> 10000
: ....
: 轉成二進位時都只有一個1，
: 所以如果有一個數，要確認是否為二的平方數
: 就可以轉成二進位，然後看看是否只有一個1來做判斷，
: 感覺非常神奇，但我想請問這是怎麼推導出來的？
: 如果要證明，是要用數學歸納法？
: 謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.39.83 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1717953912.A.ABB.html
1F：推 sluggard : 非常謝謝您的解釋與回覆！還需要想一下表達式的部分 06/10 02:15
※ 編輯: cuteSquirrel (1.161.39.83 臺灣), 06/10/2024 13:05:42