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

发布于 2024-07-14 04:45:24 字数 1104 浏览 12 评论 0原文

今天，我需要一个简单的算法来检查一个数字是否是 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;
}

对于给定的错误值，这返回了 true：9223372036854775809。

有更好的算法吗？

原文

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

The algorithm needs to be:

Simple
Correct for any ulong value.

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 log₂ x is an exactly a round number? 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;
}

This returned true for the given wrong value: 9223372036854775809.

Is there a better algorithm?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

原来分手还会想你 2024-07-21 04:45:24

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

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

注意，此函数将为 0 报告 true，这不是 2 的幂。如果您想排除它，请执行以下操作：

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

解释

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

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

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

该函数返回布尔值（true / false）并接受一个 unsigned long 类型（在本例中为 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 语句现在翻译成什么：

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

现在翻译成：

return true && (0 == 0);

return true && true;

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

There's a simple trick for this problem:

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

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

Explanation

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

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:

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)

Now we replace each occurrence of x with 4:

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 & (4-1)) == 0)

This translates to this of course:

((4 & 3) == 0)

But what exactly is 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:

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:

100
011
----
000

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

Which translates now to:

return true && (0 == 0);

return true && true;

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

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

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（30）

解释

Explanation

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

Further adding to the beauty of accepted answer above -

n&(-n)==n

n&(-n)==n

关于作者

相关话题

热门标签

推荐作者

已经忘了多久

15867725375

LonelySnow

走过海棠暮

轻许诺言

信馬由缰

友情链接

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。