如何判断一个数是否是2的幂 [英] How to check if a number is a power of 2

问题描述

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

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

算法需要:

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

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

But then I thought, how about checking if log2 x is an exactly round number? But when I checked for 2^63+1, Math.Log returned 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:

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

对于给定的错误值，这返回了 true:9223372036854775809.

This returned true for the given wrong value: 9223372036854775809.

有更好的算法吗?

推荐答案

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

There's a simple trick for this problem:

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

注意，这个函数会为0报告true，这不是2的幂.如果您想排除它，方法如下:

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

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

说明

首先是按位二进制 &来自 MSDN 定义的操作符:

Explanation

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

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

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.

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

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

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

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:

bool b = IsPowerOfTwo(4)

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

Now we replace each occurrence of x with 4:

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

我们已经知道 4 != 0 评估为真，到目前为止一切顺利.但是呢:

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

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

这当然可以转化为:

((4 & 3) == 0)

但是4&3究竟是什么?

4 的二进制表示是 100，而 3 的二进制表示是 011(记住 & 采用这些数字的二进制表示).所以我们有:

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:

100 = 4
011 = 3

想象一下这些值的叠加很像基本加法.& 运算符表示如果两个值都等于 1，则结果为 1，否则为 0.所以 1 &1 = 1, 1 &0 = 0, 0 &0 = 0 和 0 &1 = 0.所以我们计算一下:

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:

100
011
----
000

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

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

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

现在翻译成:

return true && (0 == 0);

return true && true;

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

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

这篇关于如何判断一个数是否是2的幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！