Est-il possible de simplifier (x == 0 || x == 1) en une seule opération ?

Question

Alors j’ai essayé d’écrire le nème nombre dans la séquence de Fibonacci en tant que compact une fonction possible :

Mais je me demande si je peux faire ceci encore plus compacte et plus efficace en changeant

en une seule comparaison. Y a-t-il certaines opération de décalage de bits fantaisie qui peut le faire ?

Answer 1

Il y a un certain nombre de façons de mettre en œuvre votre test à l'aide de l'arithmétique binaire arithmétique. Votre expression:

• x == 0 || x == 1

est logiquement équivalent à chacun de ces:

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

Bonus:

• x * x == x (la preuve en prend un peu d'effort)

Mais dans la pratique, ces formes sont les plus lisibles, et la petite différence de performance n'est pas vraiment la peine au niveau du bit à l'aide de l'arithmétique:

• x == 0 || x == 1
• x <= 1 (parce qu' x est un entier non signé)
• x < 2 (parce qu' x est un entier non signé)

Answer 2

Étant donné que l’argument est `` (non signés), vous pouvez mettre

Moins lisible (AMHA) mais si vous compter chaque caractère (Code Golf ou similaire)

Edit: pour votre édition de question:

Ou

Answer 3

Vous pouvez également vérifier que tous les autres bits sont à 0 comme ceci :

Pour être complet grâce à Matt la solution mieux encore :

Dans les deux cas, il faut prendre soin de la parenthèse parce que les opérateurs de bits ont une priorité plus faible que `` .

Answer 4

Si ce que vous voulez faire est de rendre la fonction plus efficace, utilisez une table de choix. La table est étonnamment faible à seulement 47 entrées - l’entrée suivante provoquerait un dépassement un entier non signé 32 bits. Il rend aussi bien sûr la fonction trivial d’écrire.

Vous pouvez évidemment faire la même chose pour les factorielles.

Answer 5

Comment le faire avec bitshift

Si vous souhaitez utiliser bitshift et rendre le code un peu obscure (mais court) que vous pourriez faire:

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

Pour un entier non signé, N dans le langage c, N>>1 lance off le bit de poids faible. Si ce résultat est non-nul, il implique que N est supérieur à 1.

Remarque: cet algorithme est horriblement inefficace, inutilement recalcule les valeurs de la série qui ont déjà été calculées.

Quelque chose de FAÇON plus rapide

Calculer une passe plutôt que de façon implicite la construction d'un fibonaci(N) de la taille de l'arbre:

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

Comme certaines personnes l'ont mentionné, il ne faut pas longtemps à débordement de même un 64 bits entier non signé. Selon la taille que vous essayez d'aller, vous aurez besoin d'utiliser des entiers en précision arbitraire.