É possível simplificar (x == 0 || x == 1) em uma única operação?

Então, eu estava tentando escrever o n º número na seqüência de Fibonacci em como a função de um compacto quanto possível:

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

Mas estou me perguntando se posso tornar isso ainda mais compacto e eficiente mudando

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

em uma única comparação. Existe alguma operação de mudança de bit sofisticada que pode fazer isso?

Este também funciona

Math.Sqrt(N) == N 

a raiz quadrada de 0 e 1 retornará 0 e 1, respectivamente.

Existem várias maneiras de implementar seu teste aritmético usando aritmética bit a bit. Sua expressão:

• x == 0 || x == 1

é logicamente equivalente a cada um destes:

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

Bônus:

• x * x == x (a prova exige um pouco de esforço)

Mas, falando de forma prática, esses formulários são os mais legíveis, e a pequena diferença no desempenho não vale o uso da aritmética bit a bit:

• x == 0 || x == 1
• x <= 1(porque xé um inteiro sem sinal)
• x < 2(porque xé um inteiro sem sinal)

Uma vez que o argumento é uint( sem sinal ), você pode colocar

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

Menos legível (IMHO), mas se você contar cada personagem ( Code Golf ou similar)

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

Editar : para sua pergunta editada :

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

Ou

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

Você também pode verificar se todos os outros bits são 0, como este:

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

Para completar, graças a Matt, a solução ainda melhor:

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

Em ambos os casos, você precisa cuidar dos parênteses porque os operadores bit a bit têm prioridade menor do que ==.

Se o que você deseja fazer é tornar a função mais eficiente, use uma tabela de pesquisa. A tabela de pesquisa é surpreendentemente pequena com apenas 47 entradas - a próxima entrada estouraria um inteiro não assinado de 32 bits. É claro que também torna a função trivial de escrever.

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, você pode fazer a mesma coisa para fatoriais.

Como fazer isso com bitshift

Se você quiser usar bitshift e tornar o código um tanto obscuro (mas curto), você pode fazer:

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

Para um inteiro sem sinal Nna linguagem c, N>>1descarta o bit de ordem inferior. Se esse resultado for diferente de zero, isso implica que N é maior que 1.

Nota: este algoritmo é terrivelmente ineficiente, pois recalcula desnecessariamente os valores na sequência que já foram calculados.

Algo BEM MUITO mais rápido

Calcule uma passagem, em vez de construir implicitamente uma árvore do tamanho 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 algumas pessoas mencionaram, não demora muito para estourar até mesmo um número inteiro sem sinal de 64 bits. Dependendo de quão grande você está tentando ir, você precisará usar inteiros de precisão arbitrária.

Ao usar um uint, que não pode ser negativo, você pode verificar se n < 2

EDITAR

Ou para esse caso de função especial, você poderia escrevê-lo da seguinte forma:

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

que levará ao mesmo resultado, é claro, ao custo de uma etapa de recursão adicional.

Basta verificar se Né <= 1, pois você sabe que N não tem sinal, só pode haver 2 condições N <= 1que resultam em TRUE: 0 e 1

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

Isenção de responsabilidade: não conheço C # e não testei este código:

Mas estou me perguntando se posso tornar isso ainda mais compacto e eficiente mudando [...] para uma única comparação ...

Não há necessidade de bitshifting ou algo semelhante, ele usa apenas uma comparação e deve ser muito mais eficiente (O (n) vs O (2 ^ n), eu acho?). O corpo da função é mais compacto , embora acabe sendo um pouco mais longo com a declaração.

(Para remover a sobrecarga da recursão, existe a versão iterativa, como na resposta 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

PS: Este é um padrão funcional comum para iteração com acumuladores. Se você substituir N--por, N-1estará efetivamente usando nenhuma mutação, o que o torna utilizável em uma abordagem puramente funcional.

Esta é minha solução, não há muito em otimizar esta função simples, por outro lado, o que estou oferecendo aqui é a legibilidade como uma definição matemática da função recursiva.

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

        case  1: return 1;

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

A definição matemática do número de Fibonacci de forma semelhante.

Levando isso adiante para forçar o caso de switch a construir uma tabela de pesquisa.

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 é uint, basta usar

N <= 1

A resposta de Dmitry é melhor, mas se fosse um tipo de retorno Int32 e você tivesse um conjunto maior de números inteiros para escolher, você poderia fazer isso.

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

A seqüência de Fibonacci é uma série de números onde um número é encontrado somando os dois números anteriores. Existem dois tipos de pontos de partida: ( 0,1 , 1,2, ..) e ( 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
-----------------------------------------

A posição N, neste caso, começa de 1, não é 0-basedcomo um índice de array.

Usando o recurso Expression-body do C # 6 e a sugestão de Dmitry sobre o operador ternário , podemos escrever uma função de uma linha com cálculo correto para o tipo 1:

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

e para o tipo 2:

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

Um pouco tarde para a festa, mas você também pode fazer (x==!!x)

!!xconverte o valor a em 1se não for 0e o deixa em 0se for.
Eu uso muito esse tipo de ofuscação.

Nota: Este é C, não tenho certeza se funciona em C #

Então criei um Listdesses inteiros especiais e verifiquei se Npertence a ele.

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

Você também pode usar um método de extensão para finalidades diferentes onde Containsé chamado apenas uma vez (por exemplo, quando seu aplicativo está iniciando e carregando dados). Isso fornece um estilo mais claro e esclarece a relação principal com seu 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);
    }
}

Aplicam-na:

N.PertainsTo(ints)

Esta pode não ser a maneira mais rápida de fazer isso, mas para mim, parece ser um estilo melhor.