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

所以我试图在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

这一个也工作

 Math.Sqrt(N) == N 

0和1的平方根将分别返回0和1。

Answer 2

有很多方法可以使用按位算术来实现您的算术testing。 你的表情：

• x == 0 || x == 1

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

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

奖金：

• x * x == x （certificate需要一点努力）

但实际上，这些forms是最可读的，性能上的微小差别并不值得使用按位算术：

• x == 0 || x == 1
• x <= 1 （因为x是一个无符号整数）
• x < 2 （因为x是一个无符号整数）

Answer 3

由于参数是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 4

您还可以检查所有其他位是否是这样的0：

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

为了完整感谢Matt ，更好的解决scheme：

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

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

Answer 5

如果你想要做的是使function更有效，那么使用查找表。 查找表是惊人的小，只有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 6

如何用bitshift做到这一点

如果你想使用bitshift，并使代码有点模糊（但很短），你可以这样做：

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

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

注意：这个algorithm是非常低效的，因为它不必要地重新计算已经计算的序列中的值。

事情的方式更快

计算一遍，而不是隐式构build斐波纳契（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 7

当你使用一个不能得到负面的uint时，你可以检查n < 2

编辑

或者对于那个特殊的function，你可以这样写：

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

这将导致相同的结果，当然以额外的recursion步骤为代价。

Answer 8

只要检查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 9

免责声明：我不知道C＃，并没有testing这个代码：

但是，我想知道如果我可以通过改变一个单一的比较，使它更加紧凑和高效…

不需要移位或者这样，这只用一个比较，而且应该更有效率 （O（n）vs O（2 ^ n））。 函数的主体更加紧凑 ，尽pipe声明结束的时间更长。

（为了消除recursion的开销，有一个迭代版本，就像在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：这是使用累加器进行迭代的常用function模式。 如果用N-1代替N-- ，那么你就可以有效地使用没有突变，这使得它可以用于纯function性的方法。

Answer 10

这里是我的解决scheme，在优化这个简单的函数方面没有太多，另一方面，我在这里提供的是可读性作为recursion函数的math定义。

 public uint fibn(uint N) { switch(N) { case 0: return 1; case 1: return 1; default: return fibn(N-1) + fibn(N-2); } } 

斐波纳契数的math定义以类似的方式。

进一步强制开关箱build立一个查询表。

 public uint fibn(uint N) { switch(N) { case 0: return 1; case 1: return 1; case 2: return 2; case 3: return 3; case 4: return 5; case 5: return 8; case 6: return 13; case 7: return 21; case 8: return 34; case 9: return 55; case 10: return 89; case 11: return 144; case 12: return 233; case 13: return 377; case 14: return 610; case 15: return 987; case 16: return 1597; case 17: return 2584; case 18: return 4181; case 19: return 6765; case 20: return 10946; case 21: return 17711; case 22: return 28657; case 23: return 46368; case 24: return 75025; case 25: return 121393; case 26: return 196418; case 27: return 317811; case 28: return 514229; case 29: return 832040; case 30: return 1346269; case 31: return 2178309; case 32: return 3524578; case 33: return 5702887; case 34: return 9227465; case 35: return 14930352; case 36: return 24157817; case 37: return 39088169; case 38: return 63245986; case 39: return 102334155; case 40: return 165580141; case 41: return 267914296; case 42: return 433494437; case 43: return 701408733; case 44: return 1134903170; case 45: return 1836311903; case 46: return 2971215073; default: return fibn(N-1) + fibn(N-2); } } 

Answer 11

德米特里的答案是最好的，但如果它是一个Int32的返回types，你有一个更大的整数集可供select，你可以做到这一点。

 return new List<int>() { -1, 0, 1, 2 }.Contains(N) ? 1 : N * fibn(N-1); 

Answer 12

对于N是uint，只是使用

 N <= 1 

Answer 13

斐波那契数列是一系列数字，其中一个数字是通过将两个数字相加而得到的。 有两种types的起点：（ 0,1，1,2 ，…）和（ 1,1，2,3 ）。

 ----------------------------------------- Position(N)| Value type 1 | Value type 2 ----------------------------------------- 1 | 0 | 1 2 | 1 | 1 3 | 1 | 2 4 | 2 | 3 5 | 3 | 5 6 | 5 | 8 7 | 8 | 13 ----------------------------------------- 

在这种情况下，位置N从1开始，它不是一个数组索引。

使用C＃6expression式体特征和德米特里关于三元运算符的build议，我们可以为types1编写一个具有正确计算的单线函数：

 public uint fibn(uint N) => N<3? N-1: fibn(N-1)+fibn(N-2); 

和types2：

 public uint fibn(uint N) => N<3? 1: fibn(N-1)+fibn(N-2); 

Answer 14

晚了一点晚了，但你也可以做(x==!!x)

如果不是0 ，则!!x将a值转换为1如果是0 ，则将其保留为0 。
我在C混淆中使用了这个有点儿的东西。

注意：这是C，不知道它是否在C＃

Answer 15

所以我创build了一个这些特殊整数的List ，并检查N属于它。

 static List<uint> ints = new List<uint> { 0, 1 }; public uint fibn(uint N) { return ints.Contains(N) ? 1 : fibn(N-1) + fibn(N-2); } 

你也可以使用一个扩展方法来实现不同的目的，其中Contains只被调用一次（例如，当你的应用程序正在启动和加载数据）。 这提供了一个更清晰的风格，并澄清与您的价值（ N ）的主要关系：

 static class ObjectHelper { public static bool PertainsTo<T>(this T obj, IEnumerable<T> enumerable) { return (enumerable is List<T> ? (List<T>) enumerable : enumerable.ToList()).Contains(obj); } } 

应用它：

 N.PertainsTo(ints) 

这可能不是最快的方法，但对我来说，这似乎是一个更好的风格。