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

Question

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?

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