Arithmetische bitweise Verschiebung rechts "a shr b" mit vorzeichenbehafteten Ganzzahlen, die in Variablen gespeichert sind - falsche Ergebnisse! Interner Delphi-Fehler?

Question

Ich habe eine Frage (oder eher einen Fehlerbericht) über Bit-Shifting-Verhalten in Delphi (getestet in Borland Delphi 7).

Ziel: Führen Sie eine "Arithmetische" bitweise Verschiebung nach rechts mit einer beliebigen Zahl durch.

Dies bedeutet, dass das Vorzeichen-Bit erweitert werden muss - die Binärzahl wird von links mit 1 anstelle von 0 gefüllt, wenn das höchstwertige Bit einer Zahl gesetzt wurde.

Also muss die Zahl "-1" nach einer arithmetischen Verschiebung rechts gleich bleiben (alle Bits = 1), aber mit "logischer Verschiebung" (die immer die Zahl mit Nullen füllt) muss eine maximale positive ganze Zahl ergeben (maximal positiv signiert Integer, um richtig zu sein)

Ich testete es nur auf 32-Bit-System (Windows); außerdem muss ich explizit mit 32-Bit-Ganzzahlen arbeiten.

Sieht aus, als gäbe es einen internen Fehler in Delphi mit "shr", wenn die Quellennummer in einer Variablen gespeichert ist.

Mein Beispielcode:

program bug; 

{$APPTYPE CONSOLE} 

var 
I:Integer; 
C:Cardinal; 

begin 
I := -1; // we’ll need that later 
C := $FFFFFFFF; 

(Es ist nur der Anfang). Als nächstes wollen wir einige "shr" s versuchen:

Writeln('0) ', -1 shr 1); 
Writeln('1) ', $FFFFFFFF shr 1); 

"-1" ist ein signiertes gleichbedeutend mit "$ FFFFFFFF". Scheint, dass "shr" Verhalten (arithmetisch oder logisch) auf der Tatsache basiert, ob die Quellennummer signiert ist oder nicht (Integer oder Kardinal).

Ausgang ist:

0) -1 
1) 2147483647 

ganz richtig. Dann muss ich versuchen, manuell diese Zahlen auf ganze Zahlen oder Kardinäle zu werfen:

Writeln('2) ', Integer(-1) shr 1); 
Writeln('3) ', Integer($FFFFFFFF) shr 1); 
Writeln('4) ', Cardinal(-1) shr 1); 
Writeln('5) ', Cardinal($FFFFFFFF) shr 1); 

Ergebnis:

2) -1 
3) -1 
4) 2147483647 
5) 2147483647 

noch korrekt. Also, ich denke, dass ich alles in "Integer" umwandeln kann, wenn ich eine arithmetische Verschiebung brauche; oder "Kardinal", wenn ich eine logische Verschiebung möchte. Aber warte! Beispiel mit Variablen (oben angegebenen):

Writeln('6) ', I shr 1); 
Writeln('7) ', C shr 1); 

Plötzlich:

6) 2147483647 
7) 2147483647 

FALSCH. Mein "I" war eine Ganzzahl mit Vorzeichen, und ich erwartete die arithmetische Verschiebung! Also könnte Casting vielleicht helfen?

Writeln('8) ', Integer(I) shr 1); 
Writeln('9) ', Cardinal(I) shr 1); 
Writeln('A) ', Integer(C) shr 1); 
Writeln('B) ', Cardinal(C) shr 1); 

Nein, immer noch das gleiche ...

8) 2147483647 
9) 2147483647 
A) 2147483647 
B) 2147483647 

Dinge noch schlimmer werden, wenn ich es eine Funktion "eine shr b" zu machen und verwenden stattdessen werde versuchen:

// Simple shift right with signed integers 
function shrI(a,b:Integer):Integer; 
begin 
Result := a shr b; 
end; 

// Simple shift right with unsigned integers 
function shrC(a,b:Cardinal):Cardinal; 
begin 
Result := a shr b; 
end; 

Jetzt:

Writeln('C) ', shrI(-1,1)); 
Writeln('D) ', shrC($FFFFFFFF,1)); 

- Es funktioniert nicht sogar mit konstanten Ausdrücken: (es macht Sinn, weil Zahlen wieder in Variablen innerhalb einer Funktion gespeichert werden)

C) 2147483647 
D) 2147483647 

Da ich meine korrekte arithmetische Verschiebung sowieso machen muss, schrieb ich diese Formeln, um dies zu tun (Verschiebung "a" nach rechts durch "b" Bits). Erstens ist die logische Verschiebung:

(a shr b) and ((1 shl (32-b))-1) 

Ich muß nur bitweise und das Ergebnis mit „32 - b“ Einsen (von rechts) „b“ links Bits im Fall „shr“ me fail zu löschen und hat arithmetische Verschiebung (kein Beispiel zeigt dies, nur um sicherzugehen). Dann wird die arithmetische Verschiebung:

(a shr b) or ((0-((a shr 31) and 1)) shl (32-b)) 

Ich muss bitweise oder das Ergebnis mit „b“ Einsen von links, aber nur, wenn höchstwertige Bit gesetzt wurde; Um dies zu tun, nehme ich zuerst das Vorzeichenbit mit "(a shr 31) und 1", negiere dann diese Zahl, um "-1" (oder $ FFFFFFFF - alle Bits = 1) zu erhalten, wenn die Quelle negativ war, und 0 andernfalls (ich setzte "0-x" statt nur "-x", weil in meinem C-Port in einigen Fällen der bcc32 C-Compiler eine Warnung vor dem Binden meldet, um eine vorzeichenlose ganze Zahl zu negieren); und schließlich habe ich es auf "32 - b" Bits verschoben, also habe ich, was ich wünsche, auch wenn "shr" fehlschlägt und Nullen gibt. Ich habe zwei Version jeder Funktion mit beiden ganzen Zahlen und Kardinäle zu behandeln (auch konnte ich Namen teilen und „Überlast“, um sie für mich, aber hier werde ich das nicht tun das Beispiel klar zu halten):

// Logical shift right with signed integers 
function srlI(a,b:Integer):Integer; 
begin 
Result := (a shr b) and ((1 shl (32-b))-1); 
end; 

// Arithmetic shift right with signed integers 
function sraI(a,b:Integer):Integer; 
begin 
Result := (a shr b) or ((0-((a shr 31) and 1)) shl (32-b)); 
end; 

// Logical shift right with unsigned integers 
function srlC(a,b:Cardinal):Cardinal; 
begin 
Result := (a shr b) and ((1 shl (32-b))-1); 
end; 

// Arithmetic shift right with unsigned integers 
function sraC(a,b:Cardinal):Cardinal; 
begin 
Result := (a shr b) or ((0-((a shr 31) and 1)) shl (32-b)); 
end; 

testen sie es:

Writeln('E) ', sraI(-1,1)); 
Writeln('F) ', srlI(-1,1)); 
Writeln('G) ', sraC($FFFFFFFF,1)); 
Writeln('H) ', srlC($FFFFFFFF,1)); 

Und bekam perfekte Ergebnisse:

E) -1 
F) 2147483647 
G) 4294967295 
H) 2147483647 

(G-Fall ist nach wie vor richtig, weil "4294967295" die unsignierte Version von "-1")

Endkontrolle mit Variablen:

Writeln('K) ', sraI(I,1)); 
Writeln('L) ', srlI(I,1)); 
Writeln('M) ', sraC(C,1)); 
Writeln('N) ', srlC(C,1)); 

Perfect:

K) -1 
L) 2147483647 
M) 4294967295 
N) 2147483647 

Für diesen Fehler habe ich versucht, auch auf eine Variable und/oder versuchen Sie es verschiedene Guss die zweite Zahl (Verschiebungsbetrag) zu ändern - derselbe Fehler ist vorhanden, sieht so aus, als ob er nicht mit dem zweiten Argument zusammenhängt. Und das Ergebnis (in Integer oder Kardinal) zu werfen, bevor die Ausgabe auch nichts verbessert hat.

Um sicherzustellen, dass ich nicht nur derjenige bin, der den Fehler hat, habe ich versucht, mein gesamtes Beispiel unter http://codeforces.com/ auszuführen (dort kann ein registrierter Benutzer ein Stück Code in verschiedenen Sprachen und Compilern auf der Serverseite kompilieren und ausführen)) um die Ausgabe zu sehen.

"Delphi 7" Compiler gab mir genau das, was ich habe - Bug war vorhanden.Alternative Option "Free Pascal 2" zeigt noch mehr falsche Ausgabe:

0) 9223372036854775807 
1) 2147483647 
2) 9223372036854775807 
3) 9223372036854775807 
4) 2147483647 
5) 2147483647 
6) 2147483647 
7) 2147483647 
8) 2147483647 
9) 2147483647 
A) 2147483647 
B) 2147483647 
C) 2147483647 
D) 2147483647 
E) -1 
F) 2147483647 
G) 4294967295 
H) 2147483647 
K) -1 
L) 2147483647 
M) 4294967295 
N) 2147483647 

Strange "9223372036854775807" in Fällen 0-2-3 (es gab "-1", "Integer (-1)" und „Integer ($ FFFFFFFF) "Wer erinnert sich nicht?

Hier ist mein ganzes Beispiel in Delphi:

program bug; 

{$APPTYPE CONSOLE} 

// Simple shift right with signed integers 
function shrI(a,b:Integer):Integer; 
begin 
Result := a shr b; 
end; 

// Simple shift right with unsigned integers 
function shrC(a,b:Cardinal):Cardinal; 
begin 
Result := a shr b; 
end; 

// Logical shift right with signed integers 
function srlI(a,b:Integer):Integer; 
begin 
Result := (a shr b) and ((1 shl (32-b))-1); 
end; 

// Arithmetic shift right with signed integers 
function sraI(a,b:Integer):Integer; 
begin 
Result := (a shr b) or ((0-((a shr 31) and 1)) shl (32-b)); 
end; 

// Logical shift right with unsigned integers 
function srlC(a,b:Cardinal):Cardinal; 
begin 
Result := (a shr b) and ((1 shl (32-b))-1); 
end; 

// Arithmetic shift right with unsigned integers 
function sraC(a,b:Cardinal):Cardinal; 
begin 
Result := (a shr b) or ((0-((a shr 31) and 1)) shl (32-b)); 
end; 

var 
I:Integer; 
C:Cardinal; 

begin 
I := -1; 
C := $FFFFFFFF; 

Writeln('0) ', -1 shr 1); 
Writeln('1) ', $FFFFFFFF shr 1); 
// 0) -1   - correct 
// 1) 2147483647 - correct 

Writeln('2) ', Integer(-1) shr 1); 
Writeln('3) ', Integer($FFFFFFFF) shr 1); 
// 2) -1   - correct 
// 3) -1   - correct 

Writeln('4) ', Cardinal(-1) shr 1); 
Writeln('5) ', Cardinal($FFFFFFFF) shr 1); 
// 4) 2147483647 - correct 
// 5) 2147483647 - correct 

Writeln('6) ', I shr 1); 
Writeln('7) ', C shr 1); 
// 6) 2147483647 - INCORRECT! 
// 7) 2147483647 - correct 

Writeln('8) ', Integer(I) shr 1); 
Writeln('9) ', Cardinal(I) shr 1); 
// 8) 2147483647 - INCORRECT! 
// 9) 2147483647 - correct 

Writeln('A) ', Integer(C) shr 1); 
Writeln('B) ', Cardinal(C) shr 1); 
// A) 2147483647 - INCORRECT! 
// B) 2147483647 - correct 

Writeln('C) ', shrI(-1,1)); 
Writeln('D) ', shrC($FFFFFFFF,1)); 
// C) 2147483647 - INCORRECT! 
// D) 2147483647 - correct 

Writeln('E) ', sraI(-1,1)); 
Writeln('F) ', srlI(-1,1)); 
// E) -1   - correct 
// F) 2147483647 - correct 

Writeln('G) ', sraC($FFFFFFFF,1)); 
Writeln('H) ', srlC($FFFFFFFF,1)); 
// G) 4294967295 - correct 
// H) 2147483647 - correct 

Writeln('K) ', sraI(I,1)); 
Writeln('L) ', srlI(I,1)); 
// K) -1   - correct 
// L) 2147483647 - correct 

Writeln('M) ', sraC(C,1)); 
Writeln('N) ', srlC(C,1)); 
// M) 4294967295 - correct 
// N) 2147483647 - correct 

end. 

Dann war ich Kuriosität, ist dieser Fehler auch in C++? Ich habe einen Port nach C++ geschrieben und benutze (Borland!) Bcc32.exe, um es zu kompilieren.

Ergebnisse:

0) -1 
1) 2147483647 
2) -1 
3) -1 
4) 2147483647 
5) 2147483647 
6) -1 
7) 2147483647 
8) -1 
9) 2147483647 
A) -1 
B) 2147483647 
C) -1 
D) 2147483647 
E) -1 
F) 2147483647 
G) 4294967295 
H) 2147483647 
K) -1 
L) 2147483647 
M) 4294967295 
N) 2147483647 

Alles ist in Ordnung. Hier ist C++ Version, falls jemand will auch aussehen:

#include <iostream> 
using namespace std; 

// Simple shift right with signed integers 
int shrI(int a, int b){ 
return a >> b; 
} 

// Simple shift right with unsigned integers 
unsigned int shrC(unsigned int a, unsigned int b){ 
return a >> b; 
} 

// Logical shift right with signed integers 
int srlI(int a, int b){ 
return (a >> b) & ((1 << (32-b))-1); 
} 

// Arithmetic shift right with signed integers 
int sraI(int a, int b){ 
return (a >> b) | ((0-((a >> 31) & 1)) << (32-b)); 
} 

// Logical shift right with unsigned integers 
unsigned int srlC(unsigned int a, unsigned int b){ 
return (a >> b) & ((1 << (32-b))-1); 
} 

// Arithmetic shift right with unsigned integers 
unsigned int sraC(unsigned int a, unsigned int b){ 
return (a >> b) | ((0-((a >> 31) & 1)) << (32-b)); 
} 

int I; 
unsigned int C; 

int main(){ 
I = -1; 
C = 0xFFFFFFFF; 

cout<<"0) "<<(-1 >> 1)<<endl; 
cout<<"1) "<<(0xFFFFFFFF >> 1)<<endl; 
// 0) -1   - correct 
// 1) 2147483647 - correct 

cout<<"2) "<<(((int)(-1)) >> 1)<<endl; 
cout<<"3) "<<(((int)(0xFFFFFFFF)) >> 1)<<endl; 
// 2) -1   - correct 
// 3) -1   - correct 

cout<<"4) "<<(((unsigned int)(-1)) >> 1)<<endl; 
cout<<"5) "<<(((unsigned int)(0xFFFFFFFF)) >> 1)<<endl; 
// 4) 2147483647 - correct 
// 5) 2147483647 - correct 

cout<<"6) "<<(I >> 1)<<endl; 
cout<<"7) "<<(C >> 1)<<endl; 
// 6) -1   - correct 
// 7) 2147483647 - correct 

cout<<"8) "<<(((int)(I)) >> 1)<<endl; 
cout<<"9) "<<(((unsigned int)(I)) >> 1)<<endl; 
// 8) -1   - correct 
// 9) 2147483647 - correct 

cout<<"A) "<<(((int)(C)) >> 1)<<endl; 
cout<<"B) "<<(((unsigned int)(C)) >> 1)<<endl; 
// A) -1   - correct 
// B) 2147483647 - correct 

cout<<"C) "<<(shrI(-1,1))<<endl; 
cout<<"D) "<<(shrC(0xFFFFFFFF,1))<<endl; 
// C) -1   - correct 
// D) 2147483647 - correct 

cout<<"E) "<<(sraI(-1,1))<<endl; 
cout<<"F) "<<(srlI(-1,1))<<endl; 
// E) -1   - correct 
// F) 2147483647 - correct 

cout<<"G) "<<(sraC(0xFFFFFFFF,1))<<endl; 
cout<<"H) "<<(srlC(0xFFFFFFFF,1))<<endl; 
// G) 4294967295 - correct 
// H) 2147483647 - correct 

cout<<"K) "<<(sraI(I,1))<<endl; 
cout<<"L) "<<(srlI(I,1))<<endl; 
// K) -1   - correct 
// L) 2147483647 - correct 

cout<<"M) "<<(sraC(C,1))<<endl; 
cout<<"N) "<<(srlC(C,1))<<endl; 
// M) 4294967295 - correct 
// N) 2147483647 - correct 

} 

Vor Posting hier habe ich versucht, dieses Problem zu suchen, und fanden keine Erwähnung dieser Fehler gefunden. Auch ich schaute hier: What is the behaviour of shl and shr for non register sized operands? und hier: Arithmetic Shift Right rather than Logical Shift Right - aber dort wurden andere Probleme diskutiert (dass der Compiler intern jeden Typ auf 32-Bit-Zahl vor der eigentlichen Verschiebung umwandelt oder mehr als 31 Bits verschiebt), aber nicht mein Bug.

Aber warte, hier ist mein Problem: http://galfar.vevb.net/wp/2009/shift-right-delphi-vs-c/!

Mit einer Bemerkung: sie sagen -

In Delphi die SHR ist immer eine Operation SHR: es dauert nie das Zeichen berücksichtigt.

Aber mein Beispiel zeigt, dass Delphi tut take Zeichen berücksichtigt, aber nur, wenn die Quelle Nummer ist ein konstanter Ausdruck, keine Variable. So ist "-10 shr 2" gleich "-3", aber "x shr 2" ist gleich "1073741821", wenn "x: = - 10".

Also ich denke, das ist ein Fehler, und kein "Verhalten", das "shr" ist immer logisch. Du siehst, nicht immer.
Der Versuch, alle Compiler-Optionen zu aktivieren/deaktivieren, z. B. eine Bereichsprüfung oder Optimierungen, hat nichts geändert.

Auch, hier habe ich Beispiele zur Umgehung dieses Problems und richtige Rechenkorrektur richtig geschrieben. Und meine Hauptfrage ist: Habe ich recht?

Scheint, dass die linke Verschiebung in Delphi immer gut ist (es verwendet nie das ursprüngliche Vorzeichenbit und nicht "undefiniert"): bei vorzeichenbehafteten Ganzzahlen verhält es sich wie ein Kardinal, bevor es verschoben wird und das Ergebnis zurück in Ganzzahl - eine Zahl kann wurde plötzlich natürlich negativ). Aber jetzt frage ich mich, gibt es noch andere ähnliche Fehler in Delphi? Dies ist der erste wirklich signifikante Bug, den ich jemals in Delphi 7 entdeckt habe. Ich liebe Delphi mehr als C++, weil ich immer sicher bin, dass mein Code immer das macht, was ich will, ohne jedes neue, ungewöhnliche Stück Code zu testen zu schreiben (IMHO).

P.S. Hier sind einige nützliche Links, die mir das StackOverflow-System vorschlägt, als ich meinen Titel eingegeben habe, bevor ich diese Frage gepostet habe.Auch hier interessante Informationen, aber nicht über diesen Fehler:

Arithmetic bit-shift on a signed integer
Signed right shift = strange result?
Bitwise shift operators on signed types
Should you always use 'int' for numbers in C, even if they are non-negative?
Are the results of bitwise operations on signed integers defined?
Verifying that C/C++ signed right shift is arithmetic for a particular compiler?
Emulating variable bit-shift using only constant shifts?

P.P.S. Vielen Dank an das Exchange-Team für die Unterstützung bei der Veröffentlichung dieses Artikels. Leute, du rockst!

Answer 1

Es ist ein Fehler, aber es ist nicht, was Sie denken. Hier ist die documentation für shr:

Wenn x eine negative ganze Zahl ist, werden die SHL und SHR-Operationen deutlich gemacht im folgenden Beispiel:

var 
    x: integer; 
    y: string; 

... 
begin 
    x := -20; 
    x := x shr 1; 
    //As the number is shifted to the right by 1 bit, the sign bit's value replaced is 
    //with 0 (all negative numbers have the sign bit set to 1). 

    y := IntToHex(x, 8); 
    writeln(y); 
    //Therefore, x is positive. 
    //Decimal value: 2147483638 
    //Hexadecimal value: 7FFFFFF6 
    //Binary value: 0111 1111 1111 1111 1111 1111 1111 0110 
end. 

So shr und shl sind immer logisch Verschiebung und sind keine arithmetische Verschiebung.

Der Defekt ist eigentlich im Umgang mit negativen wahren Konstanten:

Writeln('0) ', -1 shr 1); 

Hier -1 ist ein Wert mit Vorzeichen. Es hat tatsächlich den Typ Shortint, eine vorzeichenbehaftete 8-Bit-Ganzzahl. Die Shift-Operatoren arbeiten jedoch mit 32-Bit-Werten, daher wird das Vorzeichen auf einen 32-Bit-Wert erweitert. Das heißt also, dass dieser Auszug zwei Zeilen mit identischem Ausgang produzieren sollte:

var 
    i: Integer; 
.... 
i := -1; 
Writeln(-1 shr 1); 
Writeln(i shr 1); 

und daß der Ausgang sein soll:

2147483647 
2147483647 

Auf moderne Versionen von Delphi, sicherlich ab Version 2010 und später, aber möglicherweise sogar frühere Versionen, das ist der Fall.

Aber nach Ihrer Frage, in Delphi 7, -1 shr 1 wertet -1 was falsch ist, weil shr logische Verschiebung ist.

Wir können die Ursache des Fehlers erraten. Der Compiler wertet -1 shr 1 aus, weil es ein konstanter Wert ist, und der Compiler tut es einfach falsch, indem er arithmetische Verschiebung anstelle von logischer Verschiebung verwendet.

Im Übrigen enthält die Dokumentation einen weiteren Fehler. Dort heißt es:

Die Operationen x SHL y und x SHR y den Wert von x nach links oder rechts von y Bits verschiebt, die (wenn x eine ganze Zahl ohne Vorzeichen ist) äquivalent zur Multiplikation oder x Dividieren durch 2^y; Das Ergebnis ist vom selben Typ wie x.

Der letzte Teil ist nicht wahr. Der Ausdruck x shl y ist ein 32-Bit-Typ, wenn x ein 8-, 16- oder 32-Bit-Typ ist, andernfalls ein 64-Bit-Typ.

---

Da Ihr eigentliches Ziel die arithmetische Verschiebung ist, ist Ihnen das alles egal. Sie können shl oder shr nicht verwenden. Sie müssen die arithmetische Verschiebung selbst durchführen. Ich schlage vor, dass Sie dies mit Inline-Assembler tun, da ich vermute, dass dies letztendlich leichter zu lesen und zu verifizieren ist.

Answer 2

Wenn Sie mit den asm-Versionen der arithmetischen Verschiebungen stecken, hier einige Code sind, die funktionieren würden:

Beachten Sie, dass nach: http://docwiki.embarcadero.com/RADStudio/XE8/en/Program_Control
Die ersten drei Parameter in Registern übergeben werden, wie folgt: EAX , EDX, ECX

in 64-Bit-Register der Reihenfolge ist: RCX, RDX, R8, R9

das Ergebnis wird in EAX Funktionen weitergegeben

0.123.

unit SARL; 

interface 

    function sar(const base: integer; shift: byte): integer; 
    function sal(const base: integer; shift: byte): integer; 

implementation 

    function sar(const base: integer; shift: byte): integer; 
    asm 
    {$IFDEF CPU64BIT} 
    mov eax,ecx 
    mov ecx,edx 
    sar eax,cl 
    {$ELSE} 
    mov ecx,edx 
    sar eax,cl //shr is very different from sar 
    {$ENDIF} 
    end; 

    function sal(const base: integer; shift: byte): integer; 
    asm 
    {$IFDEF CPU64BIT} 
    mov eax,ecx 
    mov ecx,edx 
    shl eax,cl 
    {$ELSE} 
    mov ecx,edx 
    shl eax,cl //Note that sal and shl are the same thing. 
    {$ENDIF} 
    end; 

end. 

Answer 3

Ich habe in Delphi 7 getestet und es scheint, dass einfach mit "Div 2" auf eine Integer-Variable direkt kompiliert zu einer SAR-Assembler-Operation (wie im CPU-Fenster angezeigt).

Update: Div nicht richtig funktioniert als Ersatz für SAR wie ich in meinem Kommentar in dieser Antwort erklärt. Der Compiler generiert eine SAR-Anweisung, testet aber das Vorzeichenbit und passt die Antwort an, indem das rechts verschobene Bit hinzugefügt wird, wenn das Vorzeichenbit gesetzt ist. Dies ergibt das richtige Verhalten für den Div-Operator bei negativen Zahlen, aber vereitelt unser Ziel, das richtige SAR-Verhalten zu erhalten.