Quelle est la meilleure option à utiliser pour diviser un nombre entier par 2?

Laquelle des techniques suivantes est la meilleure option pour diviser un entier par 2 et pourquoi?

Technique 1:

x = x >> 1;

Technique 2:

x = x / 2;

Voici xun entier.

Utilisez l'opération qui décrit le mieux ce que vous essayez de faire.

• Si vous traitez le nombre comme une séquence de bits, utilisez bitshift.
• Si vous la traitez comme une valeur numérique, utilisez la division.

Notez qu'ils ne sont pas exactement équivalents. Ils peuvent donner des résultats différents pour les entiers négatifs. Par exemple:

-5 / 2  = -2
-5 >> 1 = -3

(ideone)

La première ressemble-t-elle à une division? Non. Si vous voulez diviser, utilisez x / 2. Le compilateur peut l'optimiser pour utiliser le bit-shift si possible (c'est ce qu'on appelle la réduction de la force), ce qui en fait une micro-optimisation inutile si vous le faites vous-même.

Pour empiler: il y a tellement de raisons de favoriser l'utilisation x = x / 2; Voici quelques-unes:

• il exprime plus clairement votre intention (en supposant que vous n'avez pas affaire à des bits de registre de torsion de bits ou à quelque chose)

• le compilateur le réduira de toute façon à une opération de décalage

• même si le compilateur ne l'a pas réduit et a choisi une opération plus lente que le changement, la probabilité que cela finisse par affecter les performances de votre programme de manière mesurable est elle-même extrêmement faible (et si elle l'affecte de manière mesurable, alors vous avez un réel raison d'utiliser un quart de travail)

• si la division va faire partie d'une expression plus large, il est plus probable que vous ayez la priorité si vous utilisez l'opérateur de division:

  x = x / 2 + 5;
  x = x >> 1 + 5;  // not the same as above

• l'arithmétique signée pourrait compliquer les choses encore plus que le problème de priorité mentionné ci-dessus

• pour réitérer - le compilateur le fera déjà de toute façon. En fait, il convertira la division par une constante en une série de décalages, s'ajoute et se multiplie pour toutes sortes de nombres, pas seulement des puissances de deux. Voir cette question pour des liens vers encore plus d'informations à ce sujet.

En bref, vous n'achetez rien en codant un décalage lorsque vous voulez vraiment multiplier ou diviser, sauf peut-être une possibilité accrue d'introduire un bug. Cela fait toute une vie que les compilateurs n'étaient pas assez intelligents pour optimiser ce genre de chose en un quart de travail le cas échéant.

Laquelle est la meilleure option et pourquoi diviser le nombre entier par 2?

Cela dépend de ce que vous entendez par le meilleur .

Si vous voulez que vos collègues vous haïssent ou rendent votre code difficile à lire, j'irais certainement avec la première option.

Si vous voulez diviser un nombre par 2, optez pour le second.

Les deux ne sont pas équivalents, ils ne se comportent pas de la même façon si le nombre est négatif ou dans des expressions plus grandes - le décalage de bits a une priorité inférieure à +ou- , la division a une priorité plus élevée.

Vous devez écrire votre code pour exprimer son intention. Si les performances vous préoccupent, ne vous inquiétez pas, l'optimiseur fait du bon travail avec ce type de micro-optimisations.

Utilisez simplement divide ( /), en supposant que c'est plus clair. Le compilateur optimisera en conséquence.

Je suis d'accord avec d'autres réponses que vous devriez privilégier x / 2car son intention est plus claire et le compilateur devrait l'optimiser pour vous.

Cependant, une autre raison de préférer x / 2plus x >> 1est que le comportement de >>dépend de la mise en œuvre si xest un signé intet est négative.

De la section 6.5.7, puce 5 de la norme ISO C99:

Le résultat E1 >> E2est des positions de bits E1décalées vers la droite E2. Si E1a un type non signé ou si E1a un type signé et une valeur non négative, la valeur du résultat fait partie intégrante du quotient de E1/ 2 ^E2. Si E1a un type signé et une valeur négative, la valeur résultante est définie par l'implémentation.

x / 2est plus clair et x >> 1n'est pas beaucoup plus rapide (selon un micro-benchmark, environ 30% plus rapide pour une JVM Java). Comme d'autres l'ont noté, pour les nombres négatifs, l'arrondi est légèrement différent, vous devez donc en tenir compte lorsque vous souhaitez traiter des nombres négatifs. Certains compilateurs peuvent se convertir automatiquement x / 2enx >> 1 s'ils savent que le nombre ne peut pas être négatif (même pensé que je ne pouvais pas vérifier).

Même x / 2ne peut pas utiliser l'instruction CPU de division (lente), car certains raccourcis sont possibles , mais il est toujours plus lent que x >> 1.

(Ceci est une question C / C ++, d' autres langages de programmation ont plusieurs opérateurs. Pour Java il y a aussi le décalage droit non signé, x >>> 1qui est encore différente. Il permet de calculer correctement la valeur moyenne (moyenne) de deux valeurs, de sorte que la (a + b) >>> 1volonté renvoie la valeur moyenne même pour les très grandes valeurs de aet b. Ceci est requis par exemple pour la recherche binaire si les indices du tableau peuvent devenir très grands. Il y avait un bogue dans de nombreuses versions de la recherche binaire , car elles servaient (a + b) / 2à calculer la moyenne. ne fonctionne pas correctement. La bonne solution est d’utiliser à la (a + b) >>> 1place.)

Knuth a déclaré:

L'optimisation prématurée est la racine de tout Mal.

Je suggère donc d'utiliser x /= 2;

De cette façon, le code est facile à comprendre et je pense également que l'optimisation de cette opération sous cette forme, ne signifie pas une grande différence pour le processeur.

Jetez un œil à la sortie du compilateur pour vous aider à décider. J'ai exécuté ce test sur x86-64 avec
gcc (GCC) 4.2.1 20070719 [FreeBSD]

Voir également les sorties du compilateur en ligne sur godbolt .

Ce que vous voyez, c'est que le compilateur utilise une sarlinstruction (décalage vers la droite arithmétique) dans les deux cas, il reconnaît donc la similitude entre les deux expressions. Si vous utilisez la division, le compilateur doit également ajuster les nombres négatifs. Pour ce faire, il décale le bit de signe vers le bit de poids faible et l'ajoute au résultat. Cela résout le problème du coup par coup lors du déplacement de nombres négatifs, par rapport à ce que ferait une division.
Étant donné que le cas de division fait 2 changements, alors que le cas de changement explicite n'en fait qu'un, nous pouvons maintenant expliquer ici certaines des différences de performances mesurées par d'autres réponses.

Code C avec sortie d'assemblage:

Pour diviser, votre entrée serait

int div2signed(int a) {
  return a / 2;
}

et cela compile pour

    movl    %edi, %eax
    shrl    $31, %eax
    addl    %edi, %eax
    sarl    %eax
    ret

de même pour le décalage

int shr2signed(int a) {
  return a >> 1;
}

avec sortie:

    sarl    %edi
    movl    %edi, %eax
    ret

Juste une note ajoutée -

x * = 0,5 sera souvent plus rapide dans certains langages basés sur des machines virtuelles - notamment actionscript, car la variable ne devra pas être vérifiée pour la division par 0.

Utilisez x = x / 2; OR, x /= 2;car il est possible qu'un nouveau programmeur y travaille à l'avenir. Il lui sera donc plus facile de savoir ce qui se passe dans la ligne de code. Tout le monde peut ne pas être au courant de telles optimisations.

Je dis dans le but de programmer des compétitions. Généralement, ils ont de très grandes entrées où la division par 2 a lieu plusieurs fois et il est connu que l'entrée est positive ou négative.

x >> 1 sera meilleur que x / 2. J'ai vérifié sur ideone.com en exécutant un programme où plus de 10 ^ 10 divisions par 2 opérations ont eu lieu. x / 2 a pris près de 5,5 s tandis que x >> 1 a pris près de 2,6 s pour le même programme.

Je dirais qu'il y a plusieurs choses à considérer.

1. Bitshift devrait être plus rapide, car aucun calcul spécial n'est vraiment nécessaire pour décaler les bits, mais comme indiqué, il existe des problèmes potentiels avec les nombres négatifs. Si vous êtes assuré d'avoir des nombres positifs et que vous recherchez la vitesse, je recommanderais le bitshift.

2. L'opérateur de division est très facile à lire pour les humains. Donc, si vous recherchez la lisibilité du code, vous pouvez l'utiliser. Notez que le domaine de l'optimisation du compilateur a parcouru un long chemin, donc rendre le code facile à lire et à comprendre est une bonne pratique.

3. Selon le matériel sous-jacent, les opérations peuvent avoir des vitesses différentes. La loi d'Amdal est de rendre le cas commun rapide. Vous pouvez donc disposer d'un matériel capable d'effectuer différentes opérations plus rapidement que d'autres. Par exemple, multiplier par 0,5 peut être plus rapide que diviser par 2. (Certes, vous devrez peut-être prendre la parole pour la multiplication si vous souhaitez appliquer la division entière).

Si vous recherchez des performances pures, je recommanderais de créer des tests qui pourraient effectuer les opérations des millions de fois. Échantillonnez l'exécution plusieurs fois (la taille de votre échantillon) pour déterminer laquelle est statistiquement la meilleure avec votre système d'exploitation / matériel / compilateur / code.

En ce qui concerne le CPU, les opérations de décalage de bits sont plus rapides que les opérations de division. Cependant, le compilateur le sait et optimisera de manière appropriée dans la mesure du possible, afin que vous puissiez coder de la manière la plus logique et la plus simple possible en sachant que votre code fonctionne efficacement. Mais rappelez-vous qu'un unsigned intpeut (dans certains cas) être mieux optimisé qu'un intpour des raisons précédemment indiquées. Si vous n'avez pas besoin d'arithmatique signée, n'incluez pas le bit de signe.

x = x / 2; est le code approprié à utiliser .. mais une opération dépend de votre propre programme de la façon dont la sortie que vous souhaitez produire.

Rendez vos intentions plus claires ... par exemple, si vous voulez diviser, utilisez x / 2 et laissez le compilateur l'optimiser pour déplacer l'opérateur (ou autre chose).

Les processeurs d'aujourd'hui ne laisseront pas ces optimisations avoir un impact sur les performances de vos programmes.

La réponse à cela dépendra de l'environnement dans lequel vous travaillez.

• Si vous travaillez sur un microcontrôleur 8 bits ou quoi que ce soit sans prise en charge matérielle pour la multiplication, le décalage de bits est prévu et courant, et bien que le compilateur se transformera presque certainement x /= 2en x >>= 1, la présence d'un symbole de division soulèvera plus de sourcils dans cet environnement que en utilisant un décalage pour effectuer une division.
• Si vous travaillez dans un environnement ou une section de code critique pour les performances, ou si votre code peut être compilé avec l'optimisation du compilateur désactivée, x >>= 1un commentaire expliquant son raisonnement est probablement préférable pour des raisons de clarté.
• Si vous n'êtes pas dans l'une des conditions ci-dessus, rendez votre code plus lisible en utilisant simplement x /= 2. Mieux vaut sauver le prochain programmeur qui regarde votre code la double prise de 10 secondes sur votre opération de décalage que de prouver inutilement que vous saviez que le décalage était plus efficace sans optimisation du compilateur.

Tout cela suppose des entiers non signés. Le changement simple n'est probablement pas ce que vous souhaitez signer. En outre, DanielH soulève un bon point sur l'utilisation x *= 0.5de certains langages comme ActionScript.

mod 2, testez pour = 1. ne sais pas la syntaxe en c. mais cela peut être le plus rapide.

généralement le décalage à droite divise:

q = i >> n; is the same as: q = i / 2**n;

ceci est parfois utilisé pour accélérer les programmes au détriment de la clarté. Je ne pense pas que tu devrais le faire. Le compilateur est suffisamment intelligent pour effectuer automatiquement l'accélération. Cela signifie que vous ne gagnez rien au détriment de la clarté .

Jetez un œil à cette page de la programmation C ++ pratique.

Évidemment, si vous écrivez votre code pour le prochain gars qui le lira, optez pour la clarté de "x / 2".

Cependant, si la vitesse est votre objectif, essayez-le dans les deux sens et chronométrez les résultats. Il y a quelques mois, j'ai travaillé sur une routine de convolution bitmap qui impliquait de parcourir un tableau d'entiers et de diviser chaque élément par 2. J'ai fait toutes sortes de choses pour l'optimiser, y compris l'ancienne astuce consistant à remplacer "x >> 1" par "x / 2 ".

Quand j'ai effectivement chronométré les deux sens, j'ai découvert à ma grande surprise que x / 2 était plus rapide que x >> 1

Cela utilisait Microsoft VS2008 C ++ avec les optimisations par défaut activées.

En termes de performances. Les opérations de décalage du processeur sont nettement plus rapides que les codes d'opération de division. Donc, en divisant par deux ou en multipliant par 2, etc., tous bénéficient d'opérations de quart de travail.

Quant à l'apparence. En tant qu'ingénieurs, quand sommes-nous devenus si attachés aux cosmétiques que même les belles femmes ne les utilisent pas! :)

X / Y est correct ... et l'opérateur de décalage ">>" ... si nous voulons que deux divisent un entier, nous pouvons utiliser l'opérateur de dividende (/). L'opérateur shift est utilisé pour décaler les bits.

x = x / 2; x / = 2; nous pouvons utiliser comme ça ..

Alors que x >> 1 est plus rapide que x / 2, l'utilisation appropriée de >> lorsqu'il s'agit de valeurs négatives est un peu plus compliquée. Cela nécessite quelque chose de semblable au suivant:

// Extension Method
public static class Global {
    public static int ShiftDivBy2(this int x) {
        return (x < 0 ? x + 1 : x) >> 1;
    }
}