Opérations au niveau du bit et des changements

Im un peu de mal à comprendre comment et pourquoi ce code fonctionne de la manière qu'il le fait. Mon partenaire dans cette mission terminé cette partie et je ne peux pas mettre la main sur lui pour savoir comment et pourquoi cela fonctionne. J'en ai essayé des choses différentes pour le comprendre, mais toute aide serait grandement appréciée. Ce code est à l'aide de complément de 2 et une de 32 bits représentation.

/* 
 * 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)>>c)^x);
    return r;
}
C'est lourd de sorcellerie. Vous n'êtes pas vraiment censé comprendre, il suffit de l'accepter comme la sagesse d'en haut. Indice: Il s'adapte si tous les bits à gauche de la position n-1 ont la même valeur que le peu que la position n-1.
Découvrez ce que chaque opérateur n' (et comprendre complément de 2), puis discuter de ce qui allait arriver à différentes valeurs d'entrée. Il faut beaucoup de pratique pour être en mesure de facilement lire quelque chose comme ci-dessus.
c'est... magnifique :O
nice sort! vraiment magique

OriginalL'auteur Scalahansolo | 2013-02-09

  1. 15
    c = 33 + ~n;

    Ce calcule combien d'ordre élevé de bits restants après l'utilisation de n bits d'ordre bas.

    ((x << c)>>c

    Cela remplit les ordre élevé de bits avec la même valeur que le bit de signe de x.

    !(blah ^ x)

    C'est l'équivalent de

    blah == x
    Juste par intérêt, je me demande pourquoi ils n'ont pas l'utiliser (x & ~(1 << c)) au lieu de ((x >> c) << c)? Il aurait éliminé l'intermédiaire de dépendance aurait peut-être sauvé un cycle ou deux sur un out-of-order pipeline du processeur.
    Je suis sûr qu'il ya plusieurs façons de faire la même chose.
    Il travaillera si x est négatif?
    Il ne fonctionne pas correctement avec les négatifs entrées. Le but de (x << c) >> c n'est pas de nul le plus élevé de bits d'ordre (comme cette réponse indique à tort), mais plutôt pour signe de remplissage. Pour les valeurs négatives de la matière de remplissage est 1, pas 0. C'est exactement ce que fait ce code de travail pour les valeurs négatives.
    Oui, mais il n'est pas juste. Cette mise en œuvre s'appuie également sur une partie du positif valeurs de devenir négatif au moment de leur haute-bit afin obtient décalé dans signe-position du bit. Cela est essentiel pour faire de ce code de rejeter, par exemple, (5, 3) d'entrée. Bien sûr, officiellement c'est UB.

    OriginalL'auteur Code-Apprentice

  2. 12

    • Sur un 2-complément de plate-forme -n est équivalent à ~n + 1. Pour cette raison, c = 33 + ~n sur une telle plate-forme est en fait équivalent à c = 32 - n. Cette c est destiné à représenter combien d'ordre supérieur bits restent en 32 bits int valeur si n bits de poids faible sont occupés.

      Remarque deux morceaux de plate-forme de dépendance présents dans ce code: 2-complément de plate-forme 32 bits int type.

    • Puis ((x << c) >> c est destiné à de connexion remplir ceux c d'ordre supérieur bits. Signe de remplissage signifie que ces valeurs de x qui ont 0 de position n - 1, ces bits doivent être mis à zéro. Mais pour ceux qui les valeurs de x qui ont 1 de position n - 1, ces bits doivent être remplies avec de 1s. Ceci est important pour que le code fonctionne correctement pour les valeurs négatives de x.

      Cela introduit un autre deux morceaux de plate-forme de dépendance: << opérateur qui se comporte bien lors du passage des valeurs négatives ou lorsque 1 est décalé dans le bit de signe (officiellement c'est un comportement indéfini) et >> de l'opérateur qui effectue la connexion extension lors du passage des valeurs négatives (officiellement c'est la mise en œuvre définies par l')

    • Le reste est, comme répondu plus haut, juste une comparaison avec la valeur d'origine de x: !(a ^ b) est équivalent à a == b. Si les transformations ne détruit pas la valeur d'origine de x puis x en effet s'insérer dans n bits de poids faible de 2-complément de la représentation.

    OriginalL'auteur AnT

  3. 3

    En utilisant le complément bit à bit (unaire ~) opérateur sur un entier signé a la mise en œuvre définis et indéfinis les aspects. En d'autres termes, ce code n'est pas portable, même si l'on considère uniquement en complément à deux implémentations.

    Il est important de noter que, même en complément à deux représentations en C peut piège des représentations. 6.2.6.2p2 même des membres de cette très clairement:

    Si le bit de signe est l'un, la valeur doit être modifiée dans l'une des façons suivantes:

    -- la valeur correspondante avec le bit de signe est 0 annulé (signe et l'ampleur);

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

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

    Lequel de ces cas est la mise en œuvre définies, si la valeur du bit de signe 1 et tous les bits à zéro (pour les deux premiers), ou avec le bit de signe et tous les bits 1 (pour " compléter), est un piège de la représentation ou une valeur normale.

    L'emphase est mienne. À l'aide de piège des représentations est un comportement indéterminé.

    Il y a des implémentations réelles que réserve de valeur comme un piège de la représentation dans le mode par défaut. Le notable, j'ai tendance à citer est Unisys Clearpath Dordado sur OS2200 (aller à 2-29). Notez la date sur le document; leur mise en œuvre ne sont pas nécessairement anciens (d'où la raison pour laquelle je cite celui-ci).

    Selon 6.2.6.2p4, le déplacement des valeurs négatives à gauche est un comportement indéterminé, trop. Je n'ai pas fait beaucoup de recherche sur ce que les comportements sont là, dans la réalité, mais je raisonnablement s'attendre à ce qu'il pourrait y avoir des implémentations qui signe-les étendre, ainsi que des implémentations qui ne le sont pas. Ce serait également un moyen de former le piège des représentations mentionné ci-dessus, qui ne sont pas définis dans la nature et donc indésirables. Théoriquement (ou peut-être un peu dans le lointain ou pas-si-lointain futur), vous pouvez également face à des signaux ", correspondant à un calcul d'exception" (c'est un C catégorie standard, semblable à celle qui SIGSEGV tombe, correspondant à des choses comme "division par zéro") ou autrement irrégulière et/ou de comportements indésirables...

    En conclusion, la seule raison pour laquelle le code de la question des œuvres est par coïncidence que les décisions de votre mise en œuvre fait arriver à aligner dans le droit chemin. Si vous utilisez la mise en œuvre que j'ai énumérés, vous trouverez probablement que ce code ne fonctionne pas comme prévu pour certaines valeurs.

    Tels lourd wizardry (comme il l'a été décrit dans les commentaires) n'est pas vraiment nécessaire, et n'a pas vraiment l'air optimale pour moi. Si vous voulez quelque chose qui ne repose pas sur magie (par exemple, quelque chose de portable) pour résoudre ce problème, envisager d'utiliser cela (en fait, ce code fonctionne pour au moins 1 <= n <= 64):

    #include <stdint.h>

int fits_bits(intmax_t x, unsigned int n) {
    uintmax_t min = 1ULL << (n - 1),
              max = min - 1;
    return (x < 0) * min + x <= max;
}
    La question, dit: "Ce code est à l'aide de complément de 2 et une de 32 bits représentation". de sorte que vos objections ne sont pas pertinents. ~ ne peut pas produire un piège de la représentation en complément de 2 (6.2.6.2/1 note de bas de page 53)
    N'utilisez pas d'information notes de bas de page pour contrer les références normatives.
    Juste point , cependant la valeur du bit de signe définir et tous les bits à zéro ne peut pas être produite par le présent code, de toute façon (dans les conditions données).
    Si vous continuez la lecture, vous pouvez noter que je mentionne l'UB de changer les valeurs négatives à gauche... vous dites que ce n'est pas pertinent ici?
    De même, est que cette réponse est toujours digne d'un downvote, en dépit de faire part d'un problème qui est certainement pertinente?

    OriginalL'auteur autistic