Quel est le moyen le plus rapide de déterminer si un nombre est pair ou impair?

Quel est le moyen le plus rapide de déterminer si un nombre est pair ou impair?

Il est bien connu que

static inline int is_odd_A(int x) { return x & 1; } 

est plus efficace que

 static inline int is_odd_B(int x) { return x % 2; } 

Mais avec l’optimiseur is_odd_B , is_odd_B ne sera- is_odd_B il pas différent de is_odd_A ? Non – avec gcc-4.2 -O2 , nous obtenons (en assembleur ARM):

 _is_odd_A: and r0, r0, #1 bx lr _is_odd_B: mov r3, r0, lsr #31 add r0, r0, r3 and r0, r0, #1 rsb r0, r3, r0 bx lr 

Nous voyons que is_odd_B prend 3 instructions de plus que is_odd_A , la raison principale étant que

 ((-1) % 2) == -1 ((-1) & 1) == 1 

Cependant , toutes les versions suivantes généreront le même code que is_odd_A :

 #include  static inline bool is_odd_D(int x) { return x % 2; } // note the bool static inline int is_odd_E(int x) { return x % 2 != 0; } // note the != 

Qu’est-ce que ça veut dire? L’optimiseur est généralement assez sophistiqué pour que, pour ces choses simples, le code le plus clair soit suffisant pour garantir la meilleure efficacité .

Manière habituelle de le faire:

 int number = ...; if(number % 2) { odd } else { even } 

Alternative:

 int number = ...; if(number & 1) { odd } else { even } 

Testé sur GCC 3.3.1 et 4.3.2, les deux ont à peu près la même vitesse (sans optimisation du compilateur) que les deux résultats dans l’instruction and (compilé sur x86) – Je sais que l’utilisation de l’instruction div pour modulo serait beaucoup plus lente, donc Je ne l’ai pas testé du tout.

 bool is_odd = number & 1; 

si (x & 1) est vrai, alors c’est étrange, sinon c’est pair.

 int i=5; if ( i%2 == 0 ) { // Even } else { // Odd } 

S’il s’agit d’un entier, il suffit probablement de cocher le bit le moins significatif. Zéro serait compté comme même si.

La méthode portable consiste à utiliser l’opérateur de module % :

 if (x % 2 == 0) // number is even 

Si vous savez que vous n’utiliserez que des architectures de complément à deux, vous pouvez utiliser un bitwise et:

 if (x & 0x01 == 0) // number is even 

L’utilisation de l’opérateur de module peut entraîner un code plus lent par rapport au bit et; cependant, je m’en tiendrai à moins que tout ce qui suit soit vrai:

  1. Vous ne répondez pas à une exigence de performance ssortingcte;
  2. Vous exécutez beaucoup x % 2 (disons dans une boucle serrée exécutée des milliers de fois);
  3. Le profilage indique que l’utilisation de l’opérateur mod est le goulot d’étranglement;
  4. Le profilage indique également que l’utilisation du bit à bits soulage le goulot d’étranglement et vous permet de respecter les exigences de performances.
 int is_odd(int n) { if (n == 0) return 0; else if (n == 1) return 1; else return !is_odd(n - 1); } 

Oh, attends, tu as dit le moyen le plus rapide , pas le plus drôle . Ma faute 😉

La fonction ci-dessus ne fonctionne que pour les nombres positifs bien sûr.

Vérifiez si le dernier bit est 1.

 int is_odd(int num) { return num & 1; } 

Cochez le bit le moins significatif:

 if (number & 0x01) { // It's odd } else { // It's even } 

Votre question n’est pas complètement spécifiée. Quoi qu’il en soit, la réponse dépend de votre compilateur et de l’architecture de votre machine. Par exemple, êtes-vous sur une machine utilisant des représentations de nombres signés à son complément ou à deux?

J’écris mon code pour être correct en premier, clair en deuxième, concis en troisième et rapide dernier. Par conséquent, je coderais cette routine comme suit:

 /* returns 0 if odd, 1 if even */ /* can use bool in C99 */ int IsEven(int n) { return n % 2 == 0; } 

Cette méthode est correcte, elle exprime plus clairement l’intention que de tester le LSB, elle est concise et, croyez-le ou non, c’est extrêmement rapide. Si et seulement si le profilage me disait que cette méthode constituait un goulot d’étranglement dans ma candidature, je envisagerais de m’en écarter.