¿Es posible simplificar (x == 0 || x == 1) en una sola operación?

Así que estaba tratando de escribir el número n en la secuencia de Fibonacci en una función lo más compacta posible:

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

Pero me pregunto si puedo hacer esto aún más compacto y eficiente cambiando

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

en una sola comparación. ¿Hay alguna operación de cambio de bits elegante que pueda hacer esto?

Este también funciona

Math.Sqrt(N) == N 

La raíz cuadrada de 0 y 1 devolverá 0 y 1 respectivamente.

Hay varias formas de implementar su prueba aritmética usando aritmética bit a bit. Tu expresión:

• x == 0 || x == 1

es lógicamente equivalente a cada uno de estos:

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

Prima:

• x * x == x (la prueba requiere un poco de esfuerzo)

Pero en la práctica, estos formularios son los más legibles, y la pequeña diferencia en el rendimiento no vale la pena usar aritmética bit a bit:

• x == 0 || x == 1
• x <= 1(porque xes un entero sin signo)
• x < 2(porque xes un entero sin signo)

Dado que el argumento está uint( sin firmar ) puede poner

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

Menos legible (en mi humilde opinión) pero si cuentas cada carácter ( Code Golf o similar)

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

Editar : para su pregunta editada :

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

O

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

También puede verificar que todos los demás bits sean 0 así:

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

Para completar gracias a Matt, la solución aún mejor:

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

En ambos casos, debe cuidar los paréntesis porque los operadores bit a bit tienen una prioridad menor que ==.

Si lo que desea hacer es hacer que la función sea más eficiente, utilice una tabla de búsqueda. La tabla de búsqueda es sorprendentemente pequeña con solo 47 entradas; la siguiente entrada desbordaría un entero sin signo de 32 bits. Por supuesto, también hace que escribir la función sea trivial.

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

Obviamente, puedes hacer lo mismo con los factoriales.

Cómo hacerlo con bitshift

Si desea usar bitshift y hacer que el código sea algo oscuro (pero corto), puede hacer:

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

Para un entero sin signo Nen el lenguaje c, N>>1descarta el bit de orden inferior. Si ese resultado es distinto de cero, implica que N es mayor que 1.

Nota: este algoritmo es terriblemente ineficiente ya que recalcula innecesariamente valores en la secuencia que ya se han calculado.

Algo MUCHO MUCHO más rápido

Calcule una pasada en lugar de construir implícitamente un árbol del tamaño de fibonaci (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;
}

Como han mencionado algunas personas, no se tarda mucho en desbordar incluso un entero de 64 bits sin signo. Dependiendo de qué tan grande esté tratando de llegar, deberá usar números enteros de precisión arbitrarios.

Como usa un uint, que no puede ser negativo, puede verificar si n < 2

EDITAR

O para ese caso de función especial, podría escribirlo de la siguiente manera:

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

lo que conducirá al mismo resultado, por supuesto, a costa de un paso de recursividad adicional.

Simplemente verifique si Nes <= 1 ya que sabe que N no está firmado, solo puede haber 2 condiciones que den N <= 1como resultado TRUE: 0 y 1

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

Descargo de responsabilidad: no sé C # y no probé este código:

Pero me pregunto si puedo hacer esto aún más compacto y eficiente cambiando [...] a una sola comparación ...

No es necesario el cambio de bits o algo así, esto usa solo una comparación, y debería ser mucho más eficiente (O (n) vs O (2 ^ n), ¿creo?). El cuerpo de la función es más compacto , aunque termina siendo un poco más largo con la declaración.

(Para eliminar la sobrecarga de la recursividad, existe la versión iterativa, como en la respuesta de 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

PD: Este es un patrón funcional común para la iteración con acumuladores. Si reemplaza N--con N-1, efectivamente no está usando ninguna mutación, lo que lo hace utilizable en un enfoque funcional puro.

Aquí está mi solución, no hay mucho para optimizar esta función simple, por otro lado, lo que estoy ofreciendo aquí es la legibilidad como una definición matemática de la función recursiva.

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

        case  1: return 1;

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

La definición matemática del número de Fibonacci de manera similar.

Llevándolo más lejos para forzar a la caja del interruptor a construir una tabla de búsqueda.

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

para N es uint, solo use

N <= 1

La respuesta de Dmitry es la mejor, pero si fuera un tipo de retorno Int32 y tuviera un conjunto más grande de enteros para elegir, podría hacer esto.

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

La secuencia de Fibonacci es una serie de números donde un número se encuentra sumando los dos números anteriores. Hay dos tipos de puntos de partida: ( 0,1 , 1,2, ..) y ( 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
-----------------------------------------

La posición Nen este caso comienza desde 1, no es 0-basedcomo un índice de matriz.

Usando la función de cuerpo de expresión de C # 6 y la sugerencia de Dmitry sobre el operador ternario, podemos escribir una función de una línea con el cálculo correcto para el tipo 1:

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

y para el tipo 2:

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

Un poco tarde para la fiesta, pero también podrías hacerlo (x==!!x)

!!xconvierte el valor a 1si no lo es 0, y lo deja 0si lo es.
Utilizo mucho este tipo de cosas en la ofuscación de C.

Nota: Esto es C, no estoy seguro si funciona en C #

Así que creé uno Listde estos enteros especiales y verifiqué si Npertenece a él.

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

También puede usar un método de extensión para diferentes propósitos donde Containsse llama solo una vez (por ejemplo, cuando su aplicación está iniciando y cargando datos). Esto proporciona un estilo más claro y aclara la relación principal con su valor ( 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);
    }
}

Apliquelo:

N.PertainsTo(ints)

Puede que esta no sea la forma más rápida de hacerlo, pero para mí, parece ser un estilo mejor.