80 votes

Est-ce ainsi que l'opérateur + est implémenté en C ?

Lorsque l'on comprend comment les opérateurs primitifs tels que + , - , * et / sont implémentés en C, j'ai trouvé le bout de phrase suivant dans le document une réponse intéressante .

// replaces the + operator
int add(int x, int y) {
    while(x) {
        int t = (x & y) <<1;
        y ^= x;
        x = t;
    }
    return y;
}

Il semble que cette fonction démontre comment + travaille en fait en arrière-plan. Cependant, c'est trop confus pour que je puisse le comprendre. Je croyais depuis longtemps que de telles opérations se font à l'aide de directives d'assemblage générées par le compilateur !

Est-ce que le + mis en œuvre comme le code posté sur LE PLUS mises en œuvre ? Cela permet-il de tirer parti du complément à deux ou d'autres caractéristiques dépendant de l'implémentation ?

60 votes

J'imagine que la plupart des implémentations utiliseront le système natif add L'instruction machine, que la plupart des CPU possèdent et qui est implémentée comme un additionneur matériel qui fonctionne en quelques horloges.

3 votes

Oui, le + L'opérateur tire très probablement parti des fonctionnalités définies par la mise en œuvre. Ces caractéristiques sont appelées "langage machine" et "CPU". Quelle est votre question ? Si vous voulez savoir comment les expressions sont converties en code machine, lisez ce qui concerne la construction des compilateurs.

0 votes

Voulez-vous dire que le code que j'ai posté est totalement inutile, parce que + sont traduits en directives d'assemblage telles que add par le compilateur ?

184voto

nightcracker Points 34498

Pour être pédant, la spécification C ne précise pas comment l'addition est mise en œuvre.

Mais pour être réaliste, la + L'opérateur sur les types d'entiers inférieurs ou égaux à la taille de mot de votre CPU est traduit directement en une instruction d'addition pour le CPU, et les types d'entiers plus grands sont traduits en instructions d'addition multiples avec quelques bits supplémentaires pour gérer le débordement.

Le CPU utilise en interne des circuits logiques pour réaliser l'addition, et n'utilise pas de boucles, de décalages de bits, ou quoi que ce soit qui ressemble de près au fonctionnement du C.

12 votes

Cette réponse est excellente car elle est présentée avec une clarté et une simplicité inhabituelles. Je ne la trouve pas du tout trop pédante, mais simplement la bonne dose de pédanterie pour la question.

5 votes

En fait, les circuits logiques des processeurs peuvent être compilés à partir de HDL, et vous êtes susceptible de générer un additionneur en utilisant des boucles et des décalages de bits vaguement similaires à la suggestion de l'OP (mais seulement vaguement). Ces boucles et décalages de bits décriraient la disposition du matériel et la façon dont ils sont connectés. Là encore, dans le matériel de haut niveau, quelqu'un pourrait dérouler lesdites boucles et décalages de bits, ou même se passer du HDL et tracer manuellement le circuit pour quelque chose d'aussi critique en termes de performances qu'un additionneur.

5 votes

Un circuit additionneur linéaire fait exactement la même chose que le code C, mais la boucle est entièrement déroulée dans le matériel (32 fois).

77voto

Mohit Jain Points 6202

Lorsque vous additionnez deux bits, le résultat est le suivant : (table de vérité)

a | b | sum (a^b) | carry bit (a&b) (goes to next)
--+---+-----------+--------------------------------
0 | 0 |    0      | 0
0 | 1 |    1      | 0
1 | 0 |    1      | 0
1 | 1 |    0      | 1

Donc si vous faites xor par bit, vous pouvez obtenir la somme sans report. Et si vous faites bit à bit et vous pouvez obtenir les bits de report.

En étendant cette observation pour les nombres multibit a et b

a+b = sum_without_carry(a, b) + carry_bits(a, b) shifted by 1 bit left
    = a^b + ((a&b) << 1)

Une fois b est 0 :

a+0 = a

Donc l'algorithme se résume à :

Add(a, b)
  if b == 0
    return a;
  else
    carry_bits = a & b;
    sum_bits = a ^ b;
    return Add(sum_bits, carry_bits << 1);

Si on se débarrasse de la récursion et qu'on la convertit en boucle.

Add(a, b)
  while(b != 0) {
    carry_bits = a & b;
    sum_bits = a ^ b;

    a = sum_bits;
    b = carrry_bits << 1;  // In next loop, add carry bits to a
  }
  return a;

Avec l'algorithme ci-dessus en tête, l'explication du code devrait être plus simple :

int t = (x & y) << 1;

Bits de report. Le bit de report est 1 si 1 bit à droite dans les deux opérandes est 1.

y ^= x;  // x is used now

Addition sans retenue (bits de retenue ignorés)

x = t;

Réutiliser x pour le mettre à porter

while(x)

Répétez tant qu'il y a plus de bits de report


Une implémentation récursive (plus facile à comprendre) serait :

int add(int x, int y) {
    return (y == 0) ? x : add(x ^ y, (x&y) << 1);
}

Il semble que cette fonction démontre comment + fonctionne réellement dans la arrière-plan

Non. Habituellement (presque toujours) l'addition d'entiers se traduit par l'addition d'instructions machine. Ceci ne fait que démontrer une implémentation alternative utilisant xor et and par bit.

5 votes

C'est la meilleure réponse à mon avis, toutes les autres indiquent qu'il est généralement traduit en une seule instruction, mais celle-ci le fait et également explique la fonction donnée.

0 votes

@NickSweeting Merci. La question peut être interprétée de 2 façons et je pense que la réponse acceptée a bien interprété ce que le PO voulait demander.

25voto

Ashish Ahuja ツ Points 1925

Il semble que cette fonction démontre comment + fonctionne réellement en arrière-plan

Non. C'est traduit en langue maternelle add l'instruction machine, qui utilise en fait l'additionneur matériel, dans les ALU .

Si vous vous demandez comment l'ordinateur fait l'addition, voici une addition de base.

Tout dans l'ordinateur est réalisé à l'aide de portes logiques, qui sont pour la plupart constituées de transistors. L'additionneur complet comporte des demi-additionneurs.

Pour un tutoriel de base sur les portes logiques et les additionneurs, voir ce . La vidéo est extrêmement utile, bien que longue.

Dans cette vidéo, un demi-additionneur de base est présenté. Si vous voulez une brève description, c'est ici :

Le demi-additionneur additionne deux bits donnés. Les combinaisons possibles sont :

  • Ajouter 0 et 0 = 0
  • Additionner 1 et 0 = 1
  • Ajouter 1 et 1 = 10 (binaire)

Alors maintenant, comment fonctionne le demi-additionneur ? Eh bien, il est composé de trois portes logiques, les and , xor et le nand . Le site nand donne un courant positif si les deux entrées sont négatives, ce qui signifie qu'il résout le cas de 0 et 0. xor donne une sortie positive : l'une des entrées est positive, et l'autre négative, ce qui signifie qu'il résout le problème du 1 et du 0. and donne une sortie positive uniquement si les deux entrées sont positives, ce qui résout le problème du 1 et du 1. Donc, en gros, nous avons maintenant notre demi-additionneur. Mais nous ne pouvons toujours qu'ajouter des bits.

Maintenant nous faisons notre additionneur complet. Un additionneur complet consiste à appeler le demi-additionneur encore et encore. Maintenant, il y a une retenue. Quand on ajoute 1 et 1, on obtient une retenue de 1. Donc ce que fait l'additionneur complet, c'est qu'il prend la retenue du demi-additionneur, la stocke, et la passe comme un autre argument au demi-additionneur.

Si vous ne savez pas comment passer la retenue, vous commencez par additionner les bits en utilisant le demi-additionneur, puis vous additionnez la somme et la retenue. Maintenant, vous avez ajouté la retenue, avec les deux bits. Vous recommencez encore et encore, jusqu'à ce que les bits que vous devez ajouter soient terminés, et vous obtenez votre résultat.

Vous êtes surpris ? Voici comment cela se passe réellement. Le processus semble long, mais l'ordinateur le réalise en quelques fractions de nanoseconde, ou plus précisément, en un demi-cycle d'horloge. Parfois, il l'effectue même en un seul cycle d'horloge. En gros, l'ordinateur a le ALU (une partie importante de la CPU ), la mémoire, les bus, etc.

Si vous voulez apprendre le matériel informatique, des portes logiques, de la mémoire et de l'ALU, et simuler un ordinateur, vous pouvez consulter ce cours, grâce auquel j'ai appris tout cela : Construire un ordinateur moderne à partir des premiers principes

C'est gratuit si vous ne voulez pas de certificat électronique. La deuxième partie du cours aura lieu au printemps de cette année.

11 votes

Quelques millisecondes ? Pour un seul ajout ?

2 votes

L'addition avec deux valeurs enregistrées est généralement réalisée en une seule horloge.

5 votes

@Tamoghna Chowdhury : Essaie quelques fractions de nanoseconde. L'ajout de registre est IIRC une horloge sur les processeurs Intel récents, donc avec une vitesse d'horloge de plusieurs GHz ... Et c'est sans compter le pipelining, l'exécution superscalaire, et autres.

15voto

Yakk Points 31636

Le C utilise une machine abstraite pour décrire ce que le code C fait. La façon dont il fonctionne n'est donc pas spécifiée. Il existe des "compilateurs" C qui compilent réellement le C dans un langage de script, par exemple.

Mais, dans la plupart des implémentations C, + entre deux entiers plus petits que la taille des entiers de la machine sera traduite en une instruction d'assemblage (après de nombreuses étapes). L'instruction d'assemblage sera traduite en code machine et intégrée à votre exécutable. L'assembleur est un langage "à une étape de distance" du code machine, destiné à être plus facile à lire qu'un paquet de binaires emballés.

Ce code machine (après de nombreuses étapes) est ensuite interprété par la plate-forme matérielle cible, où il est interprété par le décodeur d'instructions du processeur. Ce décodeur d'instructions prend l'instruction et la traduit en signaux à envoyer le long des "lignes de commande". Ces signaux acheminent les données des registres et de la mémoire à travers l'unité centrale, où les valeurs sont additionnées, souvent dans une unité arithmétique et logique.

L'unité arithmétique et logique peut comporter des additionneurs et des multiplicateurs séparés, ou les mélanger.

L'unité arithmétique et logique comporte un ensemble de transistors qui effectuent l'opération d'addition, puis produisent la sortie. Cette sortie est acheminée par les signaux générés par le décodeur d'instructions et stockée en mémoire ou dans des registres.

La disposition desdits transistors dans l'unité arithmétique et logique et dans le décodeur d'instructions (ainsi que d'autres parties que j'ai passées sous silence) est gravée dans la puce à l'usine. Le modèle de gravure est souvent produit en compilant un langage de description du matériel, qui prend une abstraction de ce qui est connecté à quoi et comment ils fonctionnent et génère des transistors et des lignes d'interconnexion.

Le langage de description du matériel peut contenir des décalages et des boucles qui ne décrivent pas ce qui se passe. à temps (comme l'un après l'autre) mais plutôt dans l'espace -- il décrit les connexions entre les différentes parties du matériel. Ce code peut ressembler très vaguement au code que vous avez posté ci-dessus.

Ce qui précède passe sous silence de nombreuses parties et couches et contient des inexactitudes. Cela vient à la fois de ma propre incompétence (j'ai écrit à la fois du matériel et des compilateurs, mais je ne suis un expert ni dans l'un ni dans l'autre) et parce que des détails complets prendraient une carrière ou deux, et non un billet d'OS.

Ici est un poste de SO sur un additionneur de 8 bits. Ici est un post non-SO, où vous noterez que certains des additionneurs utilisent juste operator+ dans le HDL ! (Le HDL lui-même comprend + et génère le code d'addition de niveau inférieur pour vous).

14voto

Tom Karzes Points 4363

Presque tous les processeurs modernes capables d'exécuter un code C compilé disposent d'un support intégré pour l'addition d'entiers. Le code que vous avez posté est une façon intelligente d'effectuer une addition d'entier sans exécuter un opcode d'addition d'entier, mais ce n'est pas la façon dont l'addition d'entier est normalement effectuée. En fait, la liaison de la fonction utilise probablement une certaine forme d'addition d'entiers pour ajuster le pointeur de pile.

Le code que vous avez posté repose sur l'observation que lorsque l'on additionne x et y, on peut décomposer cette addition en bits qu'ils ont en commun et en bits qui sont uniques à l'un des deux.

L'expression x & y (AND par bit) donne les bits communs à x et y. L'expression x ^ y (bitwise exclusive OR) donne les bits qui sont uniques à l'un de x ou y.

La somme x + y peut être réécrite comme la somme de deux fois les bits qu'ils ont en commun (puisque x et y contribuent tous deux à ces bits) plus les bits qui sont uniques à x ou à y.

(x & y) << 1 est le double des bits qu'ils ont en commun (le décalage vers la gauche de 1 multiplie effectivement par deux).

x ^ y sont les bits qui sont uniques à l'un de x ou y.

Ainsi, si nous remplaçons x par la première valeur et y par la seconde, la somme devrait rester inchangée. Vous pouvez considérer la première valeur comme les carries des additions binaires, et la seconde comme le bit de poids faible des additions binaires.

Ce processus se poursuit jusqu'à ce que x soit égal à zéro, auquel cas y contient la somme.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X