🧮 Η Γραμμική Άλγεβρα των Bit Twiddling - Πίνακες, XOR και GF(2)

🧮 Όταν οι Πράξεις με Bits Γίνονται Πίνακες

Οι περισσότεροι προγραμματιστές γνωρίζουν τις πράξεις XOR, AND, shift. Αλλά λίγοι γνωρίζουν ότι αυτές οι πράξεις είναι γραμμικοί μετασχηματισμοί — και μπορούν να περιγραφούν ως πολλαπλασιασμός πινάκων.

Το κλειδί βρίσκεται στο GF(2), το πεπερασμένο σώμα με δύο στοιχεία: 0 και 1.

📌 Το GF(2)

Στο GF(2), η πρόσθεση είναι το XOR (1 ⊕ 1 = 0) και ο πολλαπλασιασμός είναι το AND.

Έτσι, κάθε πράξη με bits γίνεται μια γραμμική πράξη σε ένα διανυσματικό χώρο πάνω από το GF(2).

📐 Οι Μετασχηματισμοί ως Πίνακες

Ας δούμε πώς περιγράφονται οι βασικές πράξεις με bits ως πίνακες (για 8-bit αριθμούς, για ευκολία στην οπτικοποίηση).

Αριστερή ολίσθηση (shift left) κατά 2 θέσεις:

\[ \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} \]

Οι απολεσθείσες θέσεις (οι δύο πρώτες σειρές) γεμίζουν με μηδενικά — γι' αυτό η ολίσθηση δεν είναι αντιστρέψιμη.

Δεξιά ολίσθηση (shift right) κατά 2 θέσεις:

\[ \begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} \]

Και εδώ, οι απολεσθείσες θέσεις γεμίζουν με μηδενικά.

🔄 Η Αντιστρεψιμότητα — Το Κλειδί του Mersenne Twister

Η ολίσθηση δεν είναι αντιστρέψιμη — χάνουμε bits. Αλλά όταν συνδυάζουμε την ολίσθηση με XOR, το αποτέλεσμα μπορεί να είναι αντιστρέψιμο.

Για παράδειγμα, ο μετασχηματισμός \( x \mapsto x \oplus (x \gg 2) \) αντιστοιχεί στον πίνακα:

\[ \begin{pmatrix} 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \]

Αυτός ο πίνακας είναι άνω τριγωνικός, με όλα τα διαγώνια στοιχεία ίσα με 1. Επομένως, η ορίζουσά του είναι 1, και ο μετασχηματισμός είναι αντιστρέψιμος.

Αυτή η ιδιότητα είναι το θεμέλιο του Mersenne Twister — ο γεννήτριας ψευδοτυχαίων αριθμών που βασίζεται σε αντιστρέψιμες πράξεις bits.

🔲 Το Bitwise AND ως Διαγώνιος Πίνακας

Το bitwise AND με μια μάσκα πολλαπλασιάζει κάθε bit του αριθμού με το αντίστοιχο bit της μάσκας. Αυτό αντιστοιχεί σε διαγώνιο πίνακα.

Για παράδειγμα, το AND με τη μάσκα 10100100 (δεκαδικά 164):

\[ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \]

Οι θέσεις όπου η μάσκα έχει 0 μηδενίζονται. Οι θέσεις με 1 παραμένουν.

🚀 Εφαρμογή — Το Tempering του Mersenne Twister

Στον αλγόριθμο Mersenne Twister, η διαδικασία tempering περιλαμβάνει γραμμές όπως:

y ^= (y << 7) & 0x9d2c5680

Αυτό σημαίνει:

1. Ολίσθηση του \( y \) κατά 7 θέσεις αριστερά.
2. AND με τη μάσκα \( 0x9d2c5680 \).
3. XOR με το αρχικό \( y \).

Σε μορφή πινάκων, αυτό αντιστοιχεί σε:

• Πολλαπλασιασμό με έναν κάτω τριγωνικό πίνακα (shift).
• Πολλαπλασιασμό με έναν διαγώνιο πίνακα (AND).
• Πρόσθεση (XOR) με τον ταυτοτικό πίνακα.

Το αποτέλεσμα είναι ένας κάτω τριγωνικός πίνακας με όλα τα διαγώνια στοιχεία 1 — επομένως αντιστρέψιμος.

Αυτή η αντιστρεψιμότητα είναι που επιτρέπει στο Mersenne Twister να παράγει υψηλής ποιότητας ψευδοτυχαίους αριθμούς.

🔗 Πηγή

https://www.johndcook.com/blog/2026/05/10/the-linear-algebra-of-bit-twiddling/

Το άρθρο του John D. Cook εξηγεί πώς οι πράξεις με bits μπορούν να αναπαρασταθούν ως γραμμικοί μετασχηματισμοί πάνω από το GF(2), με εφαρμογή στον αλγόριθμο Mersenne Twister.

📚

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώΠολλαπλό βιβλίο ΝΕΟ — 437 βιβλία σε PDF

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →

Σχετικά άρθρα