快捷搜索:

LT简单题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

方法一:二进制表示(C++代码)

分析:一个数 n 是 2 的幂,当且仅当 n 为正整数,且其二进制表示只含一位 1。

class Solution {

public:

bool isPowerOfTwo(int n) {

return n > 0 && (n & (n - 1)) == 0; //n & (n - 1)为去掉n的最低位的1

}

};

class Solution {

public:

bool isPowerOfTwo(int n) {

return n > 0 && (n & (-n)) == n; //n & (-n)为取n的最低位的1

}

};

    时间复杂度:O(1) 空间复杂度:O(1)

方法二:判断是否为最大 2 的幂的约数(C++代码)

class Solution {

private:

static constexpr int BIG = 1 << 30;

public:

bool isPowerOfTwo(int n) {

return n > 0 && BIG % n == 0;

}

};

    时间复杂度:O(1) 空间复杂度:O(1)
经验分享 程序员 职场和发展