如何判断一个数是否是2的幂

这个问题有一个简单的技巧：

bool IsPowerOfTwo(ulong x)
{
return (x & (x - 1)) == 0;
}

注意，此函数将报告0的true，它不是2的幂。如果你想排除它，下面是方法：

bool IsPowerOfTwo(ulong x)
{
return (x != 0) && ((x & (x - 1)) == 0);
}

补充说明

首先是MSDN定义中的按位二进制&运算符：

二进制&运算符是为整数类型和bool预定义的。对于 整数类型，&计算其操作数的逻辑按位AND。 对于bool操作数，&计算其操作数的逻辑AND；那 是，当且仅当它的两个操作数都为真时，结果为真。

现在让我们来看看这一切是如何发挥作用的：

该函数返回布尔值（true/false）并接受一个传入参数，类型为无符号long（在本例中为x）。为了简单起见，让我们假设有人传递了值4并像这样调用函数：

bool b = IsPowerOfTwo(4)

现在我们用4替换x的每个出现：

return (4 != 0) && ((4 & (4-1)) == 0);

我们已经知道4！=0 evals为true，到目前为止还不错。但是：

((4 & (4-1)) == 0)

这当然可以翻译为：

((4 & 3) == 0)

什么是4&3？

4的二进制表示是100,3的二进制表示是011（记住&采用这些数字的二进制表示）。所以我们有：

100 = 4
011 = 3

想象一下，这些值像基本加法一样堆叠在一起。&运算符表示，如果两个值都等于1，则结果为1，否则为0。所以1 & 1 = 1、1 & 0 = 0、0 & 0 = 0和0 & 1 = 0。所以我们做数学：

100
011
----
000

结果只是0。所以我们回过头来看看我们的返回语句现在翻译成什么：

return (4 != 0) && ((4 & 3) == 0);

现在翻译为：

return true && (0 == 0);

return true && true;

我们都知道true && true只是true，这表明在我们的例子中，4是2的幂。

提出问题后，我想到了以下解决方案：

我们需要检查二进制数字中是否只有一个是1。因此，我们只需一次将数字右移一位，如果等于1则返回true。如果在任何时候我们遇到奇数（(number & 1) == 1），我们知道结果是false。这证明（使用基准测试）对于（大）真值比原始方法稍微快，对于假值或小值要快得多。

private static bool IsPowerOfTwo(ulong number)
{
while (number != 0)
{
if (number == 1)
return true;


if ((number & 1) == 1)
// number is an odd number and not 1 - so it's not a power of two.
return false;


number = number >> 1;
}
return false;
}

当然，格雷格的解决方案要好得多。

一些记录和解释这一点和其他一些旋转黑客的网站是：

• http://graphics.stanford.edu/~seander/bithacks.html
  （http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2）
• http://bits.stephan-brumme.com/
  （http://bits.stephan-brumme.com/isPowerOfTwo.html）

他们的祖父，《黑客的喜悦》by Henry Warren， Jr.：

• http://www.hackersdelight.org/

正如肖恩·安德森的页面解释的那样，表达式((x & (x - 1)) == 0)错误地表示0是2的幂。他建议使用：

(!(x & (x - 1)) && x)

来纠正这个问题。

return (i & -i) == i

private static bool IsPowerOfTwo(ulong x)
{
var l = Math.Log(x, 2);
return (l == Math.Floor(l));
}

bool IsPowerOfTwo(ulong x)
{
return x > 0 && (x & (x - 1)) == 0;
}

求给定的数字是否是2的幂。

#include <math.h>


int main(void)
{
int n,logval,powval;
printf("Enter a number to find whether it is s power of 2\n");
scanf("%d",&n);
logval=log(n)/log(2);
powval=pow(2,logval);


if(powval==n)
printf("The number is a power of 2");
else
printf("The number is not a power of 2");


getch();
return 0;
}

这里有一个简单的C++解决方案：

bool IsPowerOfTwo( unsigned int i )
{
return std::bitset<32>(i).count() == 1;
}

bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;

如果一个数字只包含1个设置位，它就是2的幂。我们可以使用这个属性和泛型函数countSetBits来确定一个数字是否是2的幂。

这是一个C++程序：

int countSetBits(int n)
{
int c = 0;
while(n)
{
c += 1;
n  = n & (n-1);
}
return c;
}


bool isPowerOfTwo(int n)
{
return (countSetBits(n)==1);
}
int main()
{
int i, val[] = {0,1,2,3,4,5,15,16,22,32,38,64,70};
for(i=0; i<sizeof(val)/sizeof(val[0]); i++)
printf("Num:%d\tSet Bits:%d\t is power of two: %d\n",val[i], countSetBits(val[i]), isPowerOfTwo(val[i]));
return 0;
}

我们不需要显式检查0是否为2的幂，因为它也为0返回False。

输出

Num:0   Set Bits:0   is power of two: 0
Num:1   Set Bits:1   is power of two: 1
Num:2   Set Bits:1   is power of two: 1
Num:3   Set Bits:2   is power of two: 0
Num:4   Set Bits:1   is power of two: 1
Num:5   Set Bits:2   is power of two: 0
Num:15  Set Bits:4   is power of two: 0
Num:16  Set Bits:1   is power of two: 1
Num:22  Set Bits:3   is power of two: 0
Num:32  Set Bits:1   is power of two: 1
Num:38  Set Bits:3   is power of two: 0
Num:64  Set Bits:1   is power of two: 1
Num:70  Set Bits:3   is power of two: 0

bool isPowerOfTwo(int x_)
{
register int bitpos, bitpos2;
asm ("bsrl %1,%0": "+r" (bitpos):"rm" (x_));
asm ("bsfl %1,%0": "+r" (bitpos2):"rm" (x_));
return bitpos > 0 && bitpos == bitpos2;
}

int isPowerOfTwo(unsigned int x)
{
return ((x != 0) && ((x & (~x + 1)) == x));
}

这真的很快。检查所有2^32个整数大约需要6分43秒。

return ((x != 0) && !(x & (x - 1)));

如果x是2的幂，则其唯一的1位位于位置n。这意味着x – 1在位置n有一个0。要了解原因，请回忆一下二进制减法的工作原理。当从x中减去1时，借用一直传播到位置n；位n变为0，所有较低的位都变为1。现在，由于x和x – 1没有1个共同的位，因此x & (x – 1)为0，而n0为真。

这是我设计的另一种方法，在这种情况下使用|而不是&：

bool is_power_of_2(ulong x) {
if(x ==  (1 << (sizeof(ulong)*8 -1) ) return true;
return (x > 0) && (x<<1 == (x|(x-1)) +1));
}

    bool IsPowerOfTwo(int n)
{
if (n > 1)
{
while (n%2 == 0)
{
n >>= 1;
}
}
return n == 1;
}

这是一个通用算法，用来找出一个数是否是另一个数的幂。

    bool IsPowerOf(int n,int b)
{
if (n > 1)
{
while (n % b == 0)
{
n /= b;
}
}
return n == 1;
}

示例

0000 0001    Yes
0001 0001    No

算法

1. 使用位掩码，将NUM变量除以二进制

2. IF R > 0 AND L > 0: Return FALSE

3. 否则，NUM成为非零的那个

4. IF NUM = 1: Return TRUE

5. 否则，转到步骤1

复杂度

时间~O(log(d))其中d是二进制位数

以下已接受答案的附录可能对某些人有用：

2的幂，当用二进制表示时，总是看起来像1后跟n个零，其中n大于或等于0。例如：

Decimal  Binary
1        1     (1 followed by 0 zero)
2        10    (1 followed by 1 zero)
4        100   (1 followed by 2 zeroes)
8        1000  (1 followed by 3 zeroes)
.        .
.        .
.        .

诸如此类。

当我们从这些数字中减去1时，它们变成0后面跟着n个，并且n与上述相同。例如：

Decimal    Binary
1 - 1 = 0  0    (0 followed by 0 one)
2 - 1 = 1  01   (0 followed by 1 one)
4 - 1 = 3  011  (0 followed by 2 ones)
8 - 1 = 7  0111 (0 followed by 3 ones)
.          .
.          .
.          .

诸如此类。

说到关键

当我们对数字x进行按位AND时会发生什么，这是一个 2的幂和x - 1？

#EYZ0的一个与x - 1的零对齐，#EYZ0的所有零与x - 1的零对齐，导致按位AND结果为0。这就是我们上面提到的单行答案是正确的。

进一步增加了上面接受的答案的美丽-

所以，我们现在有一个财产可供我们支配：

当我们从任何数字中减去1时，在二进制表示中，最右边的1将变成0，最右边的1左侧的所有零现在都将变成1。

这个属性的一个很棒的用途是找出-给定数字的二进制表示中存在多少个1？对给定整数x执行此操作的简短而甜蜜的代码是：

byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);

可以从上面解释的概念中证明的数字的另一个方面是"每个正数都可以表示为2的幂和吗？"。

是的，每个正数都可以表示为2的幂之和。对于任何数字，取其二进制表示。例如：取数字117。

The binary representation of 117 is 1110101


Because  1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have  117     = 64      + 32     + 16    + 0    + 4   + 0  + 1

对于2的任何幂，以下也成立。

n&（-n）==n

注意：n=0失败，所以需要检查它
这个工作的原因是：
-n是n的2s补码。-n将使n的最右边设置位的每一位与n相比翻转。对于2的幂，只有一个设置位。

改进@user134548的答案，没有位算术：

public static bool IsPowerOfTwo(ulong n)
{
if (n % 2 != 0) return false;  // is odd (can't be power of 2)


double exp = Math.Log(n, 2);
if (exp != Math.Floor(exp)) return false;  // if exp is not integer, n can't be power
return Math.Pow(2, exp) == n;
}

这适用于：

IsPowerOfTwo(9223372036854775809)

马克·格雷厄尔建议这个如果你有。NET Core 3，System. Runtime. Intrinsics. X86. PopCount相关链接

public bool IsPowerOfTwo(uint i)
{
return Popcnt.PopCount(i) == 1
}

单指令，比(x != 0) && ((x & (x - 1)) == 0)快，但便携性较差。

在C中，我测试了i && !(i & (i - 1)技巧并将其与__builtin_popcount(i)进行了比较，在Linux上使用gcc，并使用-mpopcnt标志以确保使用CPU的POPCNT指令。我的测试程序计算了0到2^31之间的整数的#，这些整数是2的幂。

起初我以为i && !(i & (i - 1)快了10%，尽管我在使用__builtin_popcount的反汇编中验证了POPCNT的使用。

然而，我意识到我已经包含了一个if语句，并且分支预测可能在位旋转版本上做得更好。我删除了if和POPCNT，结果更快，正如预期的那样。

结果：

Intel（R）Core（TM）i7-4771 CPU最大3.90GHz

Timing (i & !(i & (i - 1))) trick
30


real    0m13.804s
user    0m13.799s
sys     0m0.000s


Timing POPCNT
30


real    0m11.916s
user    0m11.916s
sys     0m0.000s

AMD Ryzen Threadripper 2950X 16核处理器最大3.50GHz

Timing (i && !(i & (i - 1))) trick
30


real    0m13.675s
user    0m13.673s
sys 0m0.000s


Timing POPCNT
30


real    0m13.156s
user    0m13.153s
sys 0m0.000s

请注意，在这里，Intel CPU似乎比AMD稍微慢一点，但具有更快的POPCNT；AMD POPCNT没有提供那么多的提升。

popcnt_testc：

#include "stdio.h"


// Count # of integers that are powers of 2 up to 2^31;
int main() {
int n;
for (int z = 0; z < 20; z++){
n = 0;
for (unsigned long i = 0; i < 1<<30; i++) {
#ifdef USE_POPCNT
n += (__builtin_popcount(i)==1); // Was: if (__builtin_popcount(i) == 1) n++;
#else
n += (i && !(i & (i - 1)));  // Was: if (i && !(i & (i - 1))) n++;
#endif
}
}


printf("%d\n", n);
return 0;
}

运行测试：

gcc popcnt_test.c -O3 -o test.exe
gcc popcnt_test.c -O3 -DUSE_POPCNT -mpopcnt -o test-popcnt.exe


echo "Timing (i && !(i & (i - 1))) trick"
time ./test.exe


echo
echo "Timing POPCNT"
time ./test-opt.exe

我看到很多答案都建议返回n&&！（n&（n-1）），但根据我的经验，如果输入值为负，它会返回假值。 我将在这里分享另一种简单的方法，因为我们知道两个数的幂只有一个设置位，所以简单地我们将计算设置位的数量，这将花费O（log N）时间。

while (n > 0) {
int count = 0;
n = n & (n - 1);
count++;
}
return count == 1;

查看此文章计数数。设置位

这是另一种方法来做到这一点以及

package javacore;


import java.util.Scanner;


public class Main_exercise5 {
public static void main(String[] args) {
// Local Declaration
boolean ispoweroftwo = false;
int n;
Scanner input = new Scanner (System.in);
System.out.println("Enter a number");
n = input.nextInt();
ispoweroftwo = checkNumber(n);
System.out.println(ispoweroftwo);
}
    

public static boolean checkNumber(int n) {
// Function declaration
boolean ispoweroftwo= false;
// if not divisible by 2, means isnotpoweroftwo
if(n%2!=0){
ispoweroftwo=false;
return ispoweroftwo;
}
else {
for(int power=1; power>0; power=power<<1) {
if (power==n) {
return true;
}
else if (power>n) {
return false;
}
}
}
return ispoweroftwo;
}
}

在这种方法中，您可以检查整数中是否只有1个设置位，并且整数>0（c++）。

bool is_pow_of_2(int n){
int count = 0;
for(int i = 0; i < 32; i++){
count += (n>>i & 1);
}
return count == 1 && n > 0;
}

如果数字是2的幂，则返回64个值（您可以在循环条件中更改它（“6”代表2^6是64）；

const isPowerOfTwo = (number) => {
let result = false;
for (let i = 1; i <= 6; i++) {
if (number === Math.pow(2, i)) {
result = true;
}
}
return result;
};


console.log(isPowerOfTwo(16));
console.log(isPowerOfTwo(10));

现在很容易进入。网络6。

using System.Numerics;


bool isPow2 = BitOperations.IsPow2(64); // sets true

这里是留档。

在. NET 6中有一个班轮

// IsPow2 evaluates whether the specified Int32 value is a power of two.
Console.WriteLine(BitOperations.IsPow2(128));            // True

我一直在阅读Random.nextInt（int绑定）的留档，并看到这段不错的代码，它检查参数是否为2的幂，上面写着（代码的一部分）：

if ((bound & -bound) == bound) // ie, bouns is a power of 2

我们来测试一下

for (int i=0; i<=8; i++) {
System.out.println(i+" = " + Integer.toBinaryString(i));
}


>>
0 = 0
1 = 1
2 = 10
3 = 11
4 = 100
5 = 101
6 = 110
7 = 111
8 = 1000
// the left most 0 bits where cut out of the output


for (int i=-1; i>=-8; i--) {
System.out.println(i+" = " + Integer.toBinaryString(i));
}


>>
-1 = 11111111111111111111111111111111
-2 = 11111111111111111111111111111110
-3 = 11111111111111111111111111111101
-4 = 11111111111111111111111111111100
-5 = 11111111111111111111111111111011
-6 = 11111111111111111111111111111010
-7 = 11111111111111111111111111111001
-8 = 11111111111111111111111111111000

你注意到什么了吗？
幂2数在正二进制和负二进制表示中具有相同的位，如果我们做逻辑AND，我们得到相同的数字：）

for (int i=0; i<=8; i++) {
System.out.println(i + " & " + (-i)+" = " + (i & (-i)));
}


>>
0 & 0 = 0
1 & -1 = 1
2 & -2 = 2
3 & -3 = 1
4 & -4 = 4
5 & -5 = 1
6 & -6 = 2
7 & -7 = 1
8 & -8 = 8

静态编程语言：

fun isPowerOfTwo(n: Int): Boolean {
return (n > 0) && (n.and(n-1) == 0)
}

或

fun isPowerOfTwo(n: Int): Boolean {
if (n == 0) return false
return (n and (n - 1).inv()) == n
}

inv反转此值中的位。

备注：
log2解决方案不要适用于大数，如536870912->

import kotlin.math.truncate
import kotlin.math.log2


fun isPowerOfTwo(n: Int): Boolean {
return (n > 0) && (log2(n.toDouble())) == truncate(log2(n.toDouble()))
}

有许多答案和发布的链接解释了为什么n & (n-1) == 0适用于2的幂，但我找不到任何关于为什么它不适用于2的非幂的解释，所以我添加这个只是为了完整性。

对于n=1（2^0=1），1&0=0，所以我们很好。

对于奇数n>1，至少有2个位为1（最左边和最右边）。现在n和n-1只会相差最右边的位，所以它们的&-sum至少在最左边有一个1，所以n & (n-1) != 0：

n:          1xxxx1  for odd n > 1
n-1:        1xxxx0
------
n & (n-1):  1xxxx0 != 0

现在，即使n不是2的幂，我们也至少有2个位为1（最左边和非最右边）。这里，n和n-1在最右边的1位之间会有差异，所以它们的&-sum在最左边的位上也至少有1：

        right-most 1 bit of n
v
n:          1xxxx100..00 for even n
n-1:        1xxxx011..11
------------
n & (n-1):  1xxxx000..00 != 0

我假设1是2的次方也就是2的0次方

 bool IsPowerOfTwo(ulong testValue)
{
ulong bitTest = 1;
while (bitTest != 0)
{
if (bitTest == testValue) return true;
bitTest = bitTest << 1;
}


return false;
}

试试这个使用mod 2的函数

def is_power_of_two(n):
if n == 0:
return False
while n != 1:
if n % 2 != 0:
return False
n = n // 2
return True