【Python3】【力扣题】231. 2 的幂

力扣题】231. 2 的幂"/>

【Python3】【力扣题】231. 2 的幂

【力扣题】题目描述：

此题：n为整数（32位有符号整数），x为整数。

2 的幂次方都大于0。若幂为负数，则0<n<1，n不为整数。

因此，n为正整数，x为0和正整数。

若二进制表示，则n的二进制只有1位是1，其余均为0。

最大2的幂为。

【Python3】代码：

1、解题思路：递归。依次n/2，判断余数是否为0，最终n为1，则n是2的幂。

知识点：递归：在函数中调用函数本身（需有退出条件，否则无限循环）。

class Solution:def isPowerOfTwo(self, n: int) -> bool:if n <= 0: return Falseif n == 1: return Trueif n % 2 == 1: return Falsereturn self.isPowerOfTwo(n / 2)

2、解题思路：循环。依次n/2，判断余数是否为0，最终n为1，则n是2的幂。

class Solution:def isPowerOfTwo(self, n: int) -> bool:if n <= 0: return Falsewhile n != 1 and n % 2 == 0:n = n / 2return n == 1 

3、解题思路：二进制表示。n的二进制只有1位为1。

（3-1）判断二进制中是否只有1位为1，若是，则n是2的幂。

知识点：bin(...)：转为二进制字符串，即“0bxxx”。

              序列.count(...)：统计指定元素在序列（字符串、列表等）中有多少个。

class Solution:def isPowerOfTwo(self, n: int) -> bool:return n > 0 and bin(n).count("1") == 1

（3-2）二进制与运算。

二进制与运算：两个二进制，相对应的每一位进行与运算。

1 & 1 = 1，1 & 0 = 0，0 & 0 = 0

① n 和 (n-1) 进行二进制与运算，若结果为0，则n是2的幂。

例如：假设8位二进制，最高位为符号位。n=8，二进制00001000，n-1为00000111，00001000&00000111=00000000。

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

② n 和 -n 进行二进制与运算，若结果为n，则n是2的幂。

-n的二进制表示：n的补码（反码+1），即（有符号位）最高位符号位不变，其余位全部取反再加1（即最高位不变，最低位的1以后不变，最高位和最低位1之间的位取反）。

例如：假设8位二进制，最高位为符号位。n=8，二进制00001000，-n为01111000，00001000&01111000=00001000。

class Solution:def isPowerOfTwo(self, n: int) -> bool:return n > 0 and (n & -n) == n

4、解题思路：范围是32位有符号整数，将二进制1依次左移一位，判断是否与n相等，若是，则n是2的幂。

知识点：range(31)：从0到30的数组（不含31），即0、1、2...30。【最高位为符号位】

class Solution:def isPowerOfTwo(self, n: int) -> bool:for i in range(31):if n == (1 << i):return Truereturn False

5、解题思路：判断是否是最大2的幂的约数（即能把n整除），若是，则n是2的幂。

整数a除以整数b(b≠0)，除得商为整数，没有余数，则a是b的倍数，b是a的约数。

 知识点：2 ** 30：。

               1 << 30：左移，即1左移30位，为。

class Solution:def isPowerOfTwo(self, n: int) -> bool:return n > 0 and (2 ** 30) % n == 0# 或者return n > 0 and (1 << 30) % n == 0

6、解题思路：math模块log2()方法。判断结果是否是integer整数。

知识点：math.log2(...)：返回以2为底的对数。结果是浮点数。

              int(...)：转为整数。

              float.is_integer()：判断浮点数是否是integer整数。

例如：math.log2(8) 结果为3.0。【3.0是integer整数，和3的值相等。而3.1不是integer整数】

class Solution:def isPowerOfTwo(self, n: int) -> bool:import mathreturn n > 0 and math.log2(n) == int(math.log2(n))# 或者return n > 0 and math.log2(n).is_integer()