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

Selon la 2e édition de K&R, les résultats dépendent de la mise en œuvre pour les décalages corrects 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.

En gros, 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.

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

(En guise d'arrière-plan pour les lecteurs qui ne connaissent pas la différence, un décalage «logique» vers la 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érons iet ncomme étant respectivement les opérandes gauche et droit d'un opérateur de décalage; le type de i, après la promotion entière, être T. En supposant nêtre dans [0, sizeof(i) * CHAR_BIT)- indé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
‡ indéfini si la valeur dépasse le type de résultat T; type de i promu}

Déplacement

Tout d'abord, il y a 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 le 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 codage complémentaire à deux pour les 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 lorsque les décalages sont effectués.

Un décalage arithmétique à gauche d'un nombre X par n équivaut à multiplier X par 2 ⁿ et équivaut donc à un décalage logique à gauche; un décalage 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 droit d'un nombre X par n équivaut à une division entière de X par 2 ⁿ UNIQUEMENT si X est non négatif! La division entière n'est rien d'autre qu'une division mathématique et arrondie vers 0 ( trunc ).

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

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

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

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

37) ₁₀ = 100101) ₂

37 ÷ 2 = 18,5

37/2 = 18 (arrondi 18,5 vers 0) = 10010) ₂ [résultat du décalage arithmétique à 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 à droite]

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

Comme l'a souligné Guy Steele , cette divergence a conduit à des bogues 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écalage vers la droite se fait par division entière.

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

Opérande et types de résultat

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 de code ci-dessus, les deux opérandes deviennent int(en raison de la promotion d'entiers); si E2était négatif ou E2 ≥ sizeof(int) * CHAR_BITalors l'opération n'est pas définie. C'est parce que le décalage de plus que les bits disponibles va sûrement déborder. Avait Rété déclaré comme short, le intré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 décalé à gauche des positions de bits E2; les bits vides sont remplis de zéros. Si E1 a un type non signé, la valeur du résultat est E1 × 2 ^E2 , modulo réduit 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 à gauche sont les mêmes pour les deux, les bits vides sont simplement remplis de zéros. Il indique ensuite que pour les types non signés et non signés, il s'agit d'un décalage arithmétique. J'interprète cela comme un décalage arithmétique puisque les décalages logiques ne se soucient pas de la valeur représentée par les bits, il la regarde simplement comme un flux de bits; mais le standard ne parle pas en termes de bits, mais en le définissant en termes de valeur obtenue par le produit de E1 avec 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 l'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, le comportement du décalage vers la gauche n'est pas défini. C'est une voie facile vers un comportement indéfini qui peut facilement être négligé.

Shift vers la droite

Le résultat de E1 >> E2 est des positions de bits E1 décalées vers la droite E2. 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 est la partie intégrale 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 à droite pour les valeurs non négatives non signées et signées est assez simple; les bits vides 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 Visual C ++ implémentent le décalage vers la droite en tant que décalage arithmétique en préservant le bit de signe.

Conclusion

Contrairement à Java, qui a un opérateur spécial >>>pour le décalage logique en dehors de l'habituel >>et <<, C et C ++ ont seulement un décalage arithmétique avec certaines zones non définies et définies par l'implémentation. La raison pour laquelle je les considère comme arithmétiques est due au libellé 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 zones non définies par l'implémentation au lieu de simplement définir tous les cas comme des décalages logiques.

En ce qui concerne le type de changement que vous obtenez, l'important est le type de valeur que vous changez. Une source classique de bogues 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 posera des problèmes 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 voudrez forcer un décalage logique en déclarant explicitement la valeur comme non signée, c'est-à-dire en faisant quelque chose comme ceci:

~0U >> 1;

Voici des fonctions pour garantir un décalage logique à droite et un 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 - décalage gauche par 1 vous multipliez par 2 - décalage droit 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, je l'ai recherché sur wikipedia , et ils ont ceci à dire:

C, cependant, n'a qu'un seul opérateur de décalage vers la droite, >>. De nombreux compilateurs C choisissent le décalage à droite à effectuer en fonction du type d'entier déplacé; souvent les entiers signés sont décalés en utilisant le décalage arithmétique, et les entiers non signés sont décalés en utilisant le décalage logique.

Il semble donc que cela dépend de votre compilateur. Toujours dans cet article, notez que le décalage à gauche est le même pour l'arithmétique et la logique. Je recommanderais de faire un test simple avec des nombres signés et non signés sur le cas de la bordure (ensemble 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'a 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 de décalage, c'est toujours une opération au niveau du bit, donc nous ne pouvons pas l'utiliser avec une opération double et flottante. Chaque fois que nous quittons 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 que si le bit le plus significatif ( MSB) est défini, puis après un décalage vers la droite à nouveau, le MSBsera mis à 1 s'il a été réinitialisé puis il est à nouveau réinitialisé, ce qui signifie que si la valeur précédente était zéro, après un nouveau décalage, le le bit est nul 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 un certain décalage, la valeur atteint finalement zéro, puis après cela, si vous décalez ce -1 un nombre de fois quelconque, la valeur restera la même. Vérifiez s'il vous plaît.

gccutilisera généralement des décalages logiques sur des variables non signées et pour des décalages à gauche sur des variables signées. Le décalage arithmétique à droite est le plus important car il signera étendre la variable.

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

GCC fait

1. pour -ve -> Décalage arithmétique

2. Pour + ve -> Décalage logique

Selon beaucoup c compilateurs:

1. << est un décalage arithmétique à gauche ou un décalage à gauche au niveau du bit.
2. >> est un décalage arithmétique à droite ou un décalage à droite au niveau du bit.