Un aperçu des opérations au niveau du bit

Le message suivant est extrait d'un référentiel que j'ai créé pour aider à apprendre (et enseigner) les opérations au niveau du bit. Vous pouvez trouver ce dépôt ici, et je vous suggère de le vérifier : vous y trouverez des exemples de code et des solutions.

Introduction

Le but de ce référentiel est de vous familiariser avec les opérations au niveau du bit, en expliquant ce qu'elles sont, comment elles fonctionnent et à quoi elles peuvent être utilisées.

Chapitre 1 : Tout est binaire

En C (et dans la plupart des langages de haut niveau), nos variables ont des types. Ces types sont révélateurs de plusieurs choses. Bien sûr, une variable de type int stockera une valeur entière, mais la clé pour comprendre ces opérations au niveau du bit est de savoir que sous le capot, tous les types sont stockés en mémoire (n'importe où, pile, tas, n'importe où) sous forme binaire. Voici un exemple de ce qui se passe lorsque vous stockez une valeur entière simple sur la pile en C :

int main(int argc, char** argv) {
    int x = 2;
    return 0;
}

Après la compilation en assembly, le code pourrait ressembler à ceci (j'utilise ici l'assembly ARM et j'ai annoté le code à l'aide de commentaires) :

.section .text
.global main

main:
    ; Set up the stack for the function
    stp x29, x30 [sp, -16]! ; Save previous frame pointer & link register
    mov x29, sp ; Setup a new frame pointer

    ; Initialize x with 2
    ; IN C: int x = 2;
    mov w0, 2 ; Move 2 into the w0 register
    str w0, [sp, 16] ; Store the contents of w0 (2) at a 16-byte offset from the stack pointer
    ; Essentially, the above line stores 2 on the stack.

    mov w0, 0 ; Move 0 into w0, prepare for return

    ; Clear stack
    ldp x29, x30, [sp], 32 ; Restore frame pointer and link register
    ret ; Return

Notez que la plupart des compilateurs ne stockeraient réellement une variable comme celle que j'ai montrée sur la pile, car elle n'est pas utilisée. Cependant, s'il est utilisé plusieurs fois, il sera stocké sur la pile comme ci-dessus.

Si nous regardions l'emplacement où notre variable a été stockée sur la pile (alors qu'elle est là, bien sûr), nous verrions quelque chose comme :

Memory Address	Value Stored (Hex)	Value Stored (Binary)
0x1000	0x02	00000010
0x1001	0x00	00000000
0x1002	0x00	00000000
0x1003	0x00	00000000

Cela suppose que votre système est petit-boutiste. Je n'entrerai pas dans les détails de l'endianisme ici, mais vous pouvez en savoir plus ici.

La chose clé que j'aimerais que vous remarquiez à propos du tableau ci-dessus est que même si notre entier ne fait que 2 bits, il occupe 4 octets (32 bits) de mémoire. Maintenant, ne paniquez pas, c'est normal et attendu. L'une des nombreuses choses que font C et votre compilateur est de définir des normes pour les types que vous invoquez. Ainsi, lorsque je crée une variable int, le compilateur sait allouer 4 octets (encore une fois, 32 bits) de mémoire. Nous pouvons même tester cela en utilisant l'opérateur sizeof() en C.

L'opérateur sizeof()

sizeof() n'est pas une véritable fonction C. Au lieu de cela, au moment de la compilation, le compilateur remplace l'expression par la taille du type de données donné. Vous pouvez même l'utiliser avec vos propres types, comme les typedefs et/ou les structures :

#include <stdio.h> 

typedef struct {
  char name[64];
  int age;
} Person;

int main(int argc, char** argv) {
  printf("A Person is %lu bytes long.\n", sizeof(Person));
  return 0;
}

Une autre chose que vous vous demandez peut-être est de savoir comment les nombres négatifs sont stockés. Excellente question. Les numéros peuvent être signés ou non signés, mais par défaut, ils sont signés. Si un entier est signé, il sacrifie son bit le plus significatif pour devenir le « bit de signe ». Si le bit de signe est 1, le nombre est négatif ; sinon c'est positif. Un lecteur avisé se rendra peut-être compte que le changement qui se produit ici se situe dans la gamme des nombres possibles. Considérez les nombres de 8 bits. Il y a 256 nombres possibles à représenter (donnés par 2^8). Avec un entier non signé de 8 bits, les valeurs 0 à 255 peuvent être représentées ; avec un entier 8 bits signé, -128-127 peut être représenté.

Pour obtenir l'inverse d'un nombre binaire, utilisez le complément de deux. Trouvons -5 en binaire.

1. Commencez par 5. En binaire, 5 vaut 0101. Le 0 en tête est le signe.
2. Inversez chaque bit. 0101 → 1010.
3. Ajoutez 1 à ce numéro (en ignorant tout éventuel débordement). 1010 + 0001 = 1011.

À votre tour !

1. Confirmez que -5 est 1011 en binaire en effectuant un compliment de deux dessus pour obtenir 5, ou 0101.
2. Écrivez un programme C qui imprime la taille d'un entier en octets et en bits. Utilisez le code ci-dessus comme point de départ. Astuce : pour convertir des octets en bits, combien de bits y a-t-il dans un octet ?
3. Remplissez le tableau suivant avec des tailles de différents types, en modifiant votre programme pour les vérifier.

Type	Size (bytes)	Size (bits)
int
int64_t
int8_t
char
bool (you'll need to #include 7c6dd6636e138b73de36040ce8dc60d1)
long int
short int
long long int
double
double

Sample Responses

Question 1

1. Start with -5: 1011.
2. Invert each bit: 1011 → 0100.
3. Add 1: 0100 + 0001 = 0101

Question 2

Here's an example of what your simple program might look like (you can also check it out at Chapter 1/SizeOfOperatorTest.c).

 #include ade979de5fc0e1ca0540f360a64c230b

 int main(int argc, char** argv) {
    printf("The size of an int is %lu bytes, or %lu bits.\n", sizeof(int), sizeof(int) * 8);
    return 0;
 }

Go ahead and compile it using gcc and check out its output:

cd Chapter\ 1
gcc -o sizeof SizeOfOperatorTest.c
./sizeof

Question 3

Type	Size (bytes)	Size (bits)
int	4	32
int64_t	8	64
int8_t	1	8
char	1	8
bool (you'll need to #include 7c6dd6636e138b73de36040ce8dc60d1)	1	8
long int	4	32
short int	2	16
long long int	8	64
double	4	32
double	8	64

Take This Home

The main point I'd like you to keep in mind is that with control of every bit, we can optimize our memory usage. Though that has little effect on modern systems, in the case of embedded computing, every byte counts. By manually reading and writing bits as opposed to typical variable values, we can harness more functionality from less storage.

Chapter 2: Operating on Bits

Now that we've covered data types and how data is stored, we're ready to introduce the idea of bitwise operations. Put simply, a bitwise operation is an operation done on each bit of a piece of data. Let's take a look at each bitwise operator. Then, we'll implement them in C.

And (&)

Written x & y in C. This operator takes the corresponding bits of each number and performs an and operation. An and operation returns 1 (true) if and only if both bits are 1. This means that two bits that are both 0 do not return 1—they return 0. The result is the number made up of the binary string of results from each and. It's easiest to see this in a truth table.

Consider the operation int result = 3 & 5. First, convert 3 and 5 to binary.
Now, we have int result = 011 & 101. Consider the following truth table:

Bit A	Bit B	AND
0	1	0
1	0	0
1	1	1

The result of the and operation is 001, which when converted to decimal is 1.

Or (|)

Written x | y in C. This operator takes the corresponding bits of each number and performs an or operation. An or operation returns 1 if either bit is 1. As with other bitwise operators, the result is the number made up of the binary string of results from each or.

Consider the operation int result = 3 | 5. First, convert 3 and 5 to binary.
Now, we have int result = 011 | 101. Consider the following truth table:

Bit A	Bit B	OR
0	1	1
1	0	1
1	1	1

The result of the or operation is 111, which when converted to decimal is 7.

Xor (^)

Written x ^ y in C. This operator takes the corresponding bits of each number and performs an xor (exclusive or) operation. An xor operation returns 1 if and only if one of the two bits is 1. As with other bitwise operators, the result is the number made up of the binary string of results from each or.

Consider the operation int result = 3 ^ 5. First, convert 3 and 5 to binary.
Now, we have int result = 011 ^ 101. Consider the following truth table:

Bit A	Bit B	XOR
0	1	1
1	0	1
1	1	0

Le résultat de l'opération xor est 110, qui une fois converti en décimal est 6.

Maj gauche (d617a755e6475e1ffa3980f05444189d>)

Écrit x>> montant Cet opérateur est identique au décalage gauche, sauf qu'il fonctionne dans la direction opposée. Chaque bit du nombre donné est décalé vers la droite du montant donné. Tous les bits qui atteignent la fin du nombre sont tronqués (et des zéros apparaissent sur le côté gauche). Passons en revue un exemple.

Considérez le résultat int = 3 >> 2. Comme vous le savez, 3 vaut 011 en binaire. Passons en revue chaque itération du changement.

Initiale

0	1	1

Après un quart de travail

0	0	1

Résultat

0	0	0

Le résultat binaire est 000, soit 0 en décimal.

Non (~)

Écrit ~x. L'opérateur not inverse tous les bits du nombre donné. Encore une fois, nous utiliserons une table de vérité pour élaborer.

Considérez le résultat int = ~5. Comme vous le savez, 5 vaut 101 en binaire.

Bit A	~ Bit A
1	0
0	1
1	0

Par conséquent, le résultat de l'opération not est 010, soit 2 en binaire.

Restrictions de décalage vers la gauche et de droite

Il existe quelques restrictions notables sur ces opérations de quarts de travail. Pour commencer, vous ne pouvez pas décaler les bits un nombre de fois négatif : cela n'a tout simplement pas de sens ! De plus, un décalage supérieur au nombre de bits alloués à votre variable est considéré comme indéfini. Vous pouvez le faire, mais sa sortie n'est pas garantie d'être constante pour une valeur donnée. Enfin, bien qu'il ne s'agisse pas d'une restriction en soi, le décalage de 0 fois n'effectue tout simplement pas de décalage.

À votre tour !

1. Complétez une table de vérité pour chacun des éléments suivants. Considérez que toutes les valeurs ne sont pas signées. Convertir en décimal une fois terminé.
2. 8&2
3. 6 | 3
4. 7^5
5. (5&2) & (4&3)
6. (5 | 2) & (4 & 3)

7. (5&2) ^ (4 | 3)

8. Terminez chaque opération. Considérez que toutes les valeurs ne sont pas signées et aussi longtemps que la valeur la plus longue du problème doit l'être (c'est-à-dire que si vous avez la plus grande valeur de 8, traitez 4 bits). Convertir en décimal une fois terminé.

9. ~6

10. 9 1696365de20db2e5e4648a1b9113c55d> 1

11. 8>> (~2)

12. ~((3 >> 2) ^ ~7) & (~(7 >> 4) | 2)

Exemples de réponses

Question 1

• 8 & 2 → 1000 & 0010

Bit A	Bit B	AND
1	0	0
0	0	0
0	1	0
0	0	0

⇒ 0000, qui est 0 en décimal.

• 6 | 3 → 110 | 011

Bit A	Bit B	OR
1	0	1
1	1	1
0	1	1

⇒ 111, soit 7 en décimal.

• 7 ^ 5 → 111 ^ 101

Bit A	Bit B	XOR
1	1	0
1	0	1
1	1	0

⇒ 010, qui est 2 en décimal.

• (5 & 2) & (4 & 3) → (101 & 010) & (100 & 011)

Bit A	Bit B	A AND B	Bit C	Bit D	C AND D	(A AND B) AND (C AND D)
1	0	0	1	0	0	0
0	1	0	0	1	0	0
1	0	0	0	1	0	0

⇒ 000, qui est 0 en décimal.

• (5 | 2) & (4 & 3) → (101 | 010) & (100 & 011)

Bit A	Bit B	A OR B	Bit C	Bit D	C AND D	(A OR B) AND (C AND D)
1	0	1	1	0	0	0
0	1	1	0	1	0	0
1	0	1	0	1	0	0

⇒ 000, qui est 0 en décimal.

• (5 & 2) ^ (4 | 3) → (101 & 010) ^ (100 | 011)

Bit A	Bit B	A AND B	Bit C	Bit D	C OR D	(A AND B) XOR (C OR D)
1	0	0	1	0	1	1
0	1	0	0	1	1	1
1	0	0	0	1	1	1

⇒ 111, which is 7 in decimal.

Question 2

• ~6 → ~110 ⇒ 011, which is 3 in decimal.

• 9 882c1bd3602a338c72ccc257e908feba> 1 → (010 | 110) >> 1 → 110 >> 1 ⇒ 011, which is 3 in decimal.

• 8 >> (~2) → 1000 >> ~(10) → 1000 >> (01) → 1000 >> 1 ⇒ 0100, which is 4 in decimal.

• ~((3 >> 2) ^ ~7) & (~(7 >> 4) | 2)

To solve this, I suggest splitting into halves:

~((3 >> 2) ^ ~7) and (~(7 >> 4) | 2)

~((3 >> 2) ^ ~7) → ~((011 >> 2) ^ ~(111)) → ~((000) ^ ~(111)) → ~(000 ^ 000) → 111
(~(7 >> 4) | 2) → (~(111 >> 4) | 010) → (~(000) | 010) → (111 | 010) → 111

Hence, 111 & 111 ⇒ 111, which is 7 in decimal.

Chapter 3: Applying Bitwise Operations in C

This chapter is all about writing C code that utilizes bitwise operators. Before we get to doing bitwise operations, we should begin by writing a function that can write the binary equivalent of a given variable.

To do this, we use a mask. We initialize it to contain a 1 in the most significant (leftmost in little-endian systems) bit followed by zeros. With each iteration of a loop, we right shift the mask by 1, moving the 1 all the way "across" the mask. When we use the & operator on the pointer and the mask, any non-zero value means that a 1 occurred somewhere in the result. Since there's only one 1 in the mask, we know exactly where this occurred. Since the loop moves from left to right, we can just append the corresponding bit's character to the string. The string is one character longer than the size because it needs to contain the null character (\0). This is how printf knows to stop printing, and omitting it can lead to numerous errors and/or unexpected behaviors (like the printing of other data from in memory).

void printBinary(unsigned int decimal) {

    // To determine size (in bits), we multiply the maximum size of an unsigned int by 8 (to convert from bytes to bits).
    int size = sizeof(decimal) * 8;

    // This counts the leading zeros of the number, then subtracts them from the size.
    // Hence, we start at the first bit set to 1 (unless decimal == 0)
    size -= __builtin_clz(decimal);

    if(size == 0) size = 1; // Handle zero case, we need one space to display "0."

    int curr = 0;
    char binary[size + 1];
    for(unsigned int mask = 1 e360cd6bcd3c1b37977442911f0d6d09>= 1) {
        if((decimal & mask) != 0) {
            binary[curr] = '1';
        } else {
            binary[curr] = '0';
        }
        curr++;
    }

    binary[curr] = '\0';

    printf("%s", binary);

}

Bitwise Assignment Operators

All bitwise operators, except for not (~), can be used in the assignment fashion. This means you can add an equals sign right next to one of the bitwise operator. For example, in

int a = 2;
a &= 7;

a is both the first operand and the destination. In other words, the value of a & 7 is stored in a. This works for all bitwise operators aside from the not (~) operator.

Now, I'd like to provide a few case study like prompts for you to try. Sample responses are available.

Case Study 1: Unix File Permissions

One use case of bitwise operations is in the Unix permission system. You've probably run the command

chmod 777 some-file

But what do each of the numbers mean? And why 7? The reality is, binary is at play here, and 7 should tip you off. Recall that 7 in binary is 111. The number being passed here is acting as three flags or booleans glued together.

The three digits specified are for three classes of users:

• The file owner;
• Group members of the file owner;
• and everyone else.

As I mentioned above, each digit is a conglomeration of three flags, each representing a permission. The flag (binary bit) in the fours place represents read permission, the twos place is for write permission, and the ones is for execute. So,

chmod 777 some-file

is doing this under the hood:

File Permissions: some-file

Group	Read	Write	Execute	Decimal
Owner	1	1	1	7
Owner's Group	1	1	1	7
Everyone Else	1	1	1	7

En d’autres termes, toutes les autorisations sont données à tous.

Tâche

Concevez un vérificateur d'autorisations simple qui prend en compte une valeur d'autorisation de fichier complète (un nombre à trois chiffres) et vérifie un ensemble donné d'autorisations spécifiques (c'est-à-dire l'écriture du propriétaire, tout le monde exécute, etc.). Pour un exemple, consultez le dossier Chapitre 3.

Indice

Après avoir saisi un nombre complet, vous devrez le convertir en int (à partir d'un char*). Ensuite, utilisez l’arithmétique modulaire pour décomposer chaque ensemble d’autorisations. N'oubliez pas que le premier chiffre représente les autorisations du propriétaire, le deuxième est destiné au groupe d'utilisateurs du propriétaire et le troisième est destiné à tout le monde.

Pour vérifier si une autorisation spécifique se produit dans un ensemble d'autorisations, au niveau du bit et de l'autorisation donnée avec l'ensemble.

Cas 2 : création de sous-réseaux d'un réseau

Si vous avez déjà configuré un routeur, vous avez peut-être remarqué une option permettant de configurer le « masque de sous-réseau ». Habituellement, la valeur est 255.255.255.0, mais pourquoi ? Tout d'abord, nous devons nous rappeler que chaque octet d'une adresse IPv4 est séparé par un « . ». Lorsqu'il s'agit du type de réseau que vous connaissez le mieux (un réseau de classe C), il y a 3 octets dédiés au réseau et le dernier octet est destiné à l'hôte.

Étant donné que le masque de sous-réseau est un masque, vous comprenez peut-être son objectif. Pour chaque bit que vous « empruntez » à l'octet hôte, deux sous-réseaux sont créés.

Adresse réseau

L'adresse réseau a tous les bits hôte définis sur 0. Cela signifie que tout bit cédé pour créer
un sous-réseau pourrait toujours être défini sur 1.

En savoir plus!

Apprenez-en davantage sur les sous-réseaux en consultant ce site Web.

Tâche

En C, écrivez un programme qui prend une adresse IPv4 et un masque de sous-réseau et trouve et génère l'adresse réseau dans laquelle réside l'adresse IPv4. Pour un exemple, consultez le dossier du chapitre 3.

Indice

Vous devrez stocker chaque octet de l'adresse et du masque sous forme de valeur numérique. Pour trouver l'adresse réseau, déterminez quelle opération (au niveau du bit) entre le masque et l'adresse créera l'effet escompté.

Clôture

J'espère que cette explication vous a été utile ! Je l'ai écrit parce que je voulais moi-même en apprendre davantage sur les opérations au niveau des bits. Je l'ai vérifié, mais certaines choses pourraient ne pas fonctionner, alors n'hésitez pas à me corriger via une pull request, ou même à ajouter un commentaire ! Et si vous avez des questions, laissez un commentaire ! J'ai hâte de discuter avec vous ! Pour conclure, je suis tellement heureuse d'avoir pu vous fournir cette ressource !

Sur moi

Salut ! Je m'appelle Jackson, étudiant en informatique et français au Lafayette College et aspirant chercheur et professeur en informatique. Je m'intéresse actuellement aux domaines de la bioinformatique et de la programmation/systèmes bas niveau. Pour en savoir plus sur moi, consultez mon site.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!