Προσπαθώ να μάθω τη C στον ελεύθερο χρόνο μου και άλλες γλώσσες (C#, Java, κ.λπ.) έχουν την ίδια έννοια (και συχνά τους ίδιους τελεστές) ...
Αυτό που αναρωτιέμαι είναι, σε ένα βασικό επίπεδο, τι κάνει η μετατόπιση bit (<<
, >>
, >>>>
), ποια προβλήματα μπορεί να βοηθήσει να λυθούν, και ποιες δυσκολίες παραμονεύουν πίσω από τη στροφή; Με άλλα λόγια, ένας οδηγός για απόλυτους αρχάριους για το bit shifting σε όλη του την καλοσύνη.
Οι τελεστές μετατόπισης bit κάνουν ακριβώς αυτό που υποδηλώνει το όνομά τους. Μετατοπίζουν τα bits. Ακολουθεί μια σύντομη (ή όχι και τόσο σύντομη) εισαγωγή στους διάφορους τελεστές μετατόπισης.
>>
είναι ο αριθμητικός (ή προσημασμένος) τελεστής δεξιάς μετατόπισης.>>>>
είναι ο λογικός (ή μη προσημασμένος) τελεστής δεξιάς μετατόπισης.<<
είναι ο τελεστής αριστερής μετατόπισης και καλύπτει τις ανάγκες τόσο της λογικής όσο και της αριθμητικής μετατόπισης.Όλοι αυτοί οι τελεστές μπορούν να εφαρμοστούν σε ακέραιες τιμές (int
, long
, ενδεχομένως short
και byte
ή char
). Σε ορισμένες γλώσσες, η εφαρμογή των τελεστών μετατόπισης σε οποιονδήποτε τύπο δεδομένων μικρότερο του int
αλλάζει αυτόματα το μέγεθος του τελεστή ώστε να είναι int
.
Σημειώστε ότι ο τελεστής <<<<
δεν είναι τελεστής, διότι θα ήταν περιττός.
Σημειώστε επίσης ότι οι C και C++ δεν κάνουν διάκριση μεταξύ των τελεστών δεξιάς μετατόπισης. Παρέχουν μόνο τον τελεστή >>
, και η συμπεριφορά της δεξιάς μετατόπισης ορίζεται από την εφαρμογή για προσημασμένους τύπους. Η υπόλοιπη απάντηση χρησιμοποιεί τους τελεστές της C# / Java.
(Σε όλες τις επικρατούσες υλοποιήσεις της C και της C++, συμπεριλαμβανομένων των gcc και clang/LLVM, ο τελεστής >>
σε προσημασμένους τύπους είναι αριθμητικός. Κάποιος κώδικας το υποθέτει αυτό, αλλά δεν είναι κάτι που εγγυάται το πρότυπο. Ωστόσο, δεν είναι ανεπίσημο- το πρότυπο απαιτεί από τις υλοποιήσεις να το ορίζουν με τον ένα ή τον άλλο τρόπο. Ωστόσο, οι αριστερές μετατοπίσεις αρνητικών προσημασμένων αριθμών είναι απροσδιόριστη συμπεριφορά (υπερχείλιση προσημασμένων ακεραίων). Έτσι, εκτός αν χρειάζεστε αριθμητική δεξιά μετατόπιση, είναι συνήθως καλή ιδέα να κάνετε την μετατόπιση των bit σας με τύπους χωρίς πρόσημο).
Οι ακέραιοι αποθηκεύονται, στη μνήμη, ως μια σειρά από bits. Για παράδειγμα, ο αριθμός 6 αποθηκευμένος ως ακέραιος αριθμός 32 bit θα ήταν:
00000000 00000000 00000000 00000110
Μετατοπίζοντας αυτό το μοτίβο bit προς τα αριστερά κατά μία θέση (6 << 1
) θα προέκυπτε ο αριθμός 12:
00000000 00000000 00000000 00001100
Όπως μπορείτε να δείτε, τα ψηφία έχουν μετατοπιστεί προς τα αριστερά κατά μία θέση και το τελευταίο ψηφίο στα δεξιά είναι γεμάτο με ένα μηδέν. Θα μπορούσατε επίσης να σημειώσετε ότι η μετατόπιση προς τα αριστερά ισοδυναμεί με πολλαπλασιασμό με δυνάμεις του 2. Έτσι, το 6 << 1
ισοδυναμεί με 6 * 2
, και το 6 << 3
ισοδυναμεί με 6 * 8
. Ένας καλός μεταγλωττιστής βελτιστοποίησης θα αντικαταστήσει τους πολλαπλασιασμούς με μετατοπίσεις όταν είναι δυνατόν.
Σημειώστε ότι αυτές είναι όχι κυκλικές μετατοπίσεις. Μετατόπιση αυτής της τιμής προς τα αριστερά κατά μία θέση (3,758,096,384 << 1
):
11100000 00000000 00000000 00000000
προκύπτει η τιμή 3.221.225.472:
11000000 00000000 00000000 00000000
Το ψηφίο που μετατοπίζεται "από το τέλος" χάνεται. Δεν αναδιπλώνεται.
Η λογική δεξιά μετατόπιση είναι το αντίστροφο της αριστερής μετατόπισης. Αντί να μετακινούνται bit προς τα αριστερά, απλά μετακινούνται προς τα δεξιά. Για παράδειγμα, η μετατόπιση του αριθμού 12:
00000000 00000000 00000000 00001100
προς τα δεξιά κατά μία θέση (12 >>>> 1
) θα μας επιστρέψει το αρχικό μας 6:
00000000 00000000 00000000 00000110
Βλέπουμε λοιπόν ότι η μετατόπιση προς τα δεξιά είναι ισοδύναμη με τη διαίρεση με δυνάμεις του 2.
Ωστόσο, μια μετατόπιση δεν μπορεί να ανακτήσει τα "χαμένα" bits. Για παράδειγμα, αν μετατοπίσουμε αυτό το μοτίβο:
00111000 00000000 00000000 00000110
προς τα αριστερά κατά 4 θέσεις (939,524,102 <<4
), θα πάρουμε 2,147,483,744:
10000000 00000000 00000000 01100000
και στη συνέχεια μετατοπίζοντας προς τα πίσω ((939,524,102 << 4) >>> 4
) παίρνουμε 134,217,734:
00001000 00000000 00000000 00000110
Δεν μπορούμε να πάρουμε πίσω την αρχική μας τιμή όταν έχουμε χάσει bits.
Η αριθμητική δεξιά μετατόπιση είναι ακριβώς όπως η λογική δεξιά μετατόπιση, μόνο που αντί να γεμίζει με μηδέν, γεμίζει με το πιο σημαντικό bit. Αυτό συμβαίνει επειδή το πιο σημαντικό bit είναι το sign bit, ή το bit που διακρίνει τους θετικούς και τους αρνητικούς αριθμούς. Με το γέμισμα με το πιο σημαντικό bit, η αριθμητική δεξιά μετατόπιση διατηρεί το πρόσημο.
Για παράδειγμα, αν ερμηνεύσουμε αυτό το μοτίβο bit ως αρνητικό αριθμό:
10000000 00000000 00000000 01100000
έχουμε τον αριθμό -2.147.483.552. Αν τον μετατοπίσουμε προς τα δεξιά κατά 4 θέσεις με την αριθμητική μετατόπιση (-2,147,483,552 >> 4) θα μας δώσει:
11111000 00000000 00000000 00000110
ή τον αριθμό -134.217.722.
Βλέπουμε λοιπόν ότι διατηρήσαμε το πρόσημο των αρνητικών μας αριθμών χρησιμοποιώντας την αριθμητική δεξιά μετατόπιση και όχι τη λογική δεξιά μετατόπιση. Και για άλλη μια φορά, βλέπουμε ότι εκτελούμε διαίρεση με δυνάμεις του 2.
Ας πούμε ότι έχουμε ένα μόνο byte:
0110110
Εφαρμόζοντας μια απλή αριστερή μετατόπιση bit μας δίνει:
1101100
Το αριστερότερο μηδέν μετατοπίστηκε από το byte και ένα νέο μηδέν προστέθηκε στο δεξί άκρο του byte.
Τα bits δεν ανατρέπονται, απορρίπτονται. Αυτό σημαίνει ότι αν μετατοπίσετε αριστερά το 1101100 και στη συνέχεια το μετατοπίσετε δεξιά, δεν θα λάβετε πίσω το ίδιο αποτέλεσμα.
Η αριστερή μετατόπιση κατά N ισοδυναμεί με πολλαπλασιασμό με 2N.
Η μετατόπιση προς τα δεξιά κατά N είναι (αν χρησιμοποιείτε ones' complement) ισοδύναμη με τη διαίρεση με 2N και στρογγυλοποίηση στο μηδέν.
Η μετατόπιση bit μπορεί να χρησιμοποιηθεί για εξωφρενικά γρήγορο πολλαπλασιασμό και διαίρεση, με την προϋπόθεση ότι εργάζεστε με μια δύναμη του 2. Σχεδόν όλες οι ρουτίνες γραφικών χαμηλού επιπέδου χρησιμοποιούν τη μετατόπιση bit.
Για παράδειγμα, πολύ παλιά, χρησιμοποιούσαμε τη λειτουργία 13h (320x200 256 χρώματα) για παιχνίδια. Στη λειτουργία 13h, η μνήμη βίντεο ήταν τοποθετημένη διαδοχικά ανά εικονοστοιχείο. Αυτό σήμαινε ότι για να υπολογίσετε τη θέση για ένα εικονοστοιχείο, θα χρησιμοποιούσατε τα ακόλουθα μαθηματικά:
memoryOffset = (row * 320) + column
Τώρα, εκείνη την εποχή, η ταχύτητα ήταν κρίσιμη, οπότε χρησιμοποιούσαμε bitshifts για να κάνουμε αυτή τη λειτουργία.
Ωστόσο, το 320 δεν είναι δύναμη του δύο, οπότε για να το παρακάμψουμε αυτό πρέπει να βρούμε ποια είναι η δύναμη του δύο που προστιθέμενη μαζί κάνει 320:
(row * 320) = (row * 256) + (row * 64)
Τώρα μπορούμε να το μετατρέψουμε σε αριστερές μετατοπίσεις:
(row * 320) = (row << 8) + (row << 6)
Για ένα τελικό αποτέλεσμα:
memoryOffset = ((row << 8) + (row << 6)) + column
Τώρα παίρνουμε την ίδια μετατόπιση όπως και πριν, μόνο που αντί για μια ακριβή πράξη πολλαπλασιασμού, χρησιμοποιούμε τα δύο bitshifts... σε x86 θα ήταν κάπως έτσι (σημείωση, έχει περάσει πολύς καιρός από τότε που έκανα assembly (σημείωση του συντάκτη: διόρθωσα μερικά λάθη και πρόσθεσα ένα παράδειγμα 32-bit)):
mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]
; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov
Σύνολο: 28 κύκλοι σε όποια αρχαία CPU είχε αυτούς τους χρονισμούς.
Vrs
mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6; 2
shl di, 8; 2
add di, ax; 2 (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]
12 κύκλους στην ίδια αρχαία CPU.
Ναι, θα δουλεύαμε τόσο σκληρά για να μειώσουμε 16 κύκλους CPU.
Σε λειτουργία 32 ή 64-bit, και οι δύο εκδόσεις γίνονται πολύ πιο σύντομες και γρήγορες. Οι σύγχρονες CPUs out-of-order execution όπως η Intel Skylake (βλ. http://agner.org/optimize/) έχουν πολύ γρήγορο πολλαπλασιασμό υλικού (χαμηλή καθυστέρηση και υψηλή απόδοση), οπότε το κέρδος είναι πολύ μικρότερο. Η οικογένεια AMD Bulldozer είναι λίγο πιο αργή, ειδικά για τον πολλαπλασιασμό 64-bit. Στις CPUs της Intel, και στην AMD Ryzen, οι δύο μετατοπίσεις είναι ελαφρώς χαμηλότερη λανθάνουσα κατάσταση, αλλά περισσότερες εντολές από έναν πολλαπλασιασμό (που μπορεί να οδηγήσει σε χαμηλότερη απόδοση):
imul edi, [row], 320 ; 3 cycle latency from [row] being ready
add edi, [column] ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column], in 4 cycles from [row] being ready.
vs.
mov edi, [row]
shl edi, 6 ; row*64. 1 cycle latency
lea edi, [edi + edi*4] ; row*(64 + 64*4). 1 cycle latency
add edi, [column] ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column], in 3 cycles from [row] being ready.
Οι μεταγλωττιστές θα το κάνουν αυτό για εσάς: gcc, clang και MSVC χρησιμοποιούν όλα shift+lea όταν βελτιστοποιούν το return 320*row + col;
.
Το πιο ενδιαφέρον πράγμα που πρέπει να σημειωθεί εδώ είναι ότι η x86 έχει μια εντολή shift-and-add (LEA
) που μπορεί να κάνει μικρές αριστερές μετατοπίσεις και να προσθέσει ταυτόχρονα, με την ίδια απόδοση όπως και η εντολή add
. Η ARM είναι ακόμη πιο ισχυρή: ένας τελεστής οποιασδήποτε εντολής μπορεί να μετατοπιστεί αριστερά ή δεξιά δωρεάν. Έτσι, η κλιμάκωση με μια σταθερά σε χρόνο μεταγλώττισης που είναι γνωστό ότι είναι δύναμη του 2 μπορεί να είναι ακόμα πιο αποδοτική από έναν πολλαπλασιασμό.
Εντάξει, πίσω στις σύγχρονες μέρες... κάτι πιο χρήσιμο τώρα θα ήταν να χρησιμοποιήσετε bitshifting για να αποθηκεύσετε δύο τιμές 8-bit σε έναν ακέραιο 16-bit. Για παράδειγμα, στη C#:
// Byte1: 11110000
// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;
Στη C++, οι μεταγλωττιστές θα έπρεπε να το κάνουν αυτό για εσάς αν χρησιμοποιούσατε μια δομή
με δύο μέλη 8-bit, αλλά στην πράξη δεν το κάνουν πάντα.
Ένα πρόβλημα είναι ότι τα ακόλουθα εξαρτώνται από την εφαρμογή (σύμφωνα με το πρότυπο ANSI):
char x = -1;
x >> 1;
Το x μπορεί τώρα να είναι 127 (0111111111) ή ακόμα -1 (1111111111).
Στην πράξη, είναι συνήθως το τελευταίο.