Les opérateurs de décalage (<<, >>) sont-ils arithmétiques ou logiques en C ?

https://stackoverflow.com/questions/7622

08-06-2019
|

Question

En C, sont les opérateurs de décalage (<<, >>) arithmétique ou logique ?

La solution

Selon K&R 2e édition les résultats dépendent de l'implémentation pour les déplacements à droite des valeurs signées.

Wikipédia dit que C/C++ implémente « généralement » un décalage arithmétique sur les valeurs signées.

Fondamentalement, vous devez soit tester votre compilateur, soit ne pas vous y fier.Mon aide VS2008 pour le compilateur MS C++ actuel indique que leur compilateur effectue un décalage arithmétique.

Autres conseils

Lors d'un déplacement vers la gauche, il n'y a aucune différence entre le déplacement arithmétique et logique.Lors d'un déplacement vers la droite, le type de décalage dépend du type de valeur décalée.

(En guise d'information pour les lecteurs qui ne connaissent pas la différence, un décalage "logique" à droite de 1 bit décale tous les bits vers la droite et remplit le bit le plus à gauche avec un 0.Un décalage « arithmétique » laisse la valeur d'origine dans le bit le plus à gauche.La différence devient importante lorsqu’il s’agit de nombres négatifs.)

Lors du décalage d'une valeur non signée, l'opérateur >> en C est un décalage logique.Lors du décalage d'une valeur signée, l'opérateur >> est un décalage arithmétique.

Par exemple, en supposant une machine 32 bits :

signed int x1 = 5;
assert((x1 >> 1) == 2);
signed int x2 = -5;
assert((x2 >> 1) == -3);
unsigned int x3 = (unsigned int)-5;
assert((x3 >> 1) == 0x7FFFFFFD);

TL;DR

Considérer i et n être respectivement les opérandes gauche et droit d'un opérateur de décalage ;le type de i, après promotion entière, soit T.En supposant n en être [0, sizeof(i) * CHAR_BIT) - non défini autrement - nous avons ces cas :

| Direction  |   Type   | Value (i) | Result                   |
| ---------- | -------- | --------- | ------------------------ |
| Right (>>) | unsigned |    ≥ 0    | −∞ ← (i ÷ 2ⁿ)            |
| Right      | signed   |    ≥ 0    | −∞ ← (i ÷ 2ⁿ)            |
| Right      | signed   |    < 0    | Implementation-defined†  |
| Left  (<<) | unsigned |    ≥ 0    | (i * 2ⁿ) % (T_MAX + 1)   |
| Left       | signed   |    ≥ 0    | (i * 2ⁿ) ‡               |
| Left       | signed   |    < 0    | Undefined                |

^{† la plupart des compilateurs implémentent cela sous forme de décalage arithmétique}
^{‡ non défini si la valeur dépasse le type de résultat T ;type promu de i}

Déplacement

Le premier est la différence entre les décalages logiques et arithmétiques d'un point de vue mathématique, sans se soucier de la taille du type de données.Les décalages logiques remplissent toujours les bits rejetés avec des zéros tandis que le décalage arithmétique les remplit de zéros uniquement pour le décalage à gauche, mais pour le décalage à droite, il copie le MSB, préservant ainsi le signe de l'opérande (en supposant un complément à deux codage des valeurs négatives).

En d’autres termes, le décalage logique considère l’opérande décalé comme un simple flux de bits et les déplace, sans se soucier du signe de la valeur résultante.Le décalage arithmétique le considère comme un nombre (signé) et préserve le signe au fur et à mesure des décalages.

Un décalage arithmétique vers la gauche d'un nombre X par n équivaut à multiplier X par 2ⁿ et équivaut donc au décalage logique vers la gauche ;un changement logique donnerait également le même résultat puisque MSB tombe de toute façon à la fin et qu'il n'y a rien à préserver.

Un décalage arithmétique à droite d'un nombre X par n équivaut à une division entière de X par 2ⁿ SEULEMENT si X est non négatif !La division entière n'est rien d'autre qu'une division mathématique et rond vers 0 (tronc).

Pour les nombres négatifs, représentés par un codage en complément à deux, un décalage de n bits vers la droite a pour effet de le diviser mathématiquement par 2.ⁿ et arrondi vers −∞ (sol);ainsi le décalage vers la droite est différent pour les valeurs non négatives et négatives.

pour X ≥ 0, X >> n = X / 2ⁿ = tronc(X ÷ 2ⁿ)

pour X < 0, X >> n = plancher (X ÷ 2ⁿ)

où ÷ est une division mathématique, / est une division entière.Regardons un exemple :

37)₁₀ = 100101)₂

37 ÷ 2 = 18.5

37 / 2 = 18 (arrondir 18,5 vers 0) = 10010)₂ [résultat du décalage arithmétique vers la droite]

-37)₁₀ = 11011011)₂ (en considérant un complément à deux, représentation 8 bits)

-37 ÷ 2 = -18.5

-37 / 2 = -18 (arrondi de 18,5 vers 0) = 11101110)₂ [PAS le résultat d'un décalage arithmétique vers la droite]

-37 >> 1 = -19 (arrondi de 18,5 vers −∞) = 11101101)₂ [résultat du décalage arithmétique vers la droite]

Comme Guy Steele a souligné, cet écart a conduit à bugs dans plus d'un compilateur.Ici, les valeurs non négatives (mathématiques) peuvent être mappées à des valeurs non négatives non signées et signées (C) ;les deux sont traités de la même manière et leur déplacement vers la droite se fait par division entière.

Ainsi, la logique et l'arithmétique sont équivalentes en décalage à gauche et pour les valeurs non négatives en décalage à droite ;c'est dans le déplacement à droite des valeurs négatives qu'elles diffèrent.

Types d'opérandes et de résultats

Norme C99 §6.5.7:

Chacun des opérandes doit avoir des types entiers.

Les promotions entières sont effectuées sur chacun des opérandes.Le type du résultat est celui de l’opérande gauche promu.Si la valeur de l'opérande droit est négative ou est supérieure ou égale à la largeur de l'opérande gauche promu, le comportement n'est pas défini.

short E1 = 1, E2 = 3;
int R = E1 << E2;

Dans l'extrait ci-dessus, les deux opérandes deviennent int (en raison d'une promotion entière);si E2 était négatif ou E2 ≥ sizeof(int) * CHAR_BIT alors l'opération n'est pas définie.En effet, déplacer plus que les bits disponibles va sûrement déborder.Avait R été déclaré comme short, le int le résultat de l’opération de décalage serait implicitement converti en short;une conversion restrictive, qui peut conduire à un comportement défini par l'implémentation si la valeur n'est pas représentable dans le type de destination.

Décalage à gauche

Le résultat de E1 << E2 est E1 des positions de bits E2 décalées vers la gauche ;les bits libérés sont remplis de zéros.Si E1 a un type non signé, la valeur du résultat est E1×2^E2, réduit modulo un de plus que la valeur maximale représentable dans le type de résultat.Si E1 a un type signé et une valeur non négative, et E1×2^E2 est représentable dans le type de résultat, alors c'est la valeur résultante ;sinon, le comportement n'est pas défini.

Comme les décalages vers la gauche sont les mêmes pour les deux, les bits libérés sont simplement remplis de zéros.Il indique ensuite que pour les types non signés et signés, il s'agit d'un décalage arithmétique.Je l'interprète comme un décalage arithmétique puisque les décalages logiques ne se soucient pas de la valeur représentée par les bits, ils la considèrent simplement comme un flux de bits ;mais la norme ne parle pas en termes de bits, mais en le définissant en termes de valeur obtenue par le produit de E1 par 2^E2.

La mise en garde ici est que pour les types signés, la valeur doit être non négative et la valeur résultante doit être représentable dans le type de résultat.Sinon, l'opération n'est pas définie. Le type de résultat serait le type de E1 après application de la promotion intégrale et non le type de destination (la variable qui va contenir le résultat).La valeur résultante est implicitement convertie en type de destination ;si elle n'est pas représentable dans ce type, alors la conversion est définie par l'implémentation (C99 §6.3.1.3/3).

Si E1 est un type signé avec une valeur négative alors le comportement du décalage vers la gauche n'est pas défini. Il s’agit d’une voie facile vers un comportement indéfini qui peut facilement être négligé.

Maj droite

Le résultat de E1 >> E2 est les positions de bits E1 décalées vers la droite.Si E1 est de type non signé ou si E1 est de type signé et de 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.

Le décalage vers la droite pour les valeurs non signées et signées non négatives est assez simple ;les bits vacants sont remplis de zéros. Pour les valeurs négatives signées, le résultat du décalage vers la droite est défini par l'implémentation. Cela dit, la plupart des implémentations comme GCC et Visuel C++ implémentez le décalage vers la droite comme décalage arithmétique en préservant le bit de signe.

Conclusion

Contrairement à Java, qui possède un opérateur spécial >>> pour un décalage logique par rapport à l'habituel >> et <<, C et C++ n'ont qu'un décalage arithmétique, certaines zones restant indéfinies et définies par l'implémentation.La raison pour laquelle je les considère comme arithmétiques est due à la formulation standard de l'opération mathématiquement plutôt que de traiter l'opérande décalé comme un flux de bits ;c'est peut-être la raison pour laquelle il laisse ces domaines non définis par la mise en œuvre au lieu de simplement définir tous les cas comme des changements logiques.

En termes de type de changement que vous obtenez, l’important est le type de valeur que vous modifiez.Une source classique de bugs est lorsque vous déplacez un littéral pour, par exemple, masquer des bits.Par exemple, si vous souhaitez supprimer le bit le plus à gauche d'un entier non signé, vous pouvez essayer ceci comme masque :

~0 >> 1

Malheureusement, cela vous causera des ennuis car le masque aura tous ses bits définis car la valeur décalée (~ 0) est signée, donc un décalage arithmétique est effectué.Au lieu de cela, vous voudriez forcer un changement logique en déclarant explicitement la valeur comme non signée, c'est-à-direen faisant quelque chose comme ceci :

~0U >> 1;

Voici des fonctions pour garantir le décalage logique à droite et le décalage arithmétique à droite d'un int en C :

int logicalRightShift(int x, int n) {
    return (unsigned)x >> n;
}
int arithmeticRightShift(int x, int n) {
    if (x < 0 && n > 0)
        return x >> n | ~(~0U >> n);
    else
        return x >> n;
}

Lorsque vous faites - le changement de gauche par 1, vous multipliez par 2 - Déplacement à droite par 1 Vous divisez par 2

 x = 5
 x >> 1
 x = 2 ( x=5/2)

 x = 5
 x << 1
 x = 10 (x=5*2)

Eh bien, j'ai regardé c'est sur Wikipédia, et ils ont ceci à dire :

C, cependant, n'a qu'un seul opérateur de quart de travail, >>.De nombreux compilateurs C choisissent le bon changement à effectuer en fonction du type d'entier décalé;Les entiers souvent signés sont décalés à l'aide du décalage arithmétique, et les entiers non signés sont décalés à l'aide du décalage logique.

Il semble donc que cela dépend de votre compilateur.Également dans cet article, notez que le décalage vers la gauche est le même pour l'arithmétique et la logique.Je recommanderais de faire un test simple avec quelques nombres signés et non signés sur le cas limite (jeu de bits élevés bien sûr) et de voir quel est le résultat sur votre compilateur.Je recommanderais également d'éviter de dépendre de l'un ou de l'autre car il semble que C n'ait pas de norme, du moins s'il est raisonnable et possible d'éviter une telle dépendance.

Décalage à gauche <<

C'est en quelque sorte facile et chaque fois que vous utilisez l'opérateur shift, il s'agit toujours d'une opération au niveau du bit, nous ne pouvons donc pas l'utiliser avec une opération double et float.Chaque fois que nous laissons le décalage d'un zéro, il est toujours ajouté au bit le moins significatif (LSB).

Mais en décalage à droite >> nous devons suivre une règle supplémentaire et cette règle est appelée "copie de bit de signe".La signification de « copie de bit de signe » est si le bit le plus significatif (MSB) est défini, puis après un décalage vers la droite, le MSB sera défini s'il a été réinitialisé, puis il est à nouveau réinitialisé, cela signifie que si la valeur précédente était zéro, puis après un nouveau décalage, le bit est zéro si le bit précédent était un, puis après le décalage, il est à nouveau un.Cette règle n'est pas applicable pour un décalage à gauche.

L'exemple le plus important sur le décalage à droite si vous déplacez un nombre négatif vers le décalage à droite, puis après quelques décalages, la valeur atteint finalement zéro, puis après cela, si vous déplacez ce -1 un certain nombre de fois, la valeur restera la même.Vérifiez s'il vous plaît.

gcc utilisera généralement des décalages logiques sur les variables non signées et pour les décalages vers la gauche sur les variables signées.Le décalage arithmétique vers la droite est le plus important car il étendra la variable.

gcc l'utilisera le cas échéant, comme d'autres compilateurs sont susceptibles de le faire.

GCC fait

pour -ve -> Décalage arithmétique
Pour +ve -> Décalage Logique

Selon beaucoup c compilateurs :

<< est un décalage arithmétique vers la gauche ou un décalage vers la gauche au niveau du bit.
>> est un décalage arithmétique vers la droite ou un décalage vers la droite au niveau du bit.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow