k & r confondu avec les opérations sur les bits

L’exercice est le suivant: Ecrivez une fonction setbits (x, p, n, y) qui renvoie x avec les n bits qui commencent à la position p et se positionne sur les n bits les plus à droite de y, les autres bits restant inchangés.

Ma tentative de solution est la suivante:

#include  unsigned setbits(unsigned, int, int, unsigned); int main(void) { printf("%u\n", setbits(256, 4, 2, 255)); return 0; } unsigned setbits(unsigned x, int p, int n, unsigned y) { return (x >> (p + 1 - n)) | (1 << (n & y)); } 

C’est probablement inexact, mais suis-je sur le bon chemin ici? Si non, qu’est-ce que je fais mal? Je ne sais pas pourquoi je ne comprends pas parfaitement cela, mais j’ai passé environ une heure à essayer de le présenter.

Merci.

Voici votre algorithme:

  1. Si n est 0, retourne x.
  2. Prenez 1, et déplacez-le à gauche n fois, puis soustrayez 1. Appelez ce mask .
  3. Masque de décalage gauche p fois appeler ce mask2 .
  4. And x avec l’inverse de mask2. And y avec masque et décalage gauche p fois.
  5. Or les résultats de ces deux opérations et renvoient cette valeur.

Je pense que la réponse est une application légèrement modifiée de l’exemple getbits de la section 2.9.

Permet de le décomposer comme suit:

 Let bitssortingng x be 1 0 1 1 0 0 Let bitssortingng y be 1 0 1 1 1 1 positions -------->5 4 3 2 1 0 

Le réglage de p = 4 and n =3 nous donne la chaîne de bits de x qui est 0 1 1 . Il commence à 4 et se termine à 2 et couvre 3 éléments.

Ce que nous voulons faire est de remplacer 0 1 1 par 1 1 1 (les trois derniers éléments de la chaîne de bits y).

Oublions le décalage gauche / droit pour le moment et visualisons le problème comme suit:

Nous devons récupérer les trois derniers chiffres de la chaîne de bits y, qui est 1 1 1

Placez 1 1 1 directement sous les positions 4 3 and 2 de la chaîne de bits x.

Remplacez 0 1 1 par 1 1 1 tout en conservant le rest des bits intacts …

Voyons maintenant un peu plus en détail …

Ma première déclaration a été:

 We need to grab the last three digits from bitssortingng y which is 1 1 1 

La façon d’isoler les bits d’une chaîne de bits consiste à commencer par une chaîne de bits contenant tous les 0. Nous nous retrouvons avec 0 0 0 0 0 0 .

Les 0 ont cette propriété incroyable où bitwise ‘&’ ing avec un autre nombre nous donne tous les 0 et bitwise ‘|’ les avec un autre nombre nous restitue cet autre nombre.

0 par lui-même ne sert à rien ici … mais il nous dit que si nous ‘|’ les trois derniers chiffres de y avec un ‘0’, nous allons nous retrouver avec 1 1 1. Les autres bits de y ne nous concernent pas vraiment ici, nous devons donc trouver un moyen de mettre ces chiffres à zéro tout en conservant le trois derniers chiffres intacts. Nous avons essentiellement besoin du numéro 0 0 0 1 1 1 .

Voyons donc la série de transformations requirejses:

 Start with -> 0 0 0 0 0 0 apply ~0 -> 1 1 1 1 1 1 lshift by 3 -> 1 1 1 0 0 0 apply ~ -> 0 0 0 1 1 1 & with y -> 0 0 0 1 1 1 & 1 0 1 1 1 1 -> 0 0 0 1 1 1 

Et de cette façon, nous avons les trois derniers chiffres à utiliser pour le réglage …

Ma deuxième déclaration était:

Placez 1 1 1 directement sous les positions 4, 3 et 2 de la chaîne de bits x.

Vous trouverez un indice pour ce faire dans l’exemple de getbits de la section 2.9. Ce que nous soaps sur les positions 4,3 et 2 peut être trouvé à partir des valeurs p = 4 and n =3 . p est la position et n est la longueur du jeu de bits. Il s’avère que p+1-n nous donne le décalage du bit à partir du bit le plus à droite. Dans cet exemple particulier, p+1-n = 4 +1-3 = 2 .

So..Si nous faisons un décalage à gauche de 2 sur la chaîne 0 0 0 1 1 1 , nous nous retrouvons avec 0 1 1 1 0 0 . Si vous placez cette chaîne sous x, vous remarquerez que 1 1 1 aligné sur les positions 4 3 and 2 de x.

Je pense que je vais enfin arriver à quelque chose … la dernière déclaration que j’ai faite était

Remplacez 0 1 1 par 1 1 1 tout en conservant le rest des bits intacts …

Permet de revoir nos chaînes maintenant:

 x -> 1 0 1 1 0 0 isolated y -> 0 1 1 1 0 0 

Faire un bitwise ou sur ces deux valeurs nous donne ce dont nous avons besoin pour ce cas:

 1 1 1 1 0 0 

Mais cela échouerait si au lieu de 1 1 1 , nous avions 1 0 1 … donc si nous devons creuser un peu plus pour arriver à notre “solution miracle” …

Permet de regarder les deux chaînes ci-dessus une fois de plus …

 x -> bit by bit...1(stays) 0(changes) 1(changes) 1(changes) 0(stays) 0(stays) 

Donc, idéalement, nous avons besoin de la chaîne de bits 1 xxx 0 0 , où les x seront échangés avec des 1. Voici un saut d’intuition qui nous aidera.

 Bitwise complement of isolated y -> 1 0 0 0 1 1 & this with x gives us -> 1 0 0 0 0 0 | this with isolated y -> 1 1 1 1 0 0 (TADA!) 

Espérons que ce long post aidera les gens à rationaliser et à résoudre ces problèmes de masquage

Merci

Notez que ~0 << i vous donne un nombre dont les bits i moins significatifs sont mis à 0 et les autres bits à 1 . De même, ~(~0 << i) vous donne un nombre dont les bits i moins significatifs sont définis sur 1 et le rest sur 0 .

Maintenant, pour résoudre votre problème:

  1. Tout d'abord, vous voulez un nombre qui a tous les bits sauf les n bits qui commencent à la position p définis sur les bits de x . Pour cela, vous avez besoin d’un masque composé de 1 à tous les endroits sauf les n bits commençant à la position p :
    1. ce masque contient les bits les plus élevés (les plus significatifs), en commençant par le bit situé à la position p+1 .
    2. ce masque contient également les p+1-n bits les moins significatifs.
  2. Une fois que vous avez le masque ci-dessus, & de ce masque avec x vous donnera le nombre que vous vouliez à l'étape 1.
  3. Maintenant, vous voulez un nombre qui a les n bits les moins significatifs de y définis, décalés à gauche p+1-n bits.
    1. Vous pouvez facilement créer un masque dont les n bits les moins significatifs sont définis et que vous utilisez y pour extraire les n bits les moins significatifs.
    2. Ensuite, vous pouvez décaler ce nombre de p+1-n bits.
  4. Enfin, vous pouvez utiliser les résultats des étapes 2 et 3.2 pour obtenir votre numéro.

Clair comme de la boue? 🙂

(La méthode ci-dessus doit être indépendante de la taille des chiffres, ce qui est important, à mon avis.)

Edit : en regardant votre effort: n & y ne fait rien avec n bits. Par exemple, si n est 8, vous voulez les 8 derniers bits de y , mais n & y ne sélectionnera que le 4ème bit de y (8 en binary vaut 1000). Donc vous savez que ça ne peut pas être juste. De la même façon, le décalage x p+1-n fois vers la droite vous donne un nombre dont les p+1-n bits les plus significatifs sont mis à zéro et le rest des bits est constitué des bits les plus significatifs de x . Ce n'est pas ce que vous voulez non plus.