如何检查一个数字是否是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 预定义的。对于整数类型， & 计算其操作数的逻辑按位与。对于 bool 操作数， & 计算其操作数的逻辑与；也就是说，当且仅当它的两个操作数都为真时，结果才为真。

现在让我们看看这一切是如何发生的：

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

bool b = IsPowerOfTwo(4)

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

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

好吧，我们已经知道 4 != 0 评估为真，到目前为止一切都很好。但是关于：

((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 语句现在翻译成什么：

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

现在翻译为：

return true && (0 == 0);

return true && true;

我们都知道 true && true 只是 true，这表明对于我们的示例，4 是 2 的幂。

---

一些记录和解释这个和其他一些小技巧的网站是：

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)

还有他们的祖父，the book "Hacker's Delight" by Henry Warren, Jr.：

http://www.hackersdelight.org/

正如 Sean Anderson's page 所解释的，表达式 ((x & (x - 1)) == 0) 错误地表明 0 是 2 的幂。他建议使用：

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

来纠正这个问题。

---

return (i & -i) == i

---

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

---

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

以二进制表示时，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 个 1，并且 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（2 的幂）和 x - 1 进行按位与运算时会发生什么？

x 的一个与 x - 1 的零对齐，并且 x 的所有零与 x - 1 的一个对齐，导致按位与结果为 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

---

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

bool IsPowerOfTwo( unsigned int i )
{
    return std::bitset<32>(i).count() == 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;
}

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

---

    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;
    }

---

bool isPow2 = ((x & ~(x-1))==x)? !!x : 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，!(x & (x – 1)) 为真。

---

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

n&(-n)==n

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

---

查找给定数字是否为 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;
}

---

如果一个数字仅包含 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 is_power_of_2(ulong x) {
    if(x ==  (1 << (sizeof(ulong)*8 -1) ) return true;
    return (x > 0) && (x<<1 == (x|(x-1)) +1));
}

---

现在在 .Net 6 中非常容易。

using System.Numerics;

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

Here 是文档。

---

例子

0000 0001    Yes
0001 0001    No

算法

使用位掩码，将变量 NUM 除以二进制 IF R > 0 AND L > 0：返回 FALSE 否则，NUM 变为非零值 IF NUM = 1：返回 TRUE 否则，转到步骤 1

复杂

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

---

.NET 6 中有一个衬里

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

---

改进@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，Mark Gravell 建议使用 this，System.Runtime.Intrinsics.X86.Popcnt.PopCount

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

单条指令，比 (x != 0) && ((x & (x - 1)) == 0) 快，但可移植性较差。

---

在这种方法中，您可以检查整数中是否只有 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;
}

---

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

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

然而，我意识到我已经包含了一个 if 语句，并且分支预测在 bit twiddling 版本上可能做得更好。正如预期的那样，我删除了 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_test.c:

#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;

查看这篇文章到count no. of set bits

---

这也是另一种方法

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;
    }
}

---

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

const isPowerOfTwo = (number) => { 让结果 = false; for (let i = 1; i <= 6; i++) { if (number === Math.pow(2, i)) { result = true; } } 返回结果； }; console.log(isPowerOfTwo(16)); console.log(isPowerOfTwo(10));

---

我一直在阅读 Random.nextInt(int bound) 的 documentation 并看到了这段很好的代码，它检查参数是否是 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 数在正和负二进制表示中具有相同的位，如果我们进行逻辑与我们得到相同的数字:)

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

---

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

---