为了账号安全,请及时绑定邮箱和手机立即绑定

如何检查一个数字是否为2的幂

/ 猿问

如何检查一个数字是否为2的幂

慕码人8056858 2019-06-25 15:56:13

如何检查一个数字是否为2的幂

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

但后来我想,检查一下log2 x是正整数吗?但当我检查2^63+1时,Math.Log因为四舍五入返回了63。因此,我检查了幂63的2是否等于原来的数字-是的,因为计算是在doubles而不是确切的数字:

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.

有更好的算法吗?


查看完整描述

3 回答

?
墨色风雨

要解决这个问题,有一个简单的技巧:

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

注意,此功能将报告true0,这不是2..如果您想排除这一点,下面是如何:

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

解释

首先也是最重要的,是MSDN定义中的按位二进制&操作符:

二进制&运算符是为积分类型和bool预定义的。对于整型,计算逻辑位数及其操作数。对于bool操作数,&计算逻辑和它的操作数;也就是说,结果是真的当且仅当它的两个操作数都是真的。

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

函数返回布尔值(true/false),并接受一个输入参数(在本例中为x)。为了简单起见,让我们假设有人传递了值4并调用了函数,如下所示:

bool b = IsPowerOfTwo(4)

现在,我们将x的每次出现替换为4:

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

我们已经知道4!=0为真,到目前为止还不错。但是关于:

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

当然,这意味着:

((4 & 3) == 0)

但究竟什么是4&3?

4的二进制表示为100,3的二进制表示为011(记住&接受这些数字的二进制表示)。所以我们有:

100 = 4011 = 3

假设这些值被堆叠起来,就像基本加法一样。这个&运算符表示,如果两个值都等于1,则结果为1,否则为0。所以1 & 1 = 11 & 0 = 00 & 0 = 0,和0 & 1 = 0..所以我们计算一下:

100011----000

结果就是0。因此,我们回头看看返回语句现在转换为:

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

现在翻译为:

return true && (0 == 0);
return true && true;

我们都知道true && true是简单的true,这表明,在我们的例子中,4是2的幂。


查看完整回答
反对 回复 2019-06-25
?
哔哔one

一些记录和解释这一问题和其他一些小问题的网站有:

他们的祖父,亨利·沃伦著的“黑客的欢乐”一书。:

肖恩·安德森的页面解释,表达式((x & (x - 1)) == 0)错误地表示0是2的幂。他建议使用:

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

来纠正这个问题。


查看完整回答
反对 回复 2019-06-25
?
繁花如伊
bool IsPowerOfTwo(ulong x){
    return x > 0 && (x & (x - 1)) == 0;}


查看完整回答
反对 回复 2019-06-25

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信