Bit και μαθηματική βιβλιοθήκη

Τελεστές bit

Το μάθημα Οι ακέραιοι και η αναπαράστασή τους έδειξε ότι ένας int είναι μια σειρά από bit, 32 στα συστήματα του κύκλου μαθημάτων, και ότι η τιμή του είναι το άθροισμα των βαρών των θέσεων όπου υπάρχει 1. Ως τώρα, ωστόσο, το πρόγραμμα έχει χειριστεί τον ακέραιο μόνο ως αριθμό: τον έχει προσθέσει, πολλαπλασιάσει και διαιρέσει. Όμως η ίδια σειρά δέχεται και άλλη ανάγνωση, ως συλλογή 32 απαντήσεων ναι ή όχι, και για αυτή την ανάγνωση η C++ έχει τέσσερις τελεστές που δουλεύουν πάνω στα bit ένα προς ένα, χωρίς κρατούμενο ανάμεσα στις θέσεις.

Τα bit αριθμούνται από τα δεξιά, αρχίζοντας από το 0: το bit $k$ είναι εκείνο με βάρος $2^k$. Έτσι, στο $12$, που στο δυαδικό γράφεται 1100, είναι ενεργά τα bit 2 και 3 και ανενεργά τα bit 0 και 1.

Οι τελεστές είναι οι εξής. Το δυαδικό ΚΑΙ, a & b, έχει 1 σε κάθε θέση όπου τα a και b έχουν και τα δύο 1. Το δυαδικό Ή, a | b, έχει 1 όπου τουλάχιστον ένα από τα δύο το έχει. Το αποκλειστικό Ή, a ^ b, έχει 1 όπου ακριβώς ένα από τα δύο το έχει, δηλαδή όπου τα bit διαφέρουν. Η δυαδική άρνηση, ~a, έχει έναν μόνο τελεσταίο και αντιστρέφει κάθε bit. Οι πίνακες των τριών πρώτων, για ένα ζεύγος bit $p$ και $q$, είναι εκείνοι της σύζευξης, της διάζευξης και της αποκλειστικής διάζευξης:

Όποιος έχει μελετήσει τον κύκλο μαθημάτων «Μαθηματική λογική I» θα αναγνωρίσει εδώ τους προτασιακούς συνδέσμους, με το 1 για το αληθές και το 0 για το ψευδές: ένας τελεστής bit δεν είναι τίποτε άλλο από έναν σύνδεσμο που εφαρμόζεται σε όλες τις στήλες ταυτόχρονα. Από αυτό έπεται η μέθοδος υπολογισμού με το χέρι: γράφουμε τους δύο αριθμούς στο δυαδικό, τον έναν κάτω από τον άλλον, στοιχισμένους από τα δεξιά, και εφαρμόζουμε τον πίνακα σε κάθε στήλη, χωρίς να μας απασχολούν οι γειτονικές.

Το πρόγραμμα που ακολουθεί επαληθεύει το σχήμα. Το πεδίο μορφοποίησης {:04b}, που παρουσιάστηκε στο μάθημα για τους ακεραίους, γράφει μια τιμή στο δυαδικό με τέσσερα ψηφία, συμπληρωμένα με μηδενικά.

#include <print>​int main(){    const int a{0b1100};    const int b{0b1010};    std::println("a     = {:04b} = {}", a, a);    std::println("b     = {:04b} = {}", b, b);    std::println("a & b = {:04b} = {}", a & b, a & b);    std::println("a | b = {:04b} = {}", a | b, a | b);    std::println("a ^ b = {:04b} = {}", a ^ b, a ^ b);    std::println("~a    = {}", ~a);}

a     = 1100 = 12b     = 1010 = 10a & b = 1000 = 8a | b = 1110 = 14a ^ b = 0110 = 6~a    = -13

Η τελευταία γραμμή θέλει μια εξήγηση. Η άρνηση αντιστρέφει τα 32 bit του a, όχι μόνο τα τέσσερα που γράφονται: τα 28 μηδενικά στα αριστερά γίνονται άσσοι, και ένας int που αρχίζει με 1 είναι αρνητικός σε συμπλήρωμα ως προς δύο. Όμως, σε συμπλήρωμα ως προς δύο, ο αντίθετος ενός αριθμού προκύπτει αν αντιστρέψουμε τα bit του και προσθέσουμε 1, δηλαδή $-x = {\sim}x + 1$· επομένως ${\sim}x = -x - 1$, και το ~12 αξίζει $-13$. Η δυαδική άρνηση σε έναν ακέραιο με πρόσημο δίνει λοιπόν έναν αριθμό που σπάνια ενδιαφέρει ως αριθμός: ενδιαφέρει ως συνδυασμός bit, και γι’ αυτό τα bit τα χειριζόμαστε κατά προτίμηση σε τύπους χωρίς πρόσημο, όπως θα φανεί στην παράγραφο για τις μάσκες.

Μια προειδοποίηση για τους μικρούς τύπους. Πριν από την πράξη, η C++ μετατρέπει σε int κάθε τελεσταίο ενός στενότερου ακέραιου τύπου, όπως ο std::uint8_t· είναι η προαγωγή που το μάθημα Αριθμητικές πράξεις περιέγραψε για τις αριθμητικές πράξεις, και ισχύει και εδώ. Από αυτό έπεται ότι το ~flags, με το flags τύπου std::uint8_t και τιμή 5, δεν είναι το byte 11111010, αλλά ο int $-6$, του οποίου τα 32 bit περιλαμβάνουν 24 άσσους προστιθέμενους στα αριστερά· μόνο όταν αποθηκευτεί ξανά σε έναν std::uint8_t περικόπτεται σε οκτώ bit και ανακτάται το αναμενόμενο byte, 250.

Δεν πρέπει να συγχέονται οι τελεστές bit με τους λογικούς τελεστές του μαθήματος Σχέσεις και λογική. Το 6 && 3 είναι true: και οι δύο τελεσταίοι είναι διάφοροι του μηδενός, και το αποτέλεσμα είναι bool. Το 6 & 3, αντίθετα, είναι ακέραιος, εκείνος που σχηματίζουν οι στήλες όπου και οι δύο έχουν 1. Επιπλέον, το && αποτιμάται με βραχυκύκλωση, ενώ το & αποτιμά πάντα και τους δύο τελεσταίους.