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.
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.
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; }Copier après la connexion
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.
| Type | Size (bytes) | Size (bits) |
|---|---|---|
| int | ||
| int64_t | ||
| int8_t | ||
| char | ||
| bool (you'll need to #include |
||
| long int | ||
| short int | ||
| long long int | ||
| double | ||
| double |
Here's an example of what your simple program might look like (you can also check it out at Chapter 1/SizeOfOperatorTest.c).
#include <stdio.h>
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
| 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 |
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.
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.
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.
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.
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.
Écrit x << montant Contrairement aux opérateurs ci-dessus, cet opérateur n'opère que sur un seul numéro. Chaque bit du nombre donné est décalé vers la gauche du montant donné. Tous les bits qui atteignent la fin du nombre sont tronqués (et des zéros apparaissent sur le côté droit). Passons en revue un exemple.
Considérez le résultat int = 5 << 2. Comme vous le savez, 5 vaut 101 en binaire. Passons en revue chaque itération du changement.
Initiale
| 1 | 0 | 1 |
|---|
Après un quart de travail
| 0 | 1 | 0 |
|---|
Résultat
| 1 | 0 | 0 |
|---|
Le résultat binaire est 100, soit 4 en décimal.
É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.
É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.
(5&2) ^ (4 | 3)
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é.
~6
9 << 4 (considérez ici que la valeur est de longueur 32, il y a donc de la place pour un décalage vers la gauche).
~(7&8)
(2 | 6)>> 1
8>> (~2)
~((3 >> 2) ^ ~7) & (~(7 >> 4) | 2)
| Bit A | Bit B | AND |
|---|---|---|
| 1 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
⇒ 0000, qui est 0 en décimal.
| Bit A | Bit B | OR |
|---|---|---|
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| 0 | 1 | 1 |
⇒ 111, soit 7 en décimal.
| Bit A | Bit B | XOR |
|---|---|---|
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
⇒ 010, qui est 2 en décimal.
| 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.
| 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.
| 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.
~6 → ~110 ⇒ 011, which is 3 in decimal.
9 << 4 → 001001 << 4 ⇒ 100100, which is 36 in decimal.
~(7 & 8) → ~(0111 & 1000) → ~(0000) ⇒ 1111, which is 15 in decimal.
(2 | 6) >> 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.
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 << (size - 1); mask != 0; mask >>= 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;Copier après la connexiona 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.
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:
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:
| 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.
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.
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.
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.
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.
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é.
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 !
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!
Que dois-je faire si le navigateur IE affiche une erreur de script ?
Quels sont les types de trafic ?
mise à jour automatique de Windows
Que diriez-vous de l'échange MEX
Que dois-je faire si eDonkey Search ne parvient pas à se connecter au serveur ?
Comment configurer la fonction antiblocage de WeChat
sublime exécute le code js
Trois méthodes de virtualisation GPU
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
