Opérations et décalages binarys

J’ai du mal à comprendre comment et pourquoi ce code fonctionne comme il le fait. Mon partenaire dans cette mission a terminé cette partie et je ne peux pas l’attraper pour savoir comment et pourquoi cela fonctionne. J’ai essayé différentes choses pour le comprendre, mais toute aide serait la bienvenue. Ce code utilise un complément à 2 et une représentation 32 bits.

/* * fitsBits - return 1 if x can be represented as an * n-bit, two's complement integer. * 1 <= n <= 32 * Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1 * Legal ops: ! ~ & ^ | + <> * Max ops: 15 * Rating: 2 */ int fitsBits(int x, int n) { int r, c; c = 33 + ~n; r = !(((x <>c)^x); return r; } 

 c = 33 + ~n; 

Ceci calcule le nombre de bits de poids fort restant après l’utilisation de n bits de poids faible.

 ((x << c)>>c 

Cela remplit les bits de poids fort avec la même valeur que le bit de signe de x .

 !(blah ^ x) 

Ceci est équivalent à

 blah == x 
  • Sur une plate-forme à complément à 2, -n équivaut à ~n + 1 . Pour cette raison, c = 33 + ~n sur une telle plate-forme est en fait équivalent à c = 32 - n . Ce c est destiné à représenter le nombre de bits de poids fort restant dans une valeur int 32 bits si n bits inférieurs sont occupés.

    Notez deux dépendances de plate-forme présentes dans ce code: plate-forme à complément 2, type int 32 bits.

  • Alors ((x << c) >> c est destiné à remplir de signets ces c bits d’ordre supérieur. Signifie que les valeurs de x qui ont 0 dans la position de bit n - 1 , ces bits d’ordre supérieur doivent être mis à zéro. Mais pour les valeurs de x qui ont 1 en position de bit n - 1 , ces bits d’ordre supérieur doivent être renseignés avec une valeur égale à 1 Ceci est important pour que le code fonctionne correctement pour les valeurs négatives de x .

    Cela introduit deux autres dépendances de la plate-forme: l’opérateur << qui se comporte bien lors du décalage de valeurs négatives ou lorsque 1 est décalé dans le bit de signe (formellement, il s'agit d'un comportement indéfini) et l'opérateur >> qui effectue l'extension de signe lors du décalage de valeurs négatives (formellement c'est défini par l'implémentation)

  • Le rest est, comme indiqué ci-dessus, juste une comparaison avec la valeur initiale de x !(a ^ b) est équivalent à a == b . Si les transformations ci-dessus n'ont pas détruit la valeur d'origine de x alors x s'inscrit effectivement dans n bits inférieurs de la représentation en complément à 2.

L’utilisation de l’opérateur complément au bit ( ~ unary) sur un entier signé présente des aspects définis et non définis par l’implémentation . En d’autres termes, ce code n’est pas portable, même si vous envisagez une implémentation de complément à deux.


Il est important de noter que même les représentations de complément à deux en C peuvent avoir des représentations de piège. 6.2.6.2p2 dit même ceci très clairement:

Si le bit de signe est à un, la valeur doit être modifiée de l’une des manières suivantes:

– la valeur correspondante avec le bit de signe 0 est annulée (signe et magnitude);

– le bit de signe a la valeur – (2 M) (complément à deux);

– le bit de signe a la valeur – (2 M – 1) (complément de uns).

Laquelle de ces conditions est définie par l’implémentation, ainsi que la valeur avec le bit de signe 1 et tous les bits de valeur zéro (pour les deux premiers) , ou avec le bit de signe et tous les bits de valeur 1 (pour le complément à un), est une représentation d’interruption ou une valeur normale.

L’accent est à moi. L’utilisation de représentations d’interruption est un comportement indéfini .

Certaines implémentations actuelles réservent cette valeur en tant que représentation d’interruption dans le mode par défaut. Le plus connu est le Unisys Clearpath Dordado sur OS2200 (voir 2-29) . Notez la date sur ce document. de telles implémentations ne sont pas nécessairement anciennes (d’où la raison pour laquelle je cite celle-ci).


Selon 6.2.6.2p4 , le décalage des valeurs négatives à gauche est également un comportement indéfini. Je n’ai pas fait beaucoup de recherches sur les comportements existants, mais je m’attendrais raisonnablement à ce qu’il y ait des implémentations qui s’étendent du signe, ainsi que des implémentations qui ne le font pas. Ce serait également un moyen de former les représentations de piège mentionnées ci-dessus, qui sont de nature indéfinie et donc indésirables. Théoriquement (ou peut-être quelque temps dans un avenir lointain ou pas si lointain), vous pourriez également faire face à des signaux “correspondant à une exception informatique” (c’est une catégorie standard C similaire à celle dans laquelle se trouve SIGSEGV , correspondant à des choses comme “division” par zéro “) ou autrement erratique et / ou des comportements indésirables …


En conclusion, la seule raison pour laquelle le code de la question fonctionne est, par coïncidence, que les décisions sockets par votre implémentation sont alignées correctement. Si vous utilisez l’implémentation que j’ai listée, vous constaterez probablement que ce code ne fonctionne pas comme prévu pour certaines valeurs.

Une telle magie lourde (comme cela a été décrit dans les commentaires) n’est pas vraiment nécessaire et ne me semble pas vraiment optimale. Si vous voulez quelque chose qui ne repose pas sur la magie (par exemple quelque chose de portable) pour résoudre ce problème, envisagez de l’utiliser (en fait, ce code fonctionnera pendant au moins 1 <= n <= 64 ):

 #include  int fits_bits(intmax_t x, unsigned int n) { uintmax_t min = 1ULL << (n - 1), max = min - 1; return (x < 0) * min + x <= max; }