[231][简单] 2的幂

题目描述

231. 2 的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：20 = 1

示例 2：

输入：n = 16
输出：true
解释：24 = 16

示例 3：

输入：n = 3
输出：false

示例 4：

输入：n = 4
输出：true

示例 5：

输入：n = 5
输出：false

提示：

• -231 <= n <= 231 - 1

进阶：你能够不使用循环/递归解决此问题吗？

解题思路

二进制表示

2的幂

一个数 n 是 2 的幂, 当且仅当 n 是正整数, 并且 n 的二进制表示中仅包含 1 个 1.

n & (n - 1)

这种方法思路可以概括为: 找到最低位的1, 将这个1消除后, 剩余的二进制对应的数值是否为0.

n - 1的操作, 会将n中最低位的1置为0, 然后这个1之前的所有位置(到最低位的所有位置)都会被置为1, 因此n & (n - 1)的结果, 会将包括n中原来最低位的1所在位置之内的, 所有低位全部置为0, 达到了消除最低位1的目的.

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

n & (-n)

-n是n的相反数, 负数在二进制中是按照补码规则在计算机中存储的, -n的二进制表示为n的二进制表示的每一位取反再加上1. 因此n中最低位的1取反为0, 这之前的位原来都是0, 取反之后都是1. 加上1之后, 这些位置都会进位变成0, 原来最低位的1又会变为1.

因此如果n中只有一个1, n & (-n)的结果还应为n.

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