Comment l'opérateur + en C?

pour être pédant, la spécification C ne précise pas comment ajout est mis en œuvre.

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

le CPU utilise en interne circuits logiques pour mettre en œuvre l'ajout, et n'utilise pas de boucles, bitshifts, ou quoi que ce soit qui a une ressemblance étroite avec la façon dont C fonctionne.

quand vous ajoutez deux bits, voici le résultat: (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 en bitwise xor, vous pouvez obtenir la somme sans carry. Et si vous faites en bitwise et vous pouvez obtenir les bits de transport.

prolongeant cette observation pour les numéros à plusieurs bits 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 dégrade à:

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 vous vous débarrassez de la récursion et la convertir en une 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 à l'esprit l'explication du code devrait être plus simple:

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

Porter bits. Bit est à 1 si 1 bit vers la droite dans les deux opérandes est de 1.

y ^= x;  // x is used now

Addition sans retenue (Carry bits ignoré)

x = t;

Réutilisation x pour le mettre à porter

while(x)

répéter alors qu'il y a plus de bits de transport

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);
}

Semble que cette fonction montre comment + fonctionne réellement dans le arrière-plan

Pas de. habituellement (presque toujours) ajout d'entier traduit à la machine l'instruction add. Ceci démontre juste une implémentation alternative utilisant bitwise xor et et.

Semble que cette fonction montre comment + fonctionne en arrière-plan

Pas de. Ceci est traduit par l'instruction machine native add , qui utilise en fait le hardware adder, dans le ALU .

si vous vous demandez comment l'ordinateur ajoute, voici un adder de base.

tout dans l'ordinateur est fait en utilisant des portes logiques, qui sont la plupart du temps transistor. Le plein additionneur a demi-additionneurs.

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

dans cette vidéo, un demi-annonceur de base est affiché. Si vous voulez une brève description, c'est:

la moitié Adder ajoute deux bits donné. Les combinaisons possibles sont:

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

alors comment fonctionne la moitié de l'adder? Eh bien, il est composé de trois portes logiques, le and , xor et le nand . Le nand donne un courant positif si les deux entrées sont négatives, ce qui signifie que cela résout le cas de 0 et 0. Le xor donne une sortie positive d'entrée est positive et l'autre négative, ce qui signifie qu'il résout le problème de 1 et de 0. Le and donne une sortie positive seulement si les deux entrées sont positives, de sorte que résout le problème de 1 et 1. Donc, en gros, nous avons maintenant notre demi-vipère. Mais nous ne pouvons toujours ajouter que des bits.

maintenant nous faisons notre plein-adder. Un adder complet consiste à appeler le half-adder encore et encore. Maintenant ça a une portée. Lorsque nous ajoutons 1 et 1, on obtient un report 1. Donc ce que fait le plouc, c'est, il prend le carry de la moitié-adder, le stocke, et le passe comme un autre argument à la moitié-adder.

si vous êtes confus comment pouvez-vous passer le carry, vous essentiellement d'abord ajouter les bits en utilisant le half-adder, puis Ajouter la somme et le carry. Donc maintenant vous avez ajouté le carry, avec les deux bits. Donc vous le faites encore et encore, jusqu'à ce que les bits que vous avez à ajouter soient finis, et ensuite vous obtenez votre résultat.

surpris? C'est ce qui se passe réellement. Il ressemble à un long processus, mais l'ordinateur est-il en une fraction de nanoseconde, ou pour être plus précis, dans un demi-cycle d'horloge. Parfois, il est exécuté même dans un cycle d'horloge simple. Fondamentalement, l'ordinateur a le ALU (une partie majeure du CPU ), Mémoire, Bus, etc..

si vous voulez apprendre le matériel informatique, des portes logiques, la mémoire et L'ALU, et simuler un ordinateur, vous pouvez voir ce cours, à partir duquel j'ai appris tout cela: construire un Ordinateur moderne des premiers principes

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

c utilise une machine abstraite pour décrire ce que le code C fait. Le mode de fonctionnement n'est donc pas précisé. Il y a des "compilateurs" C qui compilent C dans un langage de script, par exemple.

mais, dans la plupart des implémentations C, + entre deux entiers plus petits que la taille de la machine sera traduit en une instruction d'assemblage (après de nombreuses étapes). L'instruction d'assemblage sera traduite en code machine et intégrée dans votre exécutable. L'assemblée est une langue "plus" de code machine, conçu pour être plus facile à lire qu'un tas de paniers binaire.

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

l'Unité de logique arithmétique peut avoir des additeurs et des multiplicateurs distincts, ou peut les mélanger.

l'Unité de logique arithmétique a un tas de transistors qui effectuent l'opération d'addition, puis produire la sortie. Cette sortie est acheminée via les signaux générés par le décodeur d'instructions, et stockée dans la mémoire ou les registres.

la disposition de ces transistors dans l'Unité de logique arithmétique et le décodeur d'instruction (ainsi que les pièces que j'ai glissées) sont gravés dans la puce à l'usine. Le motif 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 changements et des boucles qui ne décrivent pas ce qui se passe dans le temps (comme l'une après l'autre), mais plutôt dans l'espace -- il décrit les connexions entre les différents composants matériels. Ce code peut ressembler vaguement au code que vous avez posté ci-dessus.

les paragraphes ci-dessus résument de nombreuses parties et couches et contiennent des inexactitudes. C'est à la fois de ma propre incompétence (j'ai écrit à la fois du matériel et des compilateurs, mais je ne suis un expert en ni l'un ni l'autre) et parce que tous les détails demanderaient une carrière ou deux, et pas un SO post.

Ici est un post sur un 8-bit additionneur. Ici est un non-DONC post, où vous trouverez certains des additionneurs suffit d'utiliser operator+ dans le HDL! (Le HDL lui-même comprend + et génère le code adder de niveau inférieur pour vous).

presque n'importe quel processeur moderne qui peut exécuter le code C compilé aura le soutien de builtin pour l'addition entière. Le code que vous avez posté est une façon intelligente d'effectuer l'addition entière sans exécuter un ENTIER Ajouter opcode, mais ce n'est pas comment l'addition entière est normalement effectuée. En fait, la fonction linkage utilise probablement une certaine forme d'addition entière pour ajuster le pointeur de pile.

le code que vous avez posté repose sur l'observation que lorsque vous ajoutez x et y, Vous pouvez de le décomposer en morceaux ils ont en commun et les bits qui sont uniques à l'un de x ou y.

l'expression x & y (bitwise AND) 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éécrit comme la somme de deux fois les bits qu'ils ont en commun (car x et y contribuer 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 de gauche de 1 multiplie effectivement de deux).

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

donc si nous remplaçons x par la première valeur et y par la seconde, la somme devrait être inchangée. Vous pouvez penser à la première valeur comme le porte des additions bitwise, et la seconde comme le bit d'ordre bas des additions bitwise.

ce processus se poursuit jusqu'à ce que x soit zéro, auquel point y détient la somme.

le code que vous avez trouvé tente d'expliquer comment le matériel informatique très primitif pourrait mettre en œuvre une instruction" ajouter". Je dis " pourrait "parce que je peux garantir que cette méthode n'est pas utilisée par n'importe quel CPU, et je vais expliquer pourquoi.

Dans la vie normale, vous utilisez des nombres décimaux et vous avez appris à ajouter: Pour ajouter deux nombres, vous ajoutez le plus bas de deux chiffres. Si le résultat est inférieur à 10, vous écrivez le résultat et passez à la position numérique suivante. Si le résultat est de 10 ou plus, vous écrivez le résultat moins 10, passer au chiffre suivant, acheter pas oublier d'ajouter 1 plus. Par exemple: 23 + 37, vous ajoutez 3+7 = 10, vous écrivez 0 et n'oubliez pas d'ajouter 1 de plus pour la position suivante. À la position 10s, on ajoute (2+3) + 1 = 6 et on note. Le résultat est de 60 ans.

vous pouvez faire la même chose avec les nombres binaires. La différence est que les seuls chiffres sont 0 et 1, donc les seules sommes possibles sont 0, 1, 2. Pour un nombre 32 bits, vous manipuleriez une position de chiffre après l'autre. Et quelle n'est pas vraiment primitif du matériel informatique.

ce code fonctionne différemment. Vous savez que la somme de deux chiffres binaires est 2 si les deux chiffres sont 1. Donc si les deux chiffres sont 1 alors vous ajouteriez 1 plus à la position binaire suivante et écrivez 0. C'est ce que fait le calcul de t: il trouve tous les endroits où les deux chiffres binaires sont 1 ( & ) et les déplace vers le chiffre suivant la position (<< 1). Puis il fait le plus: 0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 est 2, mais nous écrire 0. C'est ce que fait l'excludive ou l'opérateur.

mais tous les 1 que vous avez eu à manipuler dans la position du prochain chiffre n'ont pas été manipulés. Ils doivent encore être ajoutés. C'est pourquoi le code fait une boucle: dans la prochaine itération, tous les extra 1 sont ajoutés.

pourquoi aucun processeur ne fait ça? Parce c'est une boucle, et les processeurs n'aiment pas les boucles, et c'est lent. C'est lent, car dans le pire des cas, 32 itérations sont nécessaires: si vous ajoutez 1 au nombre 0xffffff (32 1-bits), alors la première itération efface le bit 0 de y et définit x à 2. La deuxième itération efface le bit 1 de y et place x à 4. Et ainsi de suite. Il faut 32 itérations pour obtenir le résultat. Cependant, chaque itération doit traiter tous les bits de x et de y, ce qui prend beaucoup de matériel.

un processeur primitif ferait des choses aussi rapides que l'arithmétique décimale, de la position la plus basse à la position la plus haute. Il prend également 32 étapes, mais chaque étape ne traite que deux bits plus une valeur de la position de bit précédente, il est donc beaucoup plus facile à mettre en œuvre. Et même dans un ordinateur primitif, on peut se permettre de le faire sans avoir à implémenter des boucles.

un CPU moderne, rapide et complexe utilisera un"additionneur conditionnel". Surtout si le nombre de bits est élevé, par exemple un 64 bits adder, ça fait gagner du temps.

un adder 64 bits se compose de deux parties: D'abord, un adder 32 bits pour le plus bas 32 bits. Cet adder de 32 bits produit une somme, et un "carry" (un indicateur qu'un 1 doit être ajouté à la position bit suivante). Deuxièmement, deux additionneurs 32 bits pour les 32 bits supérieurs: L'un ajoute x + y, l'autre ajoute x + y + 1. Tous les trois additionneurs travailler en parallèle. Puis, lorsque le premier adder a produit son carry, le CPU ne fait que choisir lequel des deux résultats x + y ou x + y + 1 est la bonne, et vous avez le résultat complet. Donc un adder 64 bits ne prend qu'un tout petit peu plus de temps qu'un adder 32 bits, pas deux fois plus de temps.

les parties adder 32 bits sont à nouveau implémentées en tant qu'adders de somme conditionnelle, en utilisant plusieurs adders 16 bits, et les adders 16 bits sont des adders de somme conditionnelle, et ainsi de suite.

ma question Est: l'opérateur + est-il implémenté comme le code affiché sur la plupart des implémentations?

répondons à la question. Tous les opérateurs sont implémentés par le compilateur sous la forme d'une structure de données interne qui est éventuellement traduite en code après quelques transformations. Vous ne pouvez pas dire quel code sera généré par un simple ajout parce que presque aucun compilateur du monde réel ne génère de code pour des déclarations individuelles.

le compilateur est libre de générer n'importe quel code tant qu'il se comporte comme si les opérations réelles ont été effectuées selon la norme. Mais ce qui se passe réellement peut être quelque chose de complètement différent.

un exemple simple:

static int
foo(int a, int b)
{
    return a + b;
}
[...]
    int a = foo(1, 17);
    int b = foo(x, x);
    some_other_function(a, b);

il n'est pas nécessaire de générer des instructions supplémentaires ici. C'est parfaitement légal pour le compilateur de traduire ceci en:

some_other_function(18, x * 2);

ou peut-être que le compilateur remarque que vous appelez la fonction foo plusieurs fois de suite et qu'il s'agit d'une simple arithmétique et qu'elle générera des instructions vectorielles pour elle. Ou que le résultat de l'addition est utilisé pour l'indexation ultérieure des tableaux et que l'instruction lea sera utilisée.

vous ne pouvez tout simplement pas parler de la façon dont un opérateur est mis en œuvre parce qu'il n'est presque jamais utilisé seul.

dans le cas où une ventilation du code aide quelqu'un d'autre, prendre l'exemple x=2, y=6 :

x n'est pas zéro, donc commencer à ajouter à y :

while(2) {

x & y = 2 parce que

        x: 0 0 1 0  //2
        y: 0 1 1 0  //6
      x&y: 0 0 1 0  //2

2 <<1 = 4 parce que << 1 déplace tous les bits vers la gauche:

      x&y: 0 0 1 0  //2
(x&y) <<1: 0 1 0 0  //4

En résumé, la planque de ce résultat, 4 , dans t avec

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

maintenant appliquer le bitwise XOR "1519360920 y^=x :

        x: 0 0 1 0  //2
        y: 0 1 1 0  //6
     y^=x: 0 1 0 0  //4

x = t;

return y;

tout juste par intérêt, sur le processeur Atmega328P, avec le compilateur avr-g++, le code suivant implémente l'ajout d'un en soustrayant -1:

volatile char x;
int main ()
  {
  x = x + 1;  
  }

code généré:

00000090 <main>:
volatile char x;
int main ()
  {
  x = x + 1;  
  90:   80 91 00 01     lds r24, 0x0100
  94:   8f 5f           subi    r24, 0xFF   ; 255
  96:   80 93 00 01     sts 0x0100, r24
  }
  9a:   80 e0           ldi r24, 0x00   ; 0
  9c:   90 e0           ldi r25, 0x00   ; 0
  9e:   08 95           ret

noter en particulier que l'addition est faite par l'instruction subi (soustraire constante du registre) où 0xFF est effectivement -1 dans ce cas.

il est également intéressant de noter que ce transformateur particulier ne avoir une instruction addi , ce qui implique que les concepteurs ont pensé Que faire une soustraction du complément serait traitée adéquatement par les compilateurs-rédacteurs.

est-ce que cela permet de profiter du complément de two ou d'autres fonctionnalités dépendant de la mise en œuvre?

il serait probablement juste de dire que les rédacteurs de compilateurs tenteraient de mettre en œuvre l'effet voulu (en ajoutant un nombre à un autre) dans le plus efficace façon possible pour cela particulièrement l'architecture. Si cela nécessite de soustraire le complément, qu'il en soit ainsi.