Hängt die Bitverschiebung von der Endianness ab?

155

Angenommen, ich habe die Nummer 'numb'=1025 [00000000 00000000 00000100 00000001]dargestellt:

Auf Little-Endian-Maschine:

00000001 00000100 00000000 00000000

Auf Big-Endian-Maschine:

00000000 00000000 00000100 00000001

Wenn ich nun Left Shift auf 10 Bits anwende (dh: numb << = 10), sollte ich Folgendes haben:

[A] Auf Little-Endian-Maschine:

Wie ich in GDB bemerkt habe, macht Little Endian die Linksverschiebung in 3 Schritten: [Ich habe '3' Schritte gezeigt, um nur die Verarbeitung besser zu verstehen]

  1. Behandle die Nr. in der Big-Endian-Konvention:

    00000000        00000000        00000100    00000001
  2. Linksverschiebung anwenden:

    00000000        00010000        00000100        00000000
  3. Stellen Sie das Ergebnis erneut in Little-Endian dar:

    00000000        00000100        00010000        00000000 

[B]. Auf Big-Endian-Maschine:

00000000        00010000        00000100        00000000

Meine Frage ist:

Wenn ich direkt eine Linksverschiebung auf die Little Endian Convention anwende, sollte sie Folgendes ergeben:

numb::

00000001 00000100 00000000 00000000

numb << 10::

00010000 00000000 00000000 00000000

Aber eigentlich gibt es:

00000000        00000100        00010000        00000000 

Um nur das zweite Ergebnis zu erzielen, habe ich oben drei hypothetische Schritte gezeigt.

Bitte erklären Sie mir, warum die beiden oben genannten Ergebnisse unterschiedlich sind: Das tatsächliche Ergebnis von numb << 10unterscheidet sich vom erwarteten Ergebnis.

Sandeep Singh
quelle

Antworten:

194

Endianness ist die Art und Weise, wie Werte im Speicher gespeichert werden. Beim Laden in den Prozessor arbeitet der Bitverschiebungsbefehl unabhängig von der Endigkeit mit dem Wert im Register des Prozessors. Daher entspricht das Laden vom Speicher in den Prozessor der Konvertierung in Big Endian. Als nächstes wird die Verschiebungsoperation ausgeführt, und dann wird der neue Wert wieder im Speicher gespeichert, wo die Little Endian-Bytereihenfolge wieder wirksam wird.

Update dank @jww: Auf PowerPC sind die Vektorverschiebungen und -rotationen endiansensitiv. Sie können einen Wert in einem Vektorregister haben, und eine Verschiebung führt zu unterschiedlichen Ergebnissen für Little-Endian und Big-Endian .

Carl
quelle
4
Danke für die Erklärung. Können Sie bitte eine Referenz vorschlagen, wo ich solche Feinheiten besser verstehen kann?
Sandeep Singh
4
Das Beste, um Endianness zu verstehen, ist, es wirklich auf verschiedenen Architekturen auf einer eingebetteten Ebene zu verwenden. Ich könnte Sie jedoch auf diese beiden Artikel verweisen: codeproject.com/KB/cpp/endianness.aspx und ibm.com/developerworks/aix/library/au-endianc/…
Carl
3
Mein Code funktioniert also unabhängig von Endian?! das ist toll! Ich war so besorgt, dass ich meinen Code zur Hölle und zurück hacken müsste!
MarcusJ
2
@MarcusJ: Nicht unbedingt. Wenn Sie beispielsweise 4 Bytes aus einer Datei lesen, die eine 32-Bit-Ganzzahl darstellt, müssen Sie die Endianität der Daten, die Sie lesen, in Verbindung mit der Endianität des Systems, das die Daten empfängt, berücksichtigen, um sie richtig interpretieren zu können die Daten.
Carl
3
Auf PowerPC sind die Vektorverschiebungen und -rotationen endianempfindlich. Sie können einen Wert in einem Vektorregister haben, und eine Verschiebung führt zu unterschiedlichen Ergebnissen für Little-Endian und Big-Endian.
JWW
58

Nein, Bitshift wird wie jeder andere Teil von C als Wert und nicht als Repräsentation definiert. Linksverschiebung um 1 ist Multiplikation um 2, Rechtsverschiebung ist Division. (Achten Sie wie immer bei der Verwendung von bitweisen Operationen auf die Signatur. Bei vorzeichenlosen Integraltypen ist alles am besten definiert.)

Kerrek SB
quelle
1
Dies gilt grundsätzlich für die Ganzzahlarithmetik, aber C liefert viele Fälle von darstellungsabhängigem Verhalten.
Edmund
2
@Edmund: Hm ... vor allem ist die Implementierung der Vorzeichen nicht spezifiziert, und infolgedessen ist das Verhalten von bitweisen Operationen (wie Rechtsverschiebung) sowie von Modulo und Divide eine Implementierung, die auf negativen ganzen Zahlen definiert ist. Welche anderen Dinge haben Sie im Sinn, die implementierungsdefiniert sind?
Kerrek SB
@ KerrekSB Leider sind sie nicht für negative Ganzzahlen definiert. Sie sind in C89 nicht spezifiziert und in C99 + undefiniert, was eine sehr schlechte Idee war.
Paolo Bonzini
@PaoloBonzini: Ja, guter Punkt. Tatsächlich ist das sogar noch besser, da es den Punkt verstärkt, dass die Verschiebungsoperationen in Form von Werten definiert sind, möglicherweise undefiniert sind, wenn das Ergebnis nicht darstellbar ist, und dass Spekulationen über die zugrunde liegende Darstellung nicht helfen.
Kerrek SB
@KerrekSB: Die Sache ist, dass jeder tatsächlich eine Linksverschiebung benötigt, um je nach Fall sowohl als Werte als auch als Repräsentation dargestellt zu werden. Die Verwendung von Ganzzahlen ohne Vorzeichen kann andere Probleme verursachen, z. B. ist x &= -1u << 20sie höchstwahrscheinlich falsch, wenn sie x64-Bit und int32-Bit ist. Aus diesem Grund verspricht GCC, unterschriebene Schichten niemals als undefiniert oder gar nicht spezifiziert zu behandeln.
Paolo Bonzini
5

Welcher Verschiebungsbefehl zuerst die höherwertigen Bits herausschiebt, wird als Linksverschiebung betrachtet. Welcher Verschiebungsbefehl zuerst die Bits niedrigerer Ordnung herausschiebt, wird als die richtige Verschiebung angesehen. In diesem Sinne hängt das Verhalten von >>und <<für unsignedZahlen nicht von der Endianness ab.

Davislor
quelle
4

Computer schreiben Zahlen nicht so auf wie wir. Der Wert verschiebt sich einfach. Wenn Sie darauf bestehen, es Byte für Byte zu betrachten (obwohl der Computer dies nicht so macht), können Sie sagen, dass auf einer Little-Endian-Maschine das erste Byte nach links verschoben wird und die überschüssigen Bits in das zweite Byte gehen. und so weiter.

(Übrigens ist Little-Endian sinnvoller, wenn Sie die Bytes eher vertikal als horizontal mit höheren Adressen oben schreiben. So werden Speicherzuordnungsdiagramme üblicherweise gezeichnet.)

Raymond Chen
quelle
1

Die akzeptierte Antwort weist jedoch darauf hin, dass Endianess ein Konzept aus der Sicht des Gedächtnisses ist. Aber ich denke nicht, dass das die Frage direkt beantwortet.

Einige Antworten sagen mir, dass bitweise Operationen nicht von der Endianess abhängen und der Prozessor die Bytes auf andere Weise darstellen kann. Wie auch immer, es geht darum, dass Endianess abstrahiert wird.

Aber wenn wir zum Beispiel einige bitweise Berechnungen auf dem Papier durchführen, müssen Sie dann nicht zuerst die Endianess angeben? Meistens wählen wir implizit eine Endianess.

Angenommen, wir haben eine solche Codezeile

0x1F & 0xEF

Wie würden Sie das Ergebnis von Hand auf Papier berechnen?

  MSB   0001 1111  LSB
        1110 1111
result: 0000 1111

Hier verwenden wir also ein Big Endian-Format, um die Berechnung durchzuführen. Sie können auch Little Endian verwenden, um das gleiche Ergebnis zu berechnen und zu erhalten.

Übrigens, wenn wir Zahlen in Code schreiben, denke ich, dass es wie ein Big Endian-Format ist. 123456oder die 0x1Fmeisten signifikanten Zahlen beginnen von links.

Sobald wir ein Binärformat eines Wertes auf das Papier schreiben, haben wir wahrscheinlich bereits eine Endianess ausgewählt und sehen den Wert so, wie wir ihn aus dem Speicher sehen.

Zurück zur Frage: Eine Verschiebungsoperation <<sollte als Verschiebung von LSB (niedrigstwertiges Byte) zu MSB (höchstwertiges Byte) betrachtet werden .

Dann wie für das Beispiel in der Frage:

numb=1025

Kleiner Endian

LSB 00000001 00000100 00000000 00000000 MSB

So << 10würde 10bitVerschiebung von LSB zu MSB.


Vergleich und << 10Operationen für das Little Endian-Format Schritt für Schritt:

MSB                                        LSB
    00000000  00000000  00000100  00000001  numb(1025)
    00000000  00010000  00000100  00000000  << 10

LSB                                        MSB
    00000000  00000100  00010000  00000000 numb(1025) << 10, and put in a Little Endian Format

LSB                                        MSB
    00000001  00000100  00000000  00000000 numb(1205) in Little Endian format
    00000010  00001000  00000000  00000000 << 1 
    00000100  00010000  00000000  00000000 << 2 
    00001000  00100000  00000000  00000000 << 3 
    00010000  01000000  00000000  00000000 << 4
    00100000  10000000  00000000  00000000 << 5
    01000000  00000000  00000001  00000000 << 6
    10000000  00000000  00000010  00000000 << 7
    00000000  00000001  00000100  00000000 << 8
    00000000  00000010  00001000  00000000 << 9
    00000000  00000100  00010000  00000000 << 10 (check this final result!)

Beeindruckend! Ich bekomme das erwartete Ergebnis wie im OP beschrieben!

Die Probleme, bei denen das OP nicht das erwartete Ergebnis erzielt hat, sind folgende:

  1. Es scheint, dass er nicht von LSB zu MSB gewechselt ist.

  2. Wenn Sie Bits im Little Endian-Format verschieben, sollten Sie Folgendes beachten (Gott sei Dank, ich erkenne es):

LSB 10000000 00000000 MSB << 1ist
LSB 00000000 00000001 MSB, nicht LSB 01000000 00000000 MSB

Denn für jeden Einzelnen 8bitsschreiben wir es tatsächlich in einem MSB 00000000 LSBBig Endian-Format.

So ist es wie

LSB[ (MSB 10000000 LSB) (MSB 00000000 LSB) ]MSB


Um zusammenzufassen:

  1. Obwohl bitweise Operationen blablablabla weg abstrahiert werden sollen ... müssen wir bei der Berechnung bitweiser Operationen von Hand immer noch wissen, welche Endianess wir verwenden, wenn wir das Binärformat auf das Papier schreiben. Außerdem müssen wir sicherstellen, dass alle Operatoren dieselbe Endianess verwenden.

  2. Das OP hat nicht das erwartete Ergebnis erzielt, weil er die Schaltung falsch gemacht hat.

Rick
quelle