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

136

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

petit octet
la source
1
Quelle est la signification de l'arithmétique et de la logique? Question connexe pour les entrées signées: stackoverflow.com/questions/4009885/…
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功

Réponses:

97

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.

Ronnie
la source
141

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);
Greg Hewgill
la source
57
Si proche, Greg. Votre explication est presque parfaite, mais le déplacement d'une expression de type signé et de valeur négative est défini par l'implémentation. Voir la section 6.5.7 de l'ISO / CEI 9899: 1999.
Robᵩ
12
@Rob: En fait, pour le décalage à gauche et le nombre négatif signé, le comportement n'est pas défini.
JeremyP
5
En fait, le décalage à gauche entraîne également un comportement indéfini pour les valeurs signées positives si la valeur mathématique résultante (qui n'est pas limitée en taille de bits) ne peut pas être représentée comme une valeur positive dans ce type signé. L'essentiel est que vous devez faire preuve de prudence lorsque vous déplacez à droite une valeur signée.
Michael Burr
3
@supercat: Je ne sais vraiment pas. Cependant, je sais qu'il existe des cas documentés où du code dont le comportement n'est pas défini amène un compilateur à faire des choses très peu intuitives (généralement en raison d'une optimisation agressive - par exemple, voir l'ancien bogue du pointeur nul du pilote Linux TUN / TAP: lwn.net / Articles / 342330 ). À moins d'avoir besoin d'un remplissage de signe sur le décalage à droite (ce que je réalise est un comportement défini par l'implémentation), j'essaie généralement d'effectuer mes décalages de bits en utilisant des valeurs non signées, même si cela signifie utiliser des transtypages pour y arriver.
Michael Burr
2
@MichaelBurr: Je sais que les compilateurs hypermodernes utilisent le fait qu'un comportement qui n'a pas été défini par le standard C (même s'il avait été défini dans 99% des implémentations ) comme une justification pour transformer des programmes dont le comportement aurait été entièrement défini sur tous plates-formes sur lesquelles on pourrait s'attendre à ce qu'elles s'exécutent, dans des paquets sans valeur d'instructions machine sans comportement utile. J'admets, cependant (sarcasme) Je suis perplexe de savoir pourquoi les auteurs de compilateurs ont raté la possibilité d'optimisation la plus massive: omettre toute partie d'un programme qui, si elle est atteinte, entraînerait l'imbrication de fonctions ...
supercat
51

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 n 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 n 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 n 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 n = trunc (X ÷ 2 n )

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

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

37) 10 = 100101) 2

37 ÷ 2 = 18,5

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

-37) 10 = 11011011) 2 (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) 2 [PAS le résultat d'un décalage arithmétique à droite]

-37 >> 1 = -19 (arrondi de 18,5 vers −∞) = 11101101) 2 [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.

légendes2k
la source
1
Bonne réponse. En ce qui concerne l' arrondissement (dans la section intitulée Shifting ) - tours de décalage vers la droite vers la -Inffois négatifs et des nombres positifs. Arrondir vers 0 d'un nombre positif est un cas privé d'arrondi vers -Inf. Lors de la troncature, vous supprimez toujours les valeurs pondérées positivement, par conséquent vous soustrayez du résultat par ailleurs précis.
ysap
1
@ysap Ouais, bonne observation. Fondamentalement, arrondir vers 0 pour les nombres positifs est un cas particulier de l'arrondi plus général vers −∞; cela peut être vu dans le tableau, où les nombres positifs et négatifs que je l'avais notés comme arrondis vers −∞.
legends2k
17

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;
pseudo
la source
16

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;
}
John Scipione
la source
7

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)
Srikant Patnaik
la source
Dans x >> a et x << a si la condition est a> 0 alors la réponse est x = x / 2 ^ a, x = x * 2 ^ a respectivement alors Quelle serait la réponse si a <0?
JAVA
@sunny: a ne doit pas être inférieur à 0. C'est un comportement indéfini dans C.
Jeremy
4

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.

Mike Stone
la source
Bien que la plupart des compilateurs C aient utilisé un décalage arithmétique à gauche pour les valeurs signées, un tel comportement utile semble avoir été déconseillé. La philosophie actuelle du compilateur semble être de supposer que la performance d'un décalage à gauche sur une variable autorise un compilateur à supposer que la variable doit être non négative et donc à omettre tout code ailleurs qui serait nécessaire pour un comportement correct si la variable était négative .
supercat
0

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.

asifaftab87
la source
0

utilisera 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.

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

Cristián Romo
la source
-1

GCC fait

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

  2. Pour + ve -> Décalage logique

Alok Prasad
la source
-7

Selon beaucoup 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.
srinath
la source
3
«Décalage arithmétique à droite» et «décalage à droite au niveau du bit» sont différents. C'est le but de la question. La question posée, "Est-ce que l' >>arithmétique ou le bit (logique)?" Vous avez répondu " >>est arithmétique ou bit à bit". Cela ne répond pas à la question.
wchargin
Non, <<et les >>opérateurs sont logiques, pas arithmétiques
shjeff