作者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/cn.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