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; 

Ici, x est un 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 le 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)

Est-ce que le premier ressemble à une division? Non. Si vous souhaitez diviser, utilisez x / 2 . Le compilateur peut l’optimiser pour utiliser le bit-shift si possible (cela s’appelle la réduction de la force), ce qui en fait une micro-optimisation inutile si vous le faites vous-même.

Pour emstackr: il y a tellement de raisons de favoriser l’utilisation de x = x / 2; Voilà quelque:

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

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

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

  • Si la division doit faire partie d’une expression plus grande, vous êtes plus susceptible d’obtenir 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

  • à réitérer – le compilateur le fera déjà pour vous de toute façon. En fait, il convertira la division par une constante en une série de décalages, 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 longtemps que les compilateurs ne sont pas assez intelligents pour optimiser ce genre de choses au besoin.

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

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

Si vous voulez que vos collègues vous haïssent ou rendent votre code difficile à lire, je choisirais sans aucun doute la première option.

Si vous voulez diviser un nombre par 2, allez avec le second.

Les deux ne sont pas équivalents, ils ne se comportent pas de la même manière si le nombre est négatif ou dans des expressions plus grandes – le paramètre bitshift 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 pour ce type de micro-optimisations.

Utilisez simplement la division ( / ), en supposant que ce soit plus clair. Le compilateur optimisera en conséquence.

Je suis d’accord avec les autres réponses, vous devriez privilégier x / 2 parce que son intention est plus claire et que le compilateur doit l’optimiser pour vous.

Cependant, une autre raison de préférer x / 2 à x >> 1 est que le comportement de >> dépend de l’implémentation si x est un int signé et négatif.

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

Le résultat de E1 >> E2 est E1 positions de bit E2 décalées à droite. Si E1 a un type non signé ou si E1 a 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 E1 a un type signé et une valeur négative, la valeur résultante est définie par l’implémentation.

x / 2 est plus clair et x >> 1 n’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 tenir compte de cela lorsque vous souhaitez traiter des nombres négatifs. Certains compilateurs peuvent convertir automatiquement x / 2 en x >> 1 s’ils savent que le nombre ne peut pas être négatif (même si je ne pouvais pas le vérifier).

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

(Ceci est une question C / C ++, les autres langages de programmation ont plus d’opérateurs. Pour Java, il y a aussi le décalage droit non signé, x >>> 1 , qui est différent. Il permet de calculer correctement la valeur moyenne de deux valeurs, de sorte que (a + b) >>> 1 retournera la valeur moyenne même pour les très grandes valeurs de a et b par exemple pour la recherche binary si les indices du tableau peuvent devenir très volumineux. de nombreuses versions de recherche binary , car elles ont utilisé (a + b) / 2 pour calculer la moyenne. Cela ne fonctionne pas correctement. La solution correcte consiste à utiliser (a + b) >>> 1 place.)

Knuth a dit:

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 oeil à la sortie du compilateur pour vous aider à décider. J’ai effectué 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 instruction sarl (arithmétique à décalage à droite) dans les deux cas, donc il reconnaît la similarité entre les deux expressions. Si vous utilisez la division, le compilateur doit également ajuster les nombres négatifs. Pour ce faire, il déplace le bit de signe jusqu’au bit de poids le plus bas et l’ajoute au résultat. Cela corrige le problème hors-tout lors du décalage des nombres négatifs, comparé à ce que ferait une division.
Étant donné que le cas de la division fait 2 décalages, alors que le cas du décalage explicite ne fait que 1, nous pouvons maintenant expliquer certaines des différences de performance mesurées par d’autres réponses ici.

Code C avec sortie d’assemblage:

Pour diviser, votre consortingbution serait

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

et cela comstack à

  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 diviser par 0.

Utilisez x = x / 2; OU x /= 2; Parce qu’il est possible qu’un nouveau programmeur y travaille à l’avenir. Il sera donc plus facile pour lui de savoir ce qui se passe dans la ligne de code. Tout le monde n’est peut-être pas au courant de ces optimisations.

Je dis dans le but de programmer des compétitions. Généralement, ils ont de très gros intrants où la division par 2 se produit plusieurs fois et il est connu que les intrants sont positifs ou négatifs.

x >> 1 sera meilleur que x / 2. J’ai vérifié sur ideone.com en lançant un programme où plus de 10 ^ 10 divisions par 2 opérations ont eu lieu. x / 2 a pris presque 5,5s alors que x >> 1 a pris près de 2,6s 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 des nombres négatifs. Si vous êtes sûr d’avoir des nombres positifs et que vous cherchez de la vitesse, je vous recommanderais de choisir 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, de sorte que 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 avoir du matériel capable d’effectuer différentes opérations plus rapidement que d’autres. Par exemple, la multiplication par 0,5 peut être plus rapide que la division par 2. (Il se peut que vous deviez prendre la parole de la multiplication si vous souhaitez imposer une division entière).

Si vous recherchez des performances pures, je vous recommande de créer des tests capables d’effectuer les opérations des millions de fois. Échantillonnez l’exécution plusieurs fois (la taille de votre échantillon) pour déterminer celle qui correspond le mieux à votre système d’exploitation / matériel / compilateur / code.

En ce qui concerne le processeur, les opérations de décalage binary sont plus rapides que les opérations de division. Toutefois, le compilateur le sait et s’optimise de manière appropriée dans la mesure du possible, de sorte que vous pouvez coder de la manière la plus logique possible en sachant que votre code fonctionne efficacement. Mais rappelez-vous qu’un unsigned int peut (dans certains cas) être mieux optimisé qu’un int pour des raisons déjà mentionné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 manière dont vous souhaitez produire les résultats.

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

Les processeurs actuels ne permettent pas à ces optimisations d’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 tout ce qui ne prend pas en charge le matériel pour la multiplication, le décalage des bits est attendu et courant, et si le compilateur va presque certainement x /= 2 en x >>= 1 , la présence d’une division Le symbole soulèvera plus de sourcils dans cet environnement que d’utiliser un quart pour effectuer une division.
  • Si vous travaillez dans un environnement ou une section de code critique ou si votre code peut être compilé avec l’optimisation du compilateur désactivée, x >>= 1 avec un 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 examine votre code de la double prise de 10 secondes sur votre travail que de prouver inutilement que le changement était plus efficace sans optimisation du compilateur.

Tous ceux-ci supposent des entiers non signés. Le simple changement n’est probablement pas ce que vous voulez signer. De plus, DanielH soulève un bon point en utilisant x *= 0.5 pour certaines langues comme ActionScript.

mod 2, test pour = 1. dunno la syntaxe en c. mais cela peut être le plus rapide.

en général, le décalage de droite divise:

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

cela est parfois utilisé pour accélérer les programmes au désortingment de la clarté. Je ne pense pas que tu devrais le faire. Le compilateur est assez intelligent pour effectuer automatiquement l’accélération. Cela signifie que la mise en poste ne vous rapporte rien au désortingment de la clarté .

Jetez un coup d’oeil à cette page de la programmation pratique en C ++.

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

Toutefois, si la vitesse est votre objective, 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 consistait à parcourir un tableau d’entiers et à diviser chaque élément par 2. J’ai fait toutes sortes de choses pour l’optimiser, y compris la substitution de “x >> 1” à “x / 2 “.

Lorsque j’ai chronométré dans 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 performance. Les opérations de décalage du processeur sont beaucoup plus rapides que les codes d’opération de division. Ainsi, la division par deux ou la multiplication par 2, etc., profite toutes des opérations de poste.

En ce qui concerne le look and feel. En tant qu’ingénieurs, sums-nous devenus si attachés aux cosmétiques que même les plus belles ne l’utilisent pas! 🙂

X / Y est un correct … et l’opérateur “>>” décalé si nous voulons que deux divisent un entier, nous pouvons utiliser l’opérateur de dividende (/). opérateur de décalage est utilisé pour déplacer les bits ..

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

Alors que x >> 1 est plus rapide que x / 2, l’utilisation correcte de >> pour traiter les valeurs négatives est un peu plus compliquée. Cela nécessite quelque chose de similaire à ce qui suit:

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