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:
x % 2
(disons dans une boucle serrée exécutée des milliers de fois); 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.