Skip to content

Latest commit

 

History

History
206 lines (147 loc) · 3.44 KB

File metadata and controls

206 lines (147 loc) · 3.44 KB
comments difficulty edit_url tags
true
简单
位运算
递归
数学

English Version

题目描述

给你一个整数 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

 

提示:

  • -231 <= n <= 231 - 1

 

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

解法

方法一:位运算

$\texttt{n&amp;(n-1)}$ 可将最后一个二进制形式的 $n$ 的最后一位 $1$ 移除,若移除后为 $0$,说明 $n$$2$ 的幂。

Python3

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

Java

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

C++

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

Go

func isPowerOfTwo(n int) bool {
	return n > 0 && (n&(n-1)) == 0
}

TypeScript

function isPowerOfTwo(n: number): boolean {
    return n > 0 && (n & (n - 1)) === 0;
}

JavaScript

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

方法二:lowbit

$\texttt{n&amp;(-n)}$ 可以得到 $n$ 的最后一位 $1$ 表示的十进制数,若与 $n$ 相等,说明 $n$$2$ 的幂。

注意:要满足 $n$$2$ 的幂次方,需要保证 $n$ 大于 $0$

Python3

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

Java

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

C++

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

Go

func isPowerOfTwo(n int) bool {
	return n > 0 && n == (n&(-n))
}

TypeScript

function isPowerOfTwo(n: number): boolean {
    return n > 0 && (n & (n - 1)) === 0;
}

JavaScript

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