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

Question

今天我需要一个简单的算法来检查一个数字是否为2的幂。

该算法需要：

1. 简单易懂
2. 对于任何 ulong 值都能正确处理。

我想出了这个简单的算法：

private bool IsPowerOfTwo(ulong number)
{
    if (number == 0)
        return false;

    for (ulong power = 1; power > 0; power = power << 1)
    {
        // This for loop used shifting for powers of 2, meaning
        // that the value will become 0 after the last shift
        // (from binary 1000...0000 to 0000...0000) then, the 'for'
        // loop will break out.

        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}

但是我想到：如何检查log₂x是否正好是一个整数？当我检查2^63+1时，因为四舍五入的原因，Math.Log()返回了确切的63。所以我检查了2的63次方是否等于原始数字，它是相等的，因为计算是在double中进行的，而不是在精确数字中进行的。

private bool IsPowerOfTwo_2(ulong number)
{
    double log = Math.Log(number, 2);
    double pow = Math.Pow(2, Math.Round(log));
    return pow == number;
}

这个给定错误值：9223372036854775809，返回了true。

有没有更好的算法？

- configurator

---

我认为解决方案(x & (x - 1))在X是2的幂次和时，例如8 + 16，可能会返回错误的结果。 - Joe Brown

所有数字都可以写成二的幂次和，这就是我们能够用二进制表示任何数字的原因。此外，你提供的例子没有返回错误的结果，因为 11000 和 10111 的按位与运算等于 10000，不等于 0。 - vlsd

@JoeBrown 它没有任何误报。实际上，该表达式返回任意两个二的幂之和中较大的那个。 - Samie Bencherif

现在在 .NET 6 中非常容易。 - Vivek Nuna

每个二的幂次方只有一个位被设置，难道不是吗？2^0 = 1, 2^1 = 10， 2^2 = 100， 2^3 = 1000依此类推。因此我们可以检查是否只有一个位被设置。2 ^ x = Sum(0 x 2 ^ xi) + (1 x 2 ^ x) + Sum(0 x 2 ^ xj) - gautam1168

Answer 1

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

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

注意，这个函数会返回true给0，而0不是2的幂。如果你想排除它，可以这样做：

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

解释

首先，从MSDN的定义来看，位运算符 & 是这样的：

对于整数类型和布尔类型，二进制 & 运算符是预定义的。对于整数类型，& 计算其操作数的逻辑位与。对于布尔操作数，& 计算其操作数的逻辑与；即，只有当两个操作数都为真时，结果才为真。

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

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

bool b = IsPowerOfTwo(4)

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

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

我们已经知道 4 != 0 的结果是 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的幂。

- Greg Hewgill

---

@Kripp: 这个数字将会是二进制形式的1000...000。当你减1时，它将变成0111...111的形式。因此，这两个数字的二进制相与的结果为000000。对于非2的幂次方，这种情况不会发生，例如1010100会变成1010011，从而导致...(待续) - configurator

通过对二进制进行与运算后得出1010000。唯一的假阳性是0，因此我会使用：return (x != 0) && ((x & (x - 1)) == 0); - configurator

Kripp，请考虑以下比例：(2:1, 10:1) (4:3, 100:11) (8:7, 1000:111) (16:15, 10000:1111) 看到规律了吗？ - Thomas L Holaday

二进制补码表示负数。由于这是无符号整数，因此负数的表示方式并不相关。该技术仅依赖于非负整数的二进制表示方法。 - Greg Hewgill

@SoapBox - 什么更常见？零还是不是2的幂次方的非零数字？这是一个你不能没有更多上下文就回答的问题。而且，实际上，这并不重要。 - configurator

Answer 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)

其中最有名的是Henry Warren, Jr.的书"Hacker's Delight":

• http://www.hackersdelight.org/

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

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

纠正那个问题。

- Michael Burr

---

0 是2的幂次方，2的负无穷次方等于0。 ;) ;) ;) - Michael Bray

由于这是一个标记为___C#___的线程，值得指出的是，Sean Anderson最后一个表达式在C#中是非法的，因为!只能应用于布尔类型，而&&也需要两个操作数都是布尔类型（尽管用户定义的运算符可以使其他操作成为可能，但这对于ulong不相关）。 - Jeppe Stig Nielsen

https://catonmat.net/low-level-bit-hacks 介绍了一些与8位示例相关的位操作技巧。例如，使用 y = x & (-x) 来隔离最右边的1位。这个测试只是清除最低位设置的一个特殊情况。 - Peter Cordes

Answer 3

return (i & -i) == i

- Andreas Petersson

---

有没有任何提示为什么这会或不会起作用？我只在Java中检查了它的正确性，那里只有有符号的int/long。 如果它是正确的，这将是更好的答案。更快+更小 - Andreas Petersson

利用二进制补码的一个特性，求一个数的相反数需要对其进行按位取反并加1。在 -i 中，与 i 相同的最低位将被设置为 1。除此位外，以下所有位都为 0（两个值均如此），而以上的所有位则相对于彼此进行了反转。因此，i & -i 的值将是 i 最低位上置位的位置（也就是2的幂次方）。如果 i 和该值相同，则说明 i 中只有一位为1。当 i 为0时，这种方法会失败，原因与 i & (i - 1) == 0 相同。 - Michael Carman

如果i是一个无符号类型，那么二进制补码与之无关。你仅仅是利用模数运算和按位与的特性。 - R.. GitHub STOP HELPING ICE

当i==0时，这个条件不满足（返回(0&0==0)为true），因此这个方法不能正常工作。应该修改为return i && ( (i&-i)==i )。 - bobobobo

Answer 4

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

一个二的幂，在二进制表示中，总是看起来像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)
.          .
.          .
.          .

等等之类的。

来到关键点

当我们对一个2的幂次方的数字x和x - 1进行按位与操作时会发生什么？

x的1与x - 1的0对齐，x的所有0与x - 1的1对齐，导致按位与操作结果为0。这就是为什么我们有上面提到的单行答案是正确的。

---

进一步增添上述答案的美妙之处 -

所以，我们现在有一个可供我们使用的属性：

当我们从任意数字中减去1时，在二进制表示中，最右边的1将变为0，而该最右边1右边的所有0将变为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

- displayName

---

@Michi：我在哪里声称0是正数？还是2的幂次方？ - displayName

是的，通过以 0 作为示例，并在其二进制表示中进行数学计算，会产生混乱。 - Michi

对于“属性”，你是不是想说：“...并且右边最右边的1右边的所有零现在将变成1”? - undefined

@lesterfernandez：你说得对！ - undefined

Answer 5

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

- Matt Howells

---

如果允许负数通过（使用long而不是ulong），那么这种解决方案更好，因为它也可以处理负数。 - Steven

为什么在这种情况下十进制数可以通过二的幂传递？ - chris Frisina

Answer 6

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

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

- deft_code

---

在GCC上编译时，这将转化为一个名为__builtin_popcount的单个GCC内置函数。不幸的是，在某些处理器族中（例如x86），还没有一条单独的汇编指令来执行此操作，因此它是计算位数最快的方法。在任何其他体系结构中，这将是一条单独的汇编指令。 - deft_code

较新的x86微架构支持popcnt指令。 - phuclv

使用lea eax, [rdi-1]和test/jnz实现i & (i-1) == 0比使用popcnt / cmp/je要便宜一些，特别是如果您不需要处理i==0的情况。 - Peter Cordes

谢谢您提到C++并将其链接到C++的维基百科页面。如果没有这个，那将会非常非常令人困惑。/s - displayName

Answer 7

发布问题后，我想到了以下解决方案：

我们需要检查二进制中恰好有一个数字为1。因此，我们只需要逐位将数字向右移一位，并且如果等于1则返回true。如果在任何时候我们得到的是奇数（(number & 1) == 1），我们就知道结果是false。使用基准测试证明，这个方法对于（大）true值稍微比原来的方法快一些，而对于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的解决方案要好得多。

- configurator

Answer 8

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

- Rezo Megrelidze

Answer 9

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

- abelenky

---

这是 C# 吗？我猜这是 C++，因为 x 被返回为布尔值。 - Mariano Desanze

我是用C++编写的。将它转换为C#非常简单：bool isPow2 = ((x & ~(x-1))==x)? x!=0 : false; - abelenky

Answer 10

.Net 6现在非常容易操作。

using System.Numerics;

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

这里 是文档。

- Vivek Nuna