leetcode：231. 2 的幂

题目

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

提示：

  • [简单] 231. 2 的幂 - 图1

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

示例：

  1. 输入：n = 1
  2. 输出：true
  3. 解释：20 = 1
  1. 输入：n = 16
  2. 输出：true
  3. 解释：24 = 16
  1. 输入：n = 3
  2. 输出：false
  1. 输入：n = 4
  2. 输出：true
  1. 输入：n = 5
  2. 输出：false

解答 & 代码

如果一个数是 2 的幂，那么其二进制表示中只会有一个 1，例如：

数 1 2 4 8 16 32
二进制表示 1 10 100 1000 10000 100000

而 n & (n-1) 会消除整数 n 的二进制表示的最后一个 1。

因此，只需要判断一个数 n 是否是正数，且 (n & (n - 1)) == 0 即可。

  • 注意 (n & (n - 1)) == 0 的括号一定要加上，否则 (n - 1) == 0 的运算优先级高于 & 

    1. class Solution {
    2. public:
    3.   bool isPowerOfTwo(int n) {
    4.       return n > 0 && ((n & (n - 1)) == 0);
    5.   }
    6. };

    复杂度分析：

  • 时间复杂度 O(1)：

  • 空间复杂度 O(1)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：5.5 MB, 在所有 C++ 提交中击败了 99.93% 的用户