Ein Überblick über bitweise Operationen

Der folgende Beitrag stammt aus einem Repository, das ich erstellt habe, um das Erlernen (und Lehren) von bitweisen Operationen zu erleichtern. Sie können dieses Repo hier finden, und ich würde vorschlagen, es sich anzusehen – es gibt dort einige Codebeispiele und Lösungen.

Einführung

Das Ziel dieses Repositorys besteht darin, Sie mit bitweisen Operationen vertraut zu machen und zu erklären, was sie sind, wie sie funktionieren und wofür sie verwendet werden können.

Kapitel 1: Es ist alles binär

In C (und den meisten Hochsprachen) haben unsere Variablen Typen. Diese Typen weisen auf einige Dinge hin. Natürlich speichert eine Variable vom Typ int einen ganzzahligen Wert, aber der Schlüssel zum Verständnis dieser bitweisen Operationen besteht darin, zu wissen, dass unter der Haube alle Typen im Speicher (irgendwo, im Stapel, im Heap, wo auch immer) als Binärwerte gespeichert sind. Hier ist ein Beispiel dafür, was passiert, wenn Sie einen einfachen ganzzahligen Wert auf dem Stapel in C:
speichern

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

Nach dem Kompilieren zur Assembly könnte der Code so aussehen (ich verwende hier die ARM-Assembly und habe den Code mit Kommentaren versehen):

.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

Beachten Sie, dass die meisten Compiler eine Variable wie die, die ich gezeigt habe, nicht tatsächlich auf dem Stapel speichern würden, da sie unbenutzt ist. Wenn es jedoch mehrmals verwendet wird, wird es etwa wie oben auf dem Stapel gespeichert.

Wenn wir uns den Ort ansehen würden, an dem unsere Variable auf dem Stapel gespeichert ist (natürlich solange sie dort ist), würden wir etwas sehen wie:

Dies setzt voraus, dass Ihr System Little-Endian ist. Ich werde hier nicht auf Endianness eingehen, aber Sie können hier mehr darüber lesen.

Das Wichtigste an der obigen Tabelle ist, dass unsere Ganzzahl, obwohl sie nur 2 Bit lang ist, 4 Byte (32 Bit) Speicher beansprucht. Machen Sie sich keine Sorgen – das ist normal und wird erwartet. Eines der vielen Dinge, die C und Ihr Compiler tun, ist das Festlegen von Standards für die von Ihnen aufgerufenen Typen. Wenn ich also eine int-Variable erstelle, weiß der Compiler, dass er 4 Bytes (wiederum 32 Bits) Speicher zuweisen muss. Wir können dies sogar mit dem sizeof()-Operator in C testen.

Der sizeof()-Operator

sizeof() ist keine echte C-Funktion. Stattdessen ersetzt der Compiler zur Kompilierungszeit den Ausdruck durch die Größe des angegebenen Datentyps. Sie können dies sogar mit Ihren eigenen Typen verwenden, z. B. Typedefs und/oder Strukturen:

#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;
}

Nach dem Login kopieren

Eine andere Frage, die Sie vielleicht fragen, ist, wie negative Zahlen gespeichert werden. Ausgezeichnete Frage. Zahlen können signiert oder unsigniert sein, standardmäßig sind sie jedoch signiert. Wenn eine ganze Zahl ein Vorzeichen hat, opfert sie ihr höchstwertiges Bit als „Vorzeichenbit“. Wenn das Vorzeichenbit 1 ist, ist die Zahl negativ; ansonsten ist es positiv. Ein aufmerksamer Leser könnte erkennen, dass die Änderung, die hier stattfindet, im Bereich möglicher Zahlen liegt. Betrachten Sie 8-Bit-Zahlen. Es gibt 256 mögliche Zahlen zur Darstellung (gegeben durch 2^8). Mit einer vorzeichenlosen 8-Bit-Ganzzahl können die Werte 0–255 dargestellt werden; Mit einem vorzeichenbehafteten 8-Bit-Int können -128–127 dargestellt werden.

Um die Umkehrung einer Binärzahl zu erhalten, verwenden Sie das Zweierkomplement. Finden wir -5 im Binärformat.

1. Beginnen Sie mit 5. Binär ist 5 0101. Die führende 0 ist das Vorzeichen.
2. Jedes Bit invertieren. 0101 → 1010.
3. Fügen Sie 1 zu dieser Zahl hinzu (ignorieren Sie einen möglichen Überlauf). 1010 + 0001 = 1011.

Du bist dran!

1. Bestätigen Sie, dass -5 binär 1011 ist, indem Sie ein Zweierkomplement darauf anwenden, um 5 oder 0101 zu erhalten.
2. Schreiben Sie ein C-Programm, das die Größe eines Ints sowohl in Bytes als auch in Bits ausgibt. Verwenden Sie den obigen Code als Ausgangspunkt. Hinweis: Um von Bytes in Bits umzuwandeln, wie viele Bits enthält ein Byte?
3. Füllen Sie die folgende Tabelle mit Größen verschiedener Typen aus und modifizieren Sie Ihr Programm, um sie zu überprüfen.

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 <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

Question 3

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:

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:

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:

Das Ergebnis der XOR-Operation ist 110, was bei der Konvertierung in eine Dezimalzahl 6 ist.

Linksverschiebung (<<)

Geschrieben x << Betrag Im Gegensatz zu den oben genannten Operatoren arbeitet dieser Operator nur mit einer Zahl. Jedes Bit in der angegebenen Zahl wird um den angegebenen Betrag nach links verschoben. Alle Bits, die das Ende der Zahl erreichen, werden abgeschnitten (und auf der rechten Seite erscheinen Nullen). Lassen Sie uns ein Beispiel durchgehen.

Betrachten Sie int result = 5 << 2. Wie Sie wissen, ist 5 binär 101. Lassen Sie uns jede Iteration der Schicht durchgehen.

Anfänglich

Nach einer Schicht

Ergebnis

Das binäre Ergebnis ist 100, also 4 in Dezimalzahl.

Rechtsverschiebung (>>)

Geschrieben x >> Betrag Dieser Operator ähnelt der Linksverschiebung, funktioniert jedoch in die entgegengesetzte Richtung. Jedes Bit in der angegebenen Zahl wird um den angegebenen Betrag nach rechts verschoben. Alle Bits, die das Ende der Zahl erreichen, werden abgeschnitten (und auf der linken Seite erscheinen Nullen). Lassen Sie uns ein Beispiel durchgehen.

Consider int result = 3 >> 2. Wie Sie wissen, ist 3 binär 011. Lassen Sie uns jede Iteration der Schicht durchgehen.

Anfänglich

Nach einer Schicht

Ergebnis

Das binäre Ergebnis ist 000, was 0 in Dezimalzahl ist.

Nicht (~)

Geschrieben ~x. Der Not-Operator invertiert alle Bits der angegebenen Zahl. Zur Erläuterung verwenden wir noch einmal eine Wahrheitstabelle.

Betrachten Sie int result = ~5. Wie Sie wissen, ist 5 binär 101.

Daher ist das Ergebnis der Nicht-Operation 010, was binär 2 ist.

Einschränkungen für die Links- und Rechtsverschiebung

Für diesen Schichtbetrieb gelten einige nennenswerte Einschränkungen. Zunächst einmal können Sie Bits nicht um eine negative Anzahl verschieben – das macht einfach keinen Sinn! Außerdem gilt das Verschieben um mehr als die Anzahl der Ihrer Variablen zugewiesenen Bits als undefiniert. Sie können zwar, es ist jedoch nicht garantiert, dass die Ausgabe für einen bestimmten Wert konstant ist. Obwohl es sich hierbei nicht um eine Einschränkung per se handelt, führt eine Verschiebung um 0 einfach nicht zu einer Verschiebung.

Du bist dran!

1. Vervollständigen Sie für jede der folgenden Aussagen eine Wahrheitstabelle. Betrachten Sie alle Werte als vorzeichenlos. Nach Abschluss in eine Dezimalzahl umwandeln.
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. Schließen Sie jeden Vorgang ab. Betrachten Sie alle Werte als vorzeichenlos und solange der längste Wert im Problem erforderlich ist (d. h. wenn Sie den größten Wert von 8 haben, müssen Sie sich mit 4 Bits befassen). Nach Abschluss in eine Dezimalzahl umwandeln.

9. ~6

10. 9 << 4 (hier gehen wir davon aus, dass der Wert eine Länge von 32 hat, sodass Platz für eine Linksverschiebung vorhanden ist).

11. ~(7 & 8)

12. (2 | 6) >> 1

13. 8 >> (~2)

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

Beispielantworten

Frage 1

• 8 & 2 → 1000 & 0010

⇒ 0000, was 0 in Dezimalzahl ist.

• 6 | 3 → 110 | 011

⇒ 111, was 7 in Dezimalzahl ist.

• 7 ^ 5 → 111 ^ 101

⇒ 010, was 2 in Dezimalzahl ist.

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

⇒ 000, was 0 in Dezimalzahl ist.

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

⇒ 000, was 0 in Dezimalzahl ist.

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

⇒ 111, which is 7 in decimal.

Question 2

• ~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.

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 << (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;

Nach dem Login kopieren

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

Mit anderen Worten, alle Berechtigungen werden allen erteilt.

Aufgabe

Entwerfen Sie einen einfachen Berechtigungsprüfer, der einen vollständigen Dateiberechtigungswert (eine dreistellige Zahl) aufnimmt und nach einem bestimmten Satz spezifischer Berechtigungen sucht (z. B. Schreiben durch den Eigentümer, Ausführen durch alle usw.). Ein Beispiel finden Sie im Ordner „Kapitel 3“.

Hinweis

Nachdem Sie eine vollständige Zahl eingegeben haben, müssen Sie diese in ein int (von einem char*) umwandeln. Verwenden Sie dann modulare Arithmetik, um jeden Berechtigungssatz aufzuschlüsseln. Denken Sie daran, dass die erste Ziffer die Berechtigungen des Eigentümers darstellt, die zweite für die Benutzergruppe des Eigentümers und die dritte für alle.

Um zu überprüfen, ob eine bestimmte Berechtigung in einem Berechtigungssatz vorkommt, bitweise und die gegebene Berechtigung mit dem Satz.

Fall 2: Subnetting eines Netzwerks

Wenn Sie jemals einen Router konfiguriert haben, ist Ihnen möglicherweise eine Option zum Konfigurieren der „Subnetzmaske“ aufgefallen. Normalerweise ist dies auf 255.255.255.0 eingestellt, aber warum? Zunächst müssen wir bedenken, dass jedes Byte einer IPv4-Adresse durch ein „.“ getrennt ist. Wenn Sie es mit dem Netzwerktyp zu tun haben, mit dem Sie am besten vertraut sind (ein Netzwerk der Klasse C), sind 3 Bytes für das Netzwerk reserviert und das letzte Byte ist für den Host.

Da es sich bei der Subnetzmaske um eine Maske handelt, verstehen Sie vielleicht schon, welchen Zweck sie hat. Für jedes Bit, das Sie vom Host-Byte „ausleihen“, werden zwei Subnetze erstellt.

Netzwerkadresse

Bei der Netzwerkadresse sind alle Host-Bits auf 0 gesetzt. Dies bedeutet, dass jedes Bit zum Erstellen übergeben wird
Ein Subnetz könnte immer noch auf 1 gesetzt werden.

Mehr lesen!

Erfahren Sie mehr über Subnetze auf dieser Website.

Aufgabe

Schreiben Sie in C ein Programm, das eine IPv4-Adresse und eine Subnetzmaske aufnimmt und die Netzwerkadresse findet und ausgibt, in der sich die IPv4-Adresse befindet. Ein Beispiel finden Sie im Ordner Kapitel 3.

Hinweis

Sie müssen jedes Byte der Adresse und Maske als numerischen Wert speichern. Um die Netzwerkadresse zu finden, überlegen Sie, welche (bitweise) Operation zwischen Maske und Adresse den beabsichtigten Effekt erzeugt.

Schließen

Ich hoffe, diese Erklärung war hilfreich für Sie! Ich habe es geschrieben, weil ich selbst etwas über bitweise Operationen lernen wollte. Ich habe es überprüft, aber einige Dinge könnten falsch sein. Korrigieren Sie mich also gerne über eine Pull-Anfrage oder fügen Sie sogar einen Kommentar hinzu! Wenn Sie Fragen haben, hinterlassen Sie außerdem einen Kommentar! Ich kann es kaum erwarten, mit Ihnen zu chatten! Abschließend möchte ich sagen, dass ich sehr froh bin, Ihnen diese Ressource zur Verfügung stellen zu können!

Über mich

Hallo! Ich bin Jackson, Student der Informatik und Französisch am Lafayette College und ein aufstrebender Forscher und Professor für Informatik. Ich interessiere mich derzeit für die Bereiche Bioinformatik und Low-Level-Programmierung/Systeme. Um mehr über mich zu erfahren, schauen Sie sich meine Website an.

Das obige ist der detaillierte Inhalt vonEin Überblick über bitweise Operationen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!