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

How to check if a number is a power of 2

提问by configurator

Today I needed a simple algorithm for checking if a number is a power of 2.

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

The algorithm needs to be:

该算法需要是：

1. Simple
2. Correct for any ulongvalue.

1. 简单的
2. 修正任何ulong值。

I came up with this simple algorithm:

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

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

But then I thought, how about checking if log2xis an exactly round number? But when I checked for 2^63+1, Math.Logreturned exactly 63 because of rounding. So I checked if 2 to the power 63 is equal to the original number - and it is, because the calculation is done in doubles and not in exact numbers:

但后来我想，如何检查是否是一个整数？但是当我检查 2^63+1 时，由于四舍五入，正好返回了 63。所以我检查了 2 的 63 次方是否等于原始数字 - 确实如此，因为计算是在s 中完成的，而不是在精确数字中：log2xMath.Logdouble

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

This returned truefor the given wrong value: 9223372036854775809.

这true为给定的错误值返回：9223372036854775809。

Is there a better algorithm?

有没有更好的算法？

采纳答案by Greg Hewgill

There's a simple trick for this problem:

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

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

Note, this function will report truefor 0, which is not a power of 2. If you want to exclude that, here's how:

注意，此功能将报告true的0，这是不是一个动力2。如果你想排除它，这里是如何：

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

Explanation

解释

First and foremost the bitwise binary & operator from MSDN definition:

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

Binary & operators are predefined for the integral types and bool. For integral types, & computes the logical bitwise AND of its operands. For bool operands, & computes the logical AND of its operands; that is, the result is true if and only if both its operands are true.

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

Now let's take a look at how this all plays out:

现在让我们来看看这一切是如何进行的：

The function returns boolean (true / false) and accepts one incoming parameter of type unsigned long (x, in this case). Let us for the sake of simplicity assume that someone has passed the value 4 and called the function like so:

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

bool b = IsPowerOfTwo(4)

Now we replace each occurrence of x with 4:

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

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

Well we already know that 4 != 0 evals to true, so far so good. But what about:

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

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

This translates to this of course:

这当然可以转化为：

((4 & 3) == 0)

But what exactly is 4&3?

但究竟是4&3什么？

The binary representation of 4 is 100 and the binary representation of 3 is 011 (remember the & takes the binary representation of these numbers). So we have:

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

100 = 4
011 = 3

Imagine these values being stacked up much like elementary addition. The &operator says that if both values are equal to 1 then the result is 1, otherwise it is 0. So 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0, and 0 & 1 = 0. So we do the math:

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

100
011
----
000

The result is simply 0. So we go back and look at what our return statement now translates to:

结果只是 0。 所以我们回去看看我们的 return 语句现在转换成什么：

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

Which translates now to:

现在翻译成：

return true && (0 == 0);

return true && true;

We all know that true && trueis simply true, and this shows that for our example, 4 is a power of 2.

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

回答by configurator

After posting the question I thought of the following solution:

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

We need to check if exactly one of the binary digits is one. So we simply shift the number right one digit at a time, and return trueif it equals 1. If at any point we come by an odd number ((number & 1) == 1), we know the result is false. This proved (using a benchmark) slightly faster than the original method for (large) true values and much faster for false or small values.

我们需要检查二进制数字中的一个是否为 1。因此，我们只需将数字一次右移一位，true如果等于 1 则返回。如果在任何时候我们得到一个奇数 ( (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;
}

---

---

Of course, Greg's solution is much better.

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

回答by Michael Burr

Some sites that document and explain this and other bit twiddling hacks are:

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

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

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

And the grandaddy of them, the book "Hacker's Delight" by Henry Warren, Jr.:

还有他们的祖父，小亨利·沃伦 (Henry Warren, Jr.) 所著的《黑客的喜悦》一书：

• http://www.hackersdelight.org/

• http://www.hackersdelight.org/

As Sean Anderson's pageexplains, the expression ((x & (x - 1)) == 0)incorrectly indicates that 0 is a power of 2. He suggests to use:

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

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

to correct that problem.

来纠正这个问题。

回答by Rick Regan

I wrote an article about this recently at http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/. It covers bit counting, how to use logarithms correctly, the classic "x && !(x & (x - 1))" check, and others.

我最近在http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/写了一篇关于这个的文章。它涵盖了位计数、如何正确使用对数、经典的“x && !(x & (x - 1))”检查等。

回答by Andreas Petersson

return (i & -i) == i

return (i & -i) == i

回答by user134548

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

回答by Matt Howells

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

回答by udhaya

Find if the given number is a power of 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;
}

回答by deft_code

Here's a simple C++solution:

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

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

回答by abelenky

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