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?

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)

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

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 ==.

If what you want to do is to make the function more efficient, then use a lookup table. The lookup table is surprisingly small at only 47 entries - the next entry would overflow a 32-bit unsigned integer. It also of course makes the function trivial to write.

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];
    }
}

You can obviously do the same thing for factorials.

How to do it with bitshift

If you want to use bitshift and make the code somewhat obscure (but short) you could do:

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

For an unsigned integer N in the language c, N>>1 tosses off the low order bit. If that result is non-zero, it implies N is greater than 1.

Note: this algorithm is horribly inefficient as it needlessly recalculates values in the sequence that have already been calculated.

Something WAY WAY faster

Calculate it one pass rather than implicitly building a fibonaci(N) sized tree:

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;
}

As some people have mentioned, it doesn't take long to overflow even a 64 bit unsigned integer. Depending on how large you're trying to go, you'll need to use arbitrary precision integers.

As you use an uint, which can't get negative, you could check if n < 2

EDIT

Or for that special function case you could write it as follows:

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

which will lead to the same result, of course at the cost of an additional recursion step.

Simply check to see if N is <= 1 since you know N is unsigned there can only be 2 conditions that N <= 1 that results in TRUE: 0 and 1

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

Disclaimer: I don't know C#, and didn't test this code:

>But I'm wondering if I can make this even more compact and efficient by changing [...] into a single comparison...

No need for bitshifting or such, this uses just one comparison, and it should be a lot more efficient ( O(n) vs O(2^n) I think? ). The body of the function is more compact, though it ends being a bit longer with the declaration.

(To remove overhead from recursion, there's the iterative version, as in Mathew Gunn's answer)

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: This is a common functional pattern for iteration with accumulators. If you replace N-- with N-1 you're effectively using no mutation, which makes it usable in a pure functional approach.

for N is uint, just use

N <= 1

Here's my solution, there's not much in optimizing this simple function, on the other hand what I'm offering here is readability as a mathematical definition of the recursive function.

public uint fibn(uint N) 
{
    switch(N)
    {
        case  0: return 1;

        case  1: return 1;

        default: return fibn(N-1) + fibn(N-2);
    }
}

The mathematical definition of Fibonacci number in a similar fashion..

Taking it further to force the switch case to build a lookup table.

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);
    }
}

Dmitry's answer is best but if it was an Int32 return type and you had a larger set of integers to choose from you could do this.

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

The Fibonacci sequence is a series of numbers where a number is found by adding up the two numbers before it. There are two types of starting points: (0,1,1,2,..) and (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
-----------------------------------------

The position N in this case starts from 1, it is not 0-based as an array index.

Using C# 6 Expression-body feature and Dmitry's suggestion about ternary operator we can write a one line function with correct calculation for the type 1:

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

and for the type 2:

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

Bit late to the party, but you could also do (x==!!x)

!!x converts the a value to 1 if it's not 0, and leaves it at 0 if it is.
I use this kinda thing in C obfuscation a lot.

Note: This is C, not sure if it works in C#

So I created a List of these special integers and checked if N pertains to it.

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);
}

You could also use an extension method for different purposes where Contains is called only once (e. g. when your application is starting and loading data). This provides a clearer style and clarifies the primary relation to your value (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);
	}
}

Apply it:

N.PertainsTo(ints)

This might be not the fastest way to do it, but to me, it appears to be a better style.