极客教程JavaScript 来检查给定的数字是否是2的幂
给定一个正整数 n ，编写一个函数来判断它是否是2的幂
示例:
Input: n = 4
Output: Yes
Explanation: 22 = 4
Input: n = 32
Output: Yes
Explanation: 25 = 32
解决问题的方法如下：
一种简单的方法是将数字的对数以2为底取对数，如果得到一个整数，则该数字是2的幂。
示例： 下面是上述方法的实现：
Javascript
<script>
function isPowerOfTwo(n) {
if (n == 0)
return false;
return parseInt((Math.ceil((Math.log(n) / Math.log(2)))))
== parseInt((Math.floor(((Math.log(n) / Math.log(2))))));
}
// Driver Code
if (isPowerOfTwo(31))
console.log("Yes");
else
console.log("No");
if (isPowerOfTwo(64))
console.log("Yes");
else
console.log("No");
</script>
输出：
No
Yes
时间复杂度: O(1)。
辅助空间: O(1)。
使用除法运算符确定一个给定数字是否是2的幂次方:
要解决这个问题，请遵循以下思路:
另一种解决方案是不断将数字除以二，即迭代地执行 n = n/2。在任何迭代中，如果 n%2 不为零且 n 不为1，则 n 不是2的幂次方。如果 n 变为1，则它是2的幂次方。
示例 1: 以下是上述方法的实现:
JavaScript
<script>
function isPowerOfTwo(n) {
if (n == 0)
return 0;
while (n != 1) {
if (n % 2 != 0)
return 0;
n = n / 2;
}
return 1;
}
isPowerOfTwo(31) ? console.log("Yes") : console.log("No");
isPowerOfTwo(64) ? console.log("Yes") : console.log("No");
</script>
输出：
No
Yes
时间复杂度： O(log N).
辅助空间： O(1).
示例2： 以下是上述方法的递归实现：
Javascript
<script>
function powerOf2(n) {
// base cases
// '1' is the only odd number
// which is a power of 2(2^0)
if (n == 1)
return true;
// all other odd numbers are
// not powers of 2
else if (n % 2 != 0 ||
n == 0)
return false;
// recursive function call
return powerOf2(n / 2);
}
// Driver Code
//True
var n = 64;
//False
var m = 12;
if (powerOf2(n) == true)
console.log("True" + "\n");
else console.log("False" + "\n");
if (powerOf2(m) == true)
console.log("True" + "\n");
else
console.log("False" + "\n");
</script>
输出：
True
False
时间复杂度： O(log N)。
辅助空间： O(log N)。
通过检查置位位数来判断给定的数是否为2的幂：
解决该问题的思路如下：
所有的2的幂都只有一个置位位。因此计算置位位数，如果得到1，则该数是2的幂。请参阅 计算整数中的置位位 以计算置位位数。
示例： 上述方法的实现如下：
Javascript
<script>
function isPowerofTwo(n) {
let cnt = 0;
while (n > 0) {
if ((n & 1) == 1) {
cnt++; // if n&1 == 1 keep incrementing cnt
// variable
}
n = n >> 1; // keep dividing n by 2 using right
// shift operator
}
if (cnt == 1) {
// if cnt = 1 only then it is power of 2
return true;
}
return false;
}
// Driver code
if (isPowerofTwo(30) == true)
console.log("Yes");
else
console.log("No");
if (isPowerofTwo(128) == true)
console.log("Yes");
else
console.log("No");
</script>
输出：
No
Yes
时间复杂度： O(N)。
辅助空间： O(1)。
使用AND(&)运算符来判断一个给定的数是否是2的幂：
解决这个问题的思路如下：
如果我们将一个2的幂减去1，那么在唯一的设置位之后的所有未设置的位都将变为设置，设置位则变为未设置。
例如，对于4（100）和16（10000），我们在减去1之后得到如下结果：
3 –> 011
15 –> 01111
因此，如果一个数n是2的幂，则n和n-1的按位与运算结果将为零。根据n&(n-1)的值，我们可以判断n是否是2的幂。当n为0时，表达式n&(n-1)将不起作用。为了处理这种情况，我们的表达式将变为n&(!n&(n-1))。
示例： 下面是上述方法的实现：
Javascript
<script>
function isPowerOfTwo(x) {
/* First x in the below expression is
for the case when x is 0 */
return x != 0 && ((x & (x - 1)) == 0);
}
// Driver method
console.log(isPowerOfTwo(31) ? "Yes" : "No");
console.log((isPowerOfTwo(64) ? "Yes" : "No"));
</script>
输出:
No
Yes
时间复杂度： O(1)。
辅助空间： O(1)。
使用AND(&)和NOT(~)操作符确定给定数是否是2的幂次方：
解决该问题的方法如下：
另一种方法是使用逻辑来找到给定数的最右边的置位位，然后检查 (n & (~(n-1))) 是否等于 n 或不等于
示例： 下面是以上方法的实现：
Javascript
<script>
function isPowerofTwo(n) {
if (n == 0)
return false;
if ((n & (~(n - 1))) == n)
return true;
return false;
}
if (isPowerofTwo(30) == true)
console.log("Yes");
else
console.log("No");
if (isPowerofTwo(128) == true)
console.log("Yes");
else
console.log("No");</script>
输出：
No
Yes
时间复杂度： O(1)。
辅助空间： O(1)。
使用Brian Kernighan算法判断给定数字是否为2的幂：
解决这个问题的思路如下：
我们知道，2的幂次方只有一个比特位是1，因此当我们将待检测的数字与比它小1的数字按位与时，结果将为0。
例如：4可以表示为（2 ^ 2），
（4＆3）=0或二进制形式（100＆011 = 0）
示例： 下面是上述方法的实现：
Javascript代码
<script>
function isPowerofTwo(n) {
return (n != 0) && ((n & (n - 1)) == 0);
}
/* Function to check if x is power of 2*/
if (isPowerofTwo(30)) {
console.log("Yes");
}
else {
console.log("No");
}
if (isPowerofTwo(128)) {
console.log("Yes");
}
else {
console.log("No");
}
输出:
No
Yes
时间复杂度： O(1)。
辅助空间： O(1)。