Is it possible to simplify (x == 0 || x == 1) into a single operation?

So I was trying to write the nth number in the Fibonacci sequence in as compact a function as possible:

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

But I'm wondering if I can make this even more compact and efficient by changing

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

into a single comparison. Is there some fancy bit shift operation that can do this?

Solution 1:

There are a number of ways to implement your arithmetic test using bitwise arithmetic. Your expression:

• x == 0 || x == 1

is logically equivalent to each one of these:

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

Bonus:

• x * x == x (the proof takes a bit of effort)

But practically speaking, these forms are the most readable, and the tiny difference in performance isn't really worth using bitwise arithmetic:

• x == 0 || x == 1
• x <= 1 (because x is an unsigned integer)
• x < 2 (because x is an unsigned integer)

Solution 2:

Since argument is uint (unsigned) you can put

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

Less readable (IMHO) but if you count each character (Code Golf or alike)

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

Edit: for your edited question:

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

Or

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

Solution 3:

You could also check that all other bits are 0 like this:

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

For completeness thanks to Matt the even better solution:

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

In both cases you need to take care of the parenthesis because bitwise operators have lower priority than ==.