一起学算法-231. 2 的幂

时间:2021-6-12 作者:qvyue

一、题目

LeetCode-231. 2 的幂
链接:https://leetcode-cn.com/problems/power-of-two/

难度:简单
给你一个整数n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false 。

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

示例 1:
输入:n = 1
输出:true
解释:2^0 = 1

示例 2:
输入:n = 16
输出:true
解释:2^4 = 16

示例 3:
输入:n = 3
输出:false

示例 4:
输入:n = 4
输出:true

提示:
-2^31

二、解题思路

如果n = 2^x且 x为自然数(即 n为 2 的幂),则一定满足以下条件:

  1. 恒有 n & (n – 1) == 0,因为n 二进制最高位为 1,其余所有位为 0;
    n – 1二进制最高位为 0,其余所有位为 1;
  2. 一定满足 n > 0。

因此,通过 n > 0 且 n & (n – 1) == 0 即可判定是否满足 n = 2^x。

2^x n n-1 n&(n-1)
2^0 0001 0000 (0001) & (0000) == 0
2^1 0010 0001 (0010) & (0001) == 0
2^2 0100 0011 (0100) & (0011) == 0
2^3 1000 0111 (1000) & (0111) == 0

三、实现过程

c++

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

PHP

class Solution {

    /**
     * @param Integer $n
     * @return Boolean
     */
    function isPowerOfTwo($n) {
        return $n > 0 && ($n & ($n - 1)) == 0;
    }
}

JavaScript

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function(n) {
        return n > 0 && (n & (n - 1)) == 0;
};

四、小结

  1. 时间复杂度:O(1)
  2. 空间复杂度:O(1)
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。