Besoin d’aide pour comprendre la méthode “getbits ()” dans le chapitre 2 de K & R C

Au chapitre 2, la section sur les opérateurs au niveau des bits (section 2.9), j’ai du mal à comprendre le fonctionnement de l’une des méthodes.

Voici la méthode fournie:

unsigned int getbits(unsigned int x, int p, int n) { return (x >> (p + 1 - n)) & ~(~0 << n); } 

L’idée est que, pour le nombre x donné, les n bits commençant par la position p seront comptés à partir de la droite (le bit le plus à droite étant la position 0). Étant donné la méthode main() :

 int main(void) { int x = 0xF994, p = 4, n = 3; int z = getbits(x, p, n); printf("getbits(%u (%x), %d, %d) = %u (%X)\n", x, x, p, n, z, z); return 0; } 

La sortie est:

getbits(63892 (f994), 4, 3) = 5 (5)

J’obtiens des portions de ceci, mais j’ai des problèmes avec la “grande image”, principalement à cause des bribes (sans jeu de mots) que je ne comprends pas.

La partie qui me pose problème est la pièce complémentaire: ~(~0 << n) . Je pense que je reçois la première partie, traitant de x ; c’est cette partie (et ensuite le masque) avec laquelle je me bats – et comment tout se réunit pour récupérer ces bits. (Ce que j’ai vérifié, c’est avec du code et en vérifiant mes résultats avec calc.exe – Dieu merci, il a une vue binary!)

De l’aide?

Utilisons 16 bits pour notre exemple. Dans ce cas, ~ 0 est égal à

 1111111111111111 

Lorsque nous décalons à gauche ces n bits (3 dans votre cas), nous obtenons:

 1111111111111000 

parce que les 1 à gauche sont rejetés et les 0 alimentation à droite. Ensuite, le re-compléter donne:

 0000000000000111 

c’est donc un moyen astucieux d’obtenir n -1 bits dans la partie la moins significative du nombre.

Le “x bit” que vous décrivez a suffisamment décalé le nombre donné (f994) pour que les 3 bits les moins significatifs soient ceux que vous voulez. Dans cet exemple, les bits que vous demandez sont entourés par ‘.’ personnages.

 ff94 11111111100.101.00 # original number >> p+1-n [2] 0011111111100.101. # shift desired bits to right & ~(~0 << n) [7] 0000000000000.101. # clear all the other (left) bits 

Et là vous avez vos bits. Ta da !!

Je dirais que la meilleure chose à faire est de résoudre un problème à la main, de cette manière, vous comprendrez comment cela fonctionne.

Voici ce que j’ai fait en utilisant un int de 8 bits unsigned.

  1. Notre numéro est 75, nous voulons les 4 bits à partir de la position 6. L’appel de la fonction serait getbits (75,6,4);

  2. 75 en binary est 0100 1011

  3. Nous créons donc un masque de 4 bits de long commençant par le bit d’ordre le plus bas.

~ 0 = 1111 1111
<< 4 = 1111 0000
~ = 0000 1111

Ok nous avons notre masque.

  1. Maintenant, nous poussons les bits que nous voulons hors du nombre dans les bits d’ordre le plus bas afin de décaler le nombre binary 75 de 6 + 1-4 = 3.

0100 1011 >> 3 0000 1001

Nous avons maintenant un masque du nombre correct de bits dans l’ordre inférieur et les bits que nous voulons extraire du nombre initial dans l’ordre inférieur.

  1. donc nous et eux
   0000 1001 
& 0000 1111 ============ 0000 1001

la réponse est donc décimale 9.

Remarque: le grignotage d’ordre supérieur se compose de tous les zéros, ce qui rend le masquage redondant dans ce cas, mais cela aurait pu être différent de la valeur du nombre avec lequel nous avons commencé.

~(~0 << n) crée un masque sur lequel les n bits les plus à droite sont activés.

 0 0000000000000000 ~0 1111111111111111 ~0 << 4 1111111111110000 ~(~0 << 4) 0000000000001111 

ANDing le résultat avec quelque chose d'autre retournera ce qui est dans ces n bits.

Edit: Je voulais souligner la calculasortingce de ce programmeur que je me sers depuis toujours: AnalogX PCalc .

Personne n’en a encore parlé, mais dans ANSI C ~0 << n provoque un comportement indéfini.

Cela est dû au fait que ~0 est un nombre négatif et que les nombres négatifs décalés vers la gauche ne sont pas définis.

Référence: C11 6.5.7 / 4 (les versions précédentes avaient un texte similaire)

Le résultat de E1 << E2 est E1 positions de bits E2 décalées à gauche; les bits libérés sont remplis de zéros. [...] Si E1 a un type signé et une valeur non négative et que E1 × 2 E2 est représentable dans le type de résultat, il s'agit de la valeur résultante; sinon, le comportement n'est pas défini.

Dans K & R C, ce code s’appuyait sur la classe de système sur laquelle K & R avait été développé, décalant naïvement de 1 bit vers la gauche lors du décalage à gauche d’un numéro signé (et ce code s’appuyant également sur la représentation du complément à 2), mais certains autres Les systèmes ne partageant pas ces propriétés, le processus de normalisation C n'a pas défini ce comportement.

Donc, cet exemple n’est vraiment intéressant que comme curiosité historique, il ne devrait pas être utilisé dans aucun code réel depuis 1989 (sinon plus tôt).

En utilisant l’exemple: int x = 0xF994, p = 4, n = 3; int z = getbits (x, p, n);

et en se concentrant sur cet ensemble d’opérations ~ (~ 0 << n)

pour n’importe quel bit défini (10010011, etc.), vous voulez générer un “masque” qui extrait uniquement les bits que vous voulez voir. Donc 10010011 ou 0x03, je suis intéressé par xxxxx011. Quel est le masque qui va extraire cet ensemble? 00000111 Maintenant, je veux être indépendant de sizeof int, je vais laisser la machine faire le travail, c’est-à-dire commencer par 0 pour une machine d’octets c’est 0x00 pour une machine de mots c’est 0x0000 etc. Une machine 64 bits représenterait par 64 bits ou 0x0000000000000000

Maintenant, appliquez “not” (~ 0) et obtenez 11111111
déplacez le curseur vers la droite (<<) de n et obtenez 11111000
et “pas” cela et obtenez 00000111

donc 10010011 & 00000111 = 00000011
Vous vous rappelez comment fonctionnent les opérations booléennes?

Dans ANSI C ~0 >> n provoque un comportement indéfini

// le message sur le décalage à gauche provoquant un problème est faux.

caractère non signé m, l;

m = ~ 0 >> 4; produit 255 et est égal à ~ 0 mais,

m = ~ 0; l = m >> 4; produit la valeur correcte 15 identique à:

m = 255 >> 4;

il n’y a aucun problème avec le décalage gauche négatif ~0 << que ce soit