是否可以将(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) 

成一个单一的比较。 有一些奇特的位移操作可以做到这一点吗?

这一个也工作

 Math.Sqrt(N) == N 

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

有很多方法可以使用按位算术来实现您的算术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是一个无符号整数)

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

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

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

为了完整感谢Matt ,更好的解决scheme:

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

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

如果你想要做的是使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]; } } 

您显然可以为阶乘做同样的事情。

如何用bitshift做到这一点

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

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

对于语言c中的无符号整数NN>>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位的无符号整数溢出也不需要很长时间。 根据你试图去的大小,你需要使用任意的精度整数。

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

编辑

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

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

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

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

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

免责声明:我不知道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性的方法。

这里是我的解决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); } } 

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

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

对于N是uint,只是使用

 N <= 1 

斐波那契数列是一系列数字,其中一个数字是通过将两个数字相加而得到的。 有两种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 ----------------------------------------- 

在这种情况下,位置N1开始,它不是一个数组索引。

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

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

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

注意:这是C,不知道它是否在C#

所以我创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) 

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