是否可以将(x == 0 || x == 1)简化为单个操作？
是否可以将(x == 0 || x == 1)简化为单个操作？
提问于 2016-04-01 23:00:09
所以我试着用尽可能紧凑的函数来写斐波那契数列中的_n_th数：
public uint fibn ( uint N )
{
return (N == 0 || N == 1) ? 1 : fibn(N-1) + fibn(N-2);
}但我想知道我能不能通过改变
(N == 0 || N == 1)变成了一个单一的比较。有没有什么花哨的位移位操作可以做到这一点？
回答 10
Stack Overflow用户
发布于 2016-04-01 23:03:39
您还可以检查所有其他位是否为0，如下所示：
return (N & ~1) == 0 ? 1 : N * fibn(N-1);为了完整性，多亏了Matt，这是更好的解决方案：
return (N | 1) == 1 ? 1 : N * fibn(N-1);在这两种情况下，您都需要注意括号，因为按位运算符的优先级低于==。
Stack Overflow用户
发布于 2016-04-03 20:28:50
如果您要做的是使函数更有效，那么使用查找表。查找表出人意料地小，只有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];
}
}显然，你也可以对factorials做同样的事情。
Stack Overflow用户
发布于 2016-04-02 04:14:19
如何使用位移位执行此操作
如果你想使用位移位并使代码变得有点晦涩(但简短)，你可以这样做：
public uint fibn ( uint N ) {
return N >> 1 != 0? fibn(N-1) + finb(N-2): 1;
}对于c语言中的无符号整数N，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位的无符号整数也不需要很长时间就会溢出。根据你想要的大小，你需要使用任意精度的整数。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/36359610
复制相关文章
相似问题