Le bit change en C

Si le motif binary correspondant à un entier signé est décalé à droite, alors

1 vacant bit will be filled by the sign bit 2 vacant bit will be filled by 0 3 The outcome is implementation dependent 4 none of the above 

La réponse à cette question est la 3ème option .. Quelqu’un peut-il expliquer cela,

Donnez également quelques idées de base sur la théorie derrière les opérateurs de décalage gauche et de décalage droit dans la programmation en C. Par exemple

ce qui est rempli sur le bit vide lorsque l’une des opérations est effectuée. J’ai vérifié et remarqué que le décalage à gauche remplit le bit vide par 0 et le décalage à droite par 1. Merci d’effacer la logique …

C ne garantit pas qu’il existe un bit de signe, ou quoi que ce soit à propos de la représentation au niveau binary d’entiers, c’est pourquoi.

Pour le complément à deux , vous verrez généralement le bit de signe déplacé, mais cela dépend de la mise en œuvre.

Il faudrait que je vérifie la spécification pour savoir ce qui dépend de la mise en œuvre. Cependant, chaque mise en œuvre que j’ai utilisée au cours de plusieurs années de projets de systèmes intégrés a été judicieuse:

  • Les décalages à gauche décalent toujours dans un 0 au bit le plus bas. Aucune autre valeur n’a de sens.

  • Les décalages à droite dépendent du type de données. Un décalage à droite d’un entier signé duplique le bit haut alors qu’il décale le rest vers la droite. C’est ce qu’on appelle un “décalage arithmétique”, et a la propriété intéressante (en deux compléments arithmétiques, au moins) qu’il divise la valeur par deux tout en préservant le signe du nombre d’origine.

    Un décalage à droite d’un entier non signé décale le 0 du bit fort et est généralement appelé “décalage logique”.

Il est logique qu’une implémentation fournisse les deux types de décalage, car les deux sont utiles, et l’utilisation de l’option signée / non signée pour sélectionner la signification est un choix judicieux.

Edit: au moins une chose qui dépend absolument de l’implémentation est que le standard C ne spécifie pas (complètement) l’implémentation sous-jacente des entiers et leur stockage. Par exemple, il est possible de construire un compilateur C conforme pour une machine qui utilise l’arithmétique de complément. Il serait également possible (je pense) de construire un compilateur conforme pour une machine dont le stockage natif était signé BCD. (Non, je me suis trompé, voir ci-dessous.)

En pratique, le monde est à peu près décidé à utiliser le complément binary à deux pour la CPU et une partie du pédantisme est lancée.

Une partie de la question est donc de savoir comment définir le sens des opérateurs << et >> de manière stable quel que soit le système arithmétique sous-jacent utilisé.

IIRC, la définition de n<<1 est effectivement n*2 , et n>>1 est effectivement n/2 , avec une extension naturelle aux décalages de plus de 1 (mais pas plus de 31 ... il y aura des dragons indéfinis ...) et avec l'idée que l'opérateur >> conservera le signe s'il opère sur une valeur signée.

Edit 2: Pete Kirkham souligne dans sa réponse précise que la norme C interdit spécifiquement le cas effrayant d’une représentation BCD d’entiers, qu’il s’agisse de la magnitude signée ou du complément à dix. Je suis sûr que c'est une bonne chose, même si Knuth a utilisé une machine (éventuellement) BCD pour son exemple de code dans les premières éditions de The Art of Computer Programming .

Dans les rares cas où BCD est la bonne réponse, stockez-les dans un entier long non signé (complément à dix chiffres) ou un entier non signé à 64 bits (espace pour 16 caractères complément à dix ou 15 chiffres, signes et drapeaux) et utilisez un Une bibliothèque arithmétique soigneusement conçue pour les manipuler est logique.

En pratique, bien entendu, les implémentations en C mappent les opérateurs aussi directement que le standard l’autorise dans les instructions de la machine native de la CPU. Les auteurs de la norme étaient très conscients de l’existence de nombreuses façons de mettre en œuvre même des choses simples, telles que la représentation d’une valeur intégrale, et la norme C reflète ce fait en permettant à un nombre suffisant de comportements définis par la mise en œuvre permettant aux opérateurs de s’implémenter efficacement. machine.

L’alternative mène rapidement à un monde où toutes les opérations mathématiques sont complètement spécifiées et qui ne peuvent être efficacement mises en œuvre sur aucune machine.

ISO C99 requirejs un bit de signe quelque part dans la représentation, mais donne le choix entre divers schémas de complément / signe et de magnitude et permet le remplissage de bits, qui affectent tous le fonctionnement de >> .

Section 6.2.6.2 (Types d’entiers)

Pour les types entiers signés, les bits de la représentation d’object doivent être divisés en trois groupes: les bits de valeur, les bits de remplissage et le bit de signe. Il n’y a pas besoin de bits de remplissage; il doit y avoir exactement un bit de signe.

et

Section 6.5.7 (Opérateurs de décalage binary)

Le résultat de E1 >> E2 correspond aux positions de bit E2 décalées à droite de E1. 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é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.

Elle ne spécifie pas le compliment de 1, le compliment de 2, ni le signe et la magnitude utilisés, ni si le bit de signe est à gauche ou à droite des bits de valeur, ni où se trouve un remplissage, ce qui affecterait la sortie du >> opérateur sur les négatifs signés.

En réponse à la requête de RBerteig, C99 exclut une représentation BCD d’entiers:

Section 6.2.6.2 (Types d’entiers)

S’il y a N bits de valeur, chaque bit doit représenter une puissance différente de 2 comprise entre 1 et 2 N -1, de sorte que les objects de ce type soient capables de représenter des valeurs de 0 à 2 N -1 à l’aide d’une représentation binary pure; cela sera appelé la représentation de la valeur.

Les implémentations en langage C ont tendance à mapper les opérations de décalage de bits directement sur les instructions de code machine correspondantes. Etant donné que différentes architectures matérielles ont toujours fait des choses différentes, la spécification C tend à laisser les choses définies en termes d’implémentation de sorte que les implémentations C puissent tirer parti de toutes les offres matérielles.

Le résultat dépend de la mise en œuvre. Cependant, dans la pratique, chaque compilateur x86, PPC et MIPS avec lequel j’ai travaillé a suivi cette règle pour passer à droite:

  1. Si l’opérande est un entier signé, le bit vide est rempli avec le bit de signe (le bit le plus significatif)

  2. Si l’opérande est un entier non signé, le bit vide est rempli de zéro.

Comme le dit RBerteig, c’est ainsi que pour les entiers signés , n >> 1 = n / 2 (arrondi à la baisse ) pour n positif et négatif, et pour les entiers non signés , n >> 1 = n / 2 même pour n> 2 31 (sur une architecture 32 bits).

Les instructions matérielles correspondantes sont arithmétiques (extension de signe) et décalage logique (pas d’extension de signe); le compilateur choisit entre eux selon que l’opérande est signé ou non.