Verwendung der bitweisen Operatoren, um mehrere Werte in einen int zu packen

Question

Low-Level-Bit-Manipulation war noch nie meine Stärke. Ich werde einige Hilfe beim Verständnis der folgenden Anwendungsfall der bitweisen Operatoren zu schätzen wissen...

int age, gender, height, packed_info;

. . .   // Assign values 

// Pack as AAAAAAA G HHHHHHH using shifts and "or"
packed_info = (age << 8) | (gender << 7) | height;

// Unpack with shifts and masking using "and"
height = packed_info & 0x7F;   // This constant is binary ...01111111
gender = (packed_info >> 7) & 1;
age    = (packed_info >> 8);

Ich bin mir nicht sicher, was dieser Code bewirkt und wie er funktioniert. Warum wird die magische Zahl 0x7F verwendet? Wie wird das Packen und Entpacken bewerkstelligt?

Quelle

Answer 1

Wie der Kommentar besagt, werden wir das Alter, das Geschlecht und die Größe in 15 Bits des Formats packen:

AAAAAAAGHHHHHHH

Beginnen wir mit diesem Teil:

(age << 8)

Zunächst einmal hat das Alter dieses Format:

age           = 00000000AAAAAAA

wobei jedes A 0 oder 1 sein kann.

<< 8 verschiebt die Bits um 8 Stellen nach links und füllt die Lücken mit Nullen auf. Man erhält also:

(age << 8)    = AAAAAAA00000000

Ähnlich:

gender        = 00000000000000G
(gender << 7) = 0000000G0000000
height        = 00000000HHHHHHH

Nun wollen wir diese in einer Variablen zusammenfassen. Die | Operator arbeitet, indem er jedes Bit betrachtet und 1 zurückgibt, wenn das Bit in einem der Eingänge 1 ist. Also:

0011 | 0101 = 0111

Wenn ein Bit an einem Eingang 0 ist, erhält man das Bit vom anderen Eingang. Betrachten (age << 8) , (gender << 7) y height Sie werden sehen, dass ein Bit, das bei einem von ihnen den Wert 1 hat, bei den anderen den Wert 0 hat. Also:

packed_info = (age << 8) | (gender << 7) | height = AAAAAAAGHHHHHHH

Jetzt wollen wir die Bits auspacken. Beginnen wir mit der Höhe. Wir wollen die letzten 7 Bits erhalten und die ersten 8 ignorieren. Dazu verwenden wir die & Operator, der nur dann 1 zurückgibt, wenn beide Eingangsbits 1 sind. Also:

0011 & 0101 = 0001

Also:

packed_info          = AAAAAAAGHHHHHHH
0x7F                 = 000000001111111
(packed_info & 0x7F) = 00000000HHHHHHH = height

Um das Alter zu erhalten, können wir einfach alles um 8 Stellen nach rechts schieben, und es bleibt Folgendes übrig 0000000AAAAAAAA . Also age = (packed_info >> 8) .

Um schließlich das Geschlecht zu erhalten, schieben wir alles um 7 Stellen nach rechts, um die Höhe loszuwerden. Wir interessieren uns dann nur noch für das letzte Bit:

packed_info            = AAAAAAAGHHHHHHH
(packed_info >> 7)     = 0000000AAAAAAAG
1                      = 000000000000001
(packed_info >> 7) & 1 = 00000000000000G

Answer 2

Dies könnte eine ziemlich lange Lektion in Bitmanipulation sein, aber zunächst möchte ich Sie auf die Bitmaskierung Artikel auf Wikipedia .

packed_info = (age << 8) | (gender << 7) | height;

Nehmen Sie das Alter und verschieben Sie den Wert über 8 Bits, dann nehmen Sie das Geschlecht und verschieben Sie es über 7 Bits, und die Höhe nimmt die letzten Bits ein.

age    = 0b101
gender = 0b1
height = 0b1100
packed_info = 0b10100000000
            | 0b00010000000
            | 0b00000001100
/* which is */
packed_info = 0b10110001100

Das Entpacken erfolgt in umgekehrter Weise, wobei jedoch Masken wie 0x7F (0b 01111111) verwendet werden, um die anderen Werte in dem Feld zu entfernen.

gender = (packed_info >> 7) & 1;

Würde funktionieren wie...

gender = 0b1011 /* shifted 7 here but still has age on the other side */
       & 0b0001
/* which is */
gender = 0b1

Beachten Sie, dass eine UND-Verknüpfung mit 1 gleichbedeutend mit dem "Beibehalten" dieses Bits ist und eine UND-Verknüpfung mit 0 gleichbedeutend mit dem "Ignorieren" dieses Bits ist.

Answer 3

Wenn Sie ein Datum als Zahl speichern wollten, würden Sie vielleicht das Jahr mit 10000 multiplizieren, den Monat mit 100 und den Tag hinzufügen. Ein Datum wie der 2. Juli 2011 würde als die Zahl 20110702 kodiert werden:

    year * 10000 + month * 100 + day -> yyyymmdd
    2011 * 10000 + 7 * 100 + 2 -> 20110702

Wir können sagen, dass wir das Datum in einer jjjjmmtt Maske. Wir könnten diesen Vorgang wie folgt beschreiben

• Verschieben Sie das Jahr um 4 Positionen nach links,
• den Monat um 2 Positionen nach links zu verschieben und
• den Tag so lassen, wie er ist.
• Kombinieren Sie dann die drei Werte miteinander.

Das ist dasselbe wie bei der Kodierung von Alter, Geschlecht und Größe, nur dass der Autor in binären Kategorien denkt.

Siehe die Bereiche, die diese Werte haben können:

    age: 0 to 127 years
    gender: M or F
    height: 0 to 127 inches

Wenn wir diese Werte in binäre Werte umwandeln, ergibt sich folgendes Bild:

    age: 0 to 1111111b (7 binary digits, or bits)
    gender: 0 or 1 (1 bit)
    height: 0 to 1111111b (7 bits also)

In diesem Sinne können wir die Alter-Geschlecht-Größe-Daten mit der Maske kodieren aaaaaaaghhhhhhh nur, dass es sich hier um binär Ziffern, nicht dezimal Ziffern.

Also,

• Verschieben Sie das Alter 8 Bits auf der linken Seite,
• das Geschlecht verschieben 7 Bits nach links und
• Lassen Sie die Höhe unverändert.
• Kombinieren Sie dann alle drei Werte miteinander.

Im Binärformat verschiebt der Shift-Links-Operator (<<) einen Wert n Positionen nach links. Der "Oder"-Operator ("|" in vielen Sprachen) verbindet Werte miteinander. Daher:

    (age << 8) | (gender << 7) | height

Wie können diese Werte nun "entschlüsselt" werden?

Im Binärformat ist es einfacher als im Dezimalformat:

• Sie "verdecken" die Höhe,
• die geschlechtsspezifischen 7 Bits nach rechts verschieben und auch diese maskieren und schließlich
• verschiebt das Alter 8 Bits nach rechts.

Der Shift-Right-Operator (>>) verschiebt einen Wert um n Positionen nach rechts (alle Ziffern, die aus der äußersten rechten Position "herausgeschoben" wurden, gehen verloren). Der Binäroperator "Und" ("&" in vielen Sprachen) maskiert Bits. Dazu benötigt er eine Maske, die angibt, welche Bits erhalten und welche vernichtet werden sollen (1 Bit bleibt erhalten). Daher:

    height = value & 1111111b (preserve the 7 rightmost bits)
    gender = (value >> 1) & 1 (preserve just one bit)
    age = (value >> 8)

Da 1111111b in Hexadezimalzeichen in den meisten Sprachen 0x7f ist, ist das der Grund für diese magische Zahl. Sie würden den gleichen Effekt erzielen, wenn Sie 127 verwenden (was 1111111b in Dezimalzahlen entspricht).

Answer 4

Dieselbe Anforderung habe ich schon oft gestellt. Mit Hilfe des Bitwise AND Operators ist es sehr einfach. Qualifizieren Sie einfach Ihre Werte mit aufsteigenden Potenzen von zwei (2). Um mehrere Werte zu speichern, addieren Sie ihre relative Anzahl (Potenz von 2) und erhalten Sie die SUMME. Diese SUMME fasst Ihre ausgewählten Werte zusammen. WIE?

Führen Sie einfach ein bitweises UND mit jedem Wert durch, und Sie erhalten Null (0) für Werte, die nicht ausgewählt wurden, und Nicht-Null für Werte, die ausgewählt wurden.

Hier ist die Erklärung:

1) Werte ( YES, NO, MAYBE )

2) Zuordnung zur Zweierpotenz(2)

YES   =    2^0    =    1    =    00000001
NO    =    2^1    =    2    = 00000010
MAYBE =    2^2    =    4    = 00000100

3) Ich wähle YES und MAYBE, also SUM:

SUM    =    1    +    4    =    5

SUM    =    00000001    +    00000100    =    00000101 

Dieser Wert speichert sowohl YES als auch MAYBE. WIE?

1    &    5    =    1    ( non zero )

2    &    5    =    0    ( zero )

4    &    5    =    4    ( non zero )

SUM besteht also aus

1    =    2^0    =    YES
4    =    2^2    =    MAYBE.

Ausführlichere Erläuterungen und die Umsetzung finden Sie auf meiner Blog

Answer 5

Eine etwas knappere Antwort:

AAAAAAAA G HHHHHH

Verpacken:

packed = age << 8 | gender << 7 | height

Alternativ können Sie auch nur die Komponenten addieren, d.h. wenn Sie die MySQL SUM Aggregatfunktion verwenden

packed = age << 8 + gender << 7 + height

Auspacken:

age = packed >> 8 // no mask required
gender = packed >> 7 & ((1 << 1) - 1) // applying mask (for gender it is just 1)
height = packed & ((1 << 7) - 1) // applying mask

Ein anderes (längeres) Beispiel:

Angenommen, Sie haben eine IP-Adresse, die Sie verpacken möchten, aber es ist eine fiktive IP-Adresse, z. B. 132.513.151.319. Beachten Sie, dass einige Komponenten größer als 256 sind, was im Gegensatz zu echten IP-Adressen mehr als 8 Bits erfordert.

Zuerst müssen wir herausfinden, welchen Offset wir verwenden müssen, um die maximale Anzahl zu speichern. Nehmen wir an, mit unseren fiktiven IPs kann keine Komponente größer als 999 sein, was bedeutet, dass wir 10 Bits Speicherplatz pro Komponente benötigen (erlaubt Zahlen bis zu 1014).

packed = (comp1 << 0 * 10) | (comp1 << 1 * 10) | (comp1 << 2 * 10) | (comp1 << 3 * 10)

Das gibt dec 342682502276 o bin 100111111001001011110000000010010000100

Packen wir nun den Wert aus

comp1 = (packed >> 0 * 10) & ((1 << 10) - 1) // 132
comp2 = (packed >> 1 * 10) & ((1 << 10) - 1) // 513
comp3 = (packed >> 2 * 10) & ((1 << 10) - 1) // 151
comp4 = (packed >> 3 * 10) & ((1 << 10) - 1) // 319

Wo (1 << 10) - 1 ist eine binäre Maske, mit der wir die Bits auf der linken Seite jenseits der 10 Bits auf der rechten Seite ausblenden, an denen wir interessiert sind.

Gleiches Beispiel mit MySQL-Abfrage

SELECT

(@offset := 10) AS `No of bits required for each component`,
(@packed := (132 << 0 * @offset) | 
            (513 << 1 * @offset) | 
            (151 << 2 * @offset) | 
            (319 << 3 * @offset)) AS `Packed value (132.513.151.319)`,

BIN(@packed) AS `Packed value (bin)`,

(@packed >> 0 * @offset) & ((1 << @offset) - 1) `Component 1`,
(@packed >> 1 * @offset) & ((1 << @offset) - 1) `Component 2`,
(@packed >> 2 * @offset) & ((1 << @offset) - 1) `Component 3`,
(@packed >> 3 * @offset) & ((1 << @offset) - 1) `Component 4`;