是否可以将(x == 0 || x == 1)简化为单个操作？

Question

所以我试图在Fibonacci序列中尽可能紧凑地写出第n个数:

public uint fibn ( uint N ) 
{
   return (N == 0 || N == 1) ? 1 : fibn(N-1) + fibn(N-2);
}

但我想知道我是否可以通过改变来使其更加紧凑和高效

(N == 0 || N == 1)

进入单一比较.是否有一些奇特的位移操作可以做到这一点？

Answer 1

有许多方法可以使用按位算法实现算术测试.你的表达:

• x == 0 || x == 1

在逻辑上等同于以下每一个:

• (x & 1) == x
• (x & ~1) == 0
• (x | 1) == 1
• (~x | 1) == (uint)-1
• x >> 1 == 0

奖金:

• x * x == x (证明需要一点努力)

但实际上,这些形式是最具可读性的,并且性能的微小差异并不值得使用按位算术:

• x == 0 || x == 1
• x <= 1(因为x是无符号整数)
• x < 2(因为x是无符号整数)

Answer 2

由于参数是uint(无符号),你可以放

  return (N <= 1) ? 1 : N * fibn(N-1);

可读性较低(恕我直言),但如果算上每个角色(Code Golf或类似)

  return N < 2 ? 1 : N * fibn(N-1);

编辑:针对您编辑的问题:

  return (N <= 1) ? 1 : fibn(N-1) + fibn(N-2);

要么

  return N < 2 ? 1 : fibn(N-1) + fibn(N-2);

Answer 3

您还可以检查所有其他位是否为0,如下所示:

return (N & ~1) == 0 ? 1 : N * fibn(N-1);

为了完整性,感谢Matt更好的解决方案:

return (N | 1) == 1 ? 1 : N * fibn(N-1);

在这两种情况下,您都需要注意括号,因为按位运算符的优先级低于==.

Answer 4

如果您想要做的是使函数更有效,那么使用查找表.只有47个条目的查找表非常小 - 下一个条目将溢出32位无符号整数.它当然也使得函数写得微不足道.

class Sequences
{
    // Store the complete list of values that will fit in a 32-bit unsigned integer without overflow.
    private static readonly uint[] FibonacciSequence = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
        233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
        317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169,
        63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073
    };

    public uint fibn(uint N)
    {
        return FibonacciSequence[N];
    }
}

显然,你可以为因子做同样的事情.

Answer 5

如何用bitshift做到这一点

如果你想使用bitshift并使代码有点模糊(但很短),你可以这样做:

public uint fibn ( uint N ) {
   return N >> 1 != 0? fibn(N-1) + finb(N-2): 1;
}

对于N语言c中的无符号整数,N>>1抛弃低位.如果该结果不为零,则表示N大于1.

注意:此算法非常低效,因为它不必要地重新计算已经计算的序列中的值.

东西方式更快

计算它一次而不是隐式地构建一个fibonaci(N)大小的树:

uint faster_fibn(uint N) { //requires N > 1 to work
  uint a = 1, b = 1, c = 1;
  while(--N != 0) {
    c = b + a;
    a = b;
    b = c;
  }
  return c;
}

正如一些人所提到的,即使64位无符号整数溢出也不需要很长时间.根据您尝试的大小,您需要使用任意精度整数.

Answer 6

当你使用一个不能消极的uint时,你可以检查一下 n < 2

编辑

或者对于那个特殊功能案例,您可以按如下方式编写它:

public uint fibn(uint N)
    return (N == 0) ? 1 : N * fibn(N-1);
}

这将导致相同的结果,当然是以额外的递归步骤为代价.

Answer 7

只需检查是否N<= 1,因为您知道N是无符号的,只有2个条件N <= 1导致TRUE:0和1

public uint fibn ( uint N ) 
{
   return (N <= 1) ? 1 : fibn(N-1) + finb(N-2);
}

Answer 8

免责声明:我不知道C#,并没有测试此代码:

但我想知道我是否可以通过将[...]更改为单个比较来使其更加紧凑和高效...

不需要比特移位等,这只使用一次比较,它应该更高效(我认为O(n)vs O(2 ^ n)？).函数的主体更紧凑,但声明的结束时间稍长.

(为了消除递归的开销,有迭代版本,如Mathew Gunn的答案)

public uint fibn ( uint N, uint B=1, uint A=0 ) 
{
    return N == 0 ? A : fibn( N--, A+B, B );
}

                     fibn( 5 ) =
                     fibn( 5,   1,   0 ) =
return 5  == 0 ? 0 : fibn( 5--, 0+1, 1 ) =
                     fibn( 4,   1,   1 ) =
return 4  == 0 ? 1 : fibn( 4--, 1+1, 1 ) =
                     fibn( 3,   2,   1 ) =
return 3  == 0 ? 1 : fibn( 3--, 1+2, 2 ) =
                     fibn( 2,   3,   2 ) =
return 2  == 0 ? 2 : fibn( 2--, 2+3, 3 ) =
                     fibn( 1,   5,   3 ) =
return 1  == 0 ? 3 : fibn( 1--, 3+5, 5 ) =
                     fibn( 0,   8,   5 ) =
return 0  == 0 ? 5 : fibn( 0--, 5+8, 8 ) =
                 5
fibn(5)=5

PS:这是使用累加器进行迭代的常用功能模式.如果你替换N--为N-1你有效地使用没有变异,这使它可用于纯粹的功能方法.

Answer 9

因为 N 是 uint，只需使用

N <= 1