Dividieren durch Schiften

>Gegen eine Division spricht natürlich immer noch nichts...


Dann warte ab, bis die Puristen wach werden und an Deinem Code noch 2,37 
Bit einsparen wollen.
Oder mache eine reziproke Multiplikation am besten mit Fixkomma. 
Irgendwie muß man doch Fehler in den Code bekommen. Nicht wahr?

Dass der Standard für negativen Zahlen die Division spezifiziert, den
Rechts-Shift aber nicht, war mir bisher auch nicht bewusst, da ich
generell diese Operationen mit negativen Zahlen zu vermeiden versuche.

In meinen Augen wäre es aber umgekehrt (also den Shift statt der
Division zu spezifizieren) logischer:

Praktisch jeder Prozessor hat einen ASR-Befehl (oder ein Äquivalent mit
anderem Namen), der sich (bis auf die Bitbreite) auf allen Prozessoren
gleich verhält und damit eine einheitliche und trotzdem effiziente
Implementierung des >>-Operators für vorzeichenbehaftete Zahlen zuließe.

Einen Divisionsbefehl hingegen haben nur manche Prozessoren, und ich
wäre mir nicht ganz so sicher, ob das Divisionsergebnis bei allen nach
C-Standard (also zur Null hin) gerundet wird.

Ok, bei den aktuellen Prozessoren wird der C-Standard für die Division
sicher schon bei der Entwicklung berücksichtigt, aber beim ASR stellt
sich die Frage der Rundungsrichtung erst gar nicht.

Ich frage mich nun, ob es für einen konkreten Compiler (bspw. den
AVR-GCC) einen standardkonformen C-Ausdruck gibt, der sich exakt wie der
ASR-Befehl verhält (also eine immer in negative Richtung rundende
Division durch 2) und auch als solcher übersetzt wird.

Folgende Möglichkeiten wären denkbar (a und b sind beide int8_t):

1

b = a>>1;

liefert zwar das gewünschte Ergebnis und wird tatsächlich in einen
einzelnen ASR-Befehl übersetzt, ist aber nicht standardkonform, da >>
für negatives a nicht spezifiziert ist.

1

b = a/2;

ist zwar standardkonform, liefert aber ein anderes Ergebnis und ist
weniger effizient, da der Compiler zusätzliche Befehle zur
Vorzeichenkorrektur generiert.

1

b = a<0 ? (a-1)/2 : a/2;

bzw.

1

b = (a<0 ? a-1 : a) / 2;

sind zwar standardkonform und liefern das gewünschte Ergebnis, enden
jedoch in sehr ineffizientem Code.

Hat jemand vielleicht eine bessere Lösung dieses Problems?



An dieser Stelle ist der Standard meiner Meinung nach einfach etwas
daneben. Ich würde folgende Spezifikation als sehr viel praxisnäher
betrachten:

- Der >>-Operator liefert für a>>b den um b Bits nach rechts geschobenen
  Wert von a, wobei die frei werdenden höchstwertigen b Bits des
  Ergebnisses gleich 0 werden, wenn a vorzeichenlos ist, und gleich dem
  höchstwertigen Bit von a, wenn a vorzeichenbehaftet ist.

- Der /-Operator liefert das Ergebnis der Division der beiden Operanden
  auf die nächstkleinere (d.h. negativere) ganze Zahl gerundet. Ist der
  rechte Operand negativ, ist das Ergebnis undefiniert (damit wenigstens
  etwas unspezifiziert bleibt :) ).

- Der %-Operator liefert für a%b das Ergebnis a-(a/b)*b. Auch hier ist
  das Ergebnis für negatives b undefiniert.

Mit diesen Regeln wären a>>1 und a/2 auch für negatives a äquivalent,
die Funktion f(x)=x/c wäre für konstantes c eine saubere Treppenfunk-
tion, die im Gegensatz zum offiziellen Standard auch an der Stelle 0
eine Stufe hat und damit gleichmäßig von den negativen in die positiven
Werte übergeht. Schließlich läge das Ergebnis von a%b immer im Intervall
[0,b-1], das genauso viele Elemente enthält wie es Restklassen modulo b
gibt. Im offiziellen Standard liegt das Ergebnis dagegen in dem fast
doppelt so großen Intervall [-b+1,b-1], in dem jede Restklasse außer der
0 durch zwei Werte repräsentiert wird, bspw. (1 und -b+1), (2 und -b+2)
und (b-1 und -1), was sich in der Praxis oft störend auswirkt.

Aber mich hat ja damals keiner gefragt ;-)

> b = a>>1;
>
> liefert zwar das gewünschte Ergebnis und wird tatsächlich in einen
> einzelnen ASR-Befehl übersetzt, ist aber nicht standardkonform, da
> >> für negatives a nicht spezifiziert ist.

Es ist "implementation-defined", nicht "unspecified". Das sind zwei 
verschiedene Dinge. Bei ersterem muß in der Dokumentation des Compilers 
angegeben sein, was er daraus macht.

> Hat jemand vielleicht eine bessere Lösung dieses Problems?

Wie oft brauchst du denn den Shift für negative Zahlen? Also sprich, 
bewußt eine Division durch eine Zweierpotenz, bei der aber die Rundung 
für negative Werte falsch sein soll?

> - Der >>-Operator liefert für a>>b den um b Bits nach rechts
> geschobenen  Wert von a, wobei die frei werdenden höchstwertigen b
> Bits des Ergebnisses gleich 0 werden, wenn a vorzeichenlos ist, und
> gleich dem  höchstwertigen Bit von a, wenn a vorzeichenbehaftet ist.

Bei allen in der C-Norm möglichen Repräsentationen vorzeichenbehafteter 
Zahlen? Deine Definition gibt nämlich nur bei Zweierkomplement wirklich 
einen Sinn.

> - Der /-Operator liefert das Ergebnis der Division der beiden
> Operanden  auf die nächstkleinere (d.h. negativere) ganze Zahl
> gerundet.

Das wäre aber sehr schlecht, denn erstens erwartet man meistens eine 
Rundung gegen 0, zweitens wird genau die auch von Divisions-Einheiten in 
den Prozessoren, die sowas haben, implementiert. Der Compiler müßte dann 
für eine Division umständlich die Rundung gegen 0 kaputtmachen.

> Ist der  rechte Operand negativ, ist das Ergebnis undefiniert (damit
> wenigstens  etwas unspezifiziert bleibt :) ).

"undefined" ist nochmal was anderes als "unspecified" und 
"implementation-defined". Da wird streng unterschieden.
Und warum darf nur der rechte Operand nicht negativ sein?

>> b = a>>1;
>> […] ist aber nicht standardkonform, da >> für negatives a nicht
>> spezifiziert ist.
>
> Es ist "implementation-defined", nicht "unspecified". Das sind zwei
> verschiedene Dinge.

Ok, entschuldige bitte den falschen Ausdruck. Dann ist der Ausdruck eben
nicht nicht standardkonform, sondern — zumindest gemäß Standard — nicht
portabel.

> Wie oft brauchst du denn den Shift für negative Zahlen? Also sprich,
> bewußt eine Division durch eine Zweierpotenz, bei der aber die Rundung
> für negative Werte falsch sein soll?

Den Shift als solchen mit negativen Zahlen habe ich bisher recht selten
gebraucht, ein paar Mal für irgendwelche trickreichen Bitpopeleien, an
die ich micht aber nicht mehr genau erinnern kann. Was ich aber häufig
brauchen könnte, wäre eine Division mit Abrunden. Die einfachste
Anwendung dafür ist eine Division mit "normalem" Runden (also ab 0,5 
auf-,
sonst abrunden), die man dann ganz einfach als

1

(a + b/2) / b

schreiben könnte, bei der Division nach C-Standard aber eine
Fallunterscheidung nach positiven und negativen Werten erfordert. Es
gibt aber noch viel mehr Fälle, vor allem im Zusammehang mit
Modulo-Operationen, wo eine einheitliche Rundungsrichtung praktisch
wäre.

>> - Der >>-Operator liefert für a>>b den um b Bits nach rechts
>> geschobenen  Wert von a, wobei die frei werdenden höchstwertigen b
>> Bits des Ergebnisses gleich 0 werden, wenn a vorzeichenlos ist, und
>> gleich dem  höchstwertigen Bit von a, wenn a vorzeichenbehaftet ist.
>
> Bei allen in der C-Norm möglichen Repräsentationen
> vorzeichenbehafteter Zahlen? Deine Definition gibt nämlich nur bei
> Zweierkomplement wirklich einen Sinn.

Dann sollte der Standard das Zweierkomplement als einzig erlaubtes
Signed-Integer-Format vorschreiben. Ich kenne keinen seit der Einführung
von C produzierten Mikroprozessor, der nicht im Zweierkomplement
rechnet (lasse mich aber gerne eines Besseren belehren), wo läge also
das Problem? Der C-Standard berücksichtigt ja auch keine Prozessoren,
die statt im Binär- im Ternärsystem rechnen.

Als Bitoperationen haben die Schiebebefehle aber ohnehin nichts mit
Arithmetik und damit auch wenig mit der internen Zahlendarstellung zu
tun. Hat ein Prozessor also eine andere Zahlendarstellung als das
Zweierkomplement, bedeutet das für meine obige Spezifikation nur, dass
man den >>-Operator nicht für Divisionen durch Zweierpotenzen
missbrauchen kann. Aber das sollte man ja sowieso nicht.

>> - Der /-Operator liefert das Ergebnis der Division der beiden
>> Operanden  auf die nächstkleinere (d.h. negativere) ganze Zahl
>> gerundet.
>
> Das wäre aber sehr schlecht, denn erstens erwartet man meistens eine
> Rundung gegen 0,

Wer ist "man"? Du? Ich jedenfalls nicht. Wenn ich es nicht besser
wüsste, würde ich erwarten, dass das Ergebnis unabhängig vom Vorzeichen
immer abgerundet wird, ähnlich wie es die Floor-Funktion bei FP-Zahlen
macht.

> zweitens wird genau die auch von Divisions-Einheiten in den
> Prozessoren, die sowas haben, implementiert.

Die Prozessoren machen das deswegen so, weil es der C-Standard so
möchte.

>> Ist der  rechte Operand negativ, ist das Ergebnis undefiniert (damit
>> wenigstens  etwas unspezifiziert bleibt :) ).
>
> "undefined" ist nochmal was anderes als "unspecified" und
> "implementation-defined". Da wird streng unterschieden.
> Und warum darf nur der rechte Operand nicht negativ sein?

Ja, da habe ich schon wieder den falschen Begriff verwendet. Ich meinte
auch hier "implementation-defined".

Grund: Bei einer Division durch negative Zahlen fallen mir einfach keine
schlüssigen Gründe für die Rundung in die eine oder in die andere
Richtung ein. Da man sie bei Integer-Zahlen so gut wie nie braucht, habe
ich gedacht, ich gestehe die Auswahl der Rundungsrichtung den
Prozessorherstellern zu ;-)

> Dann sollte der Standard das Zweierkomplement als einzig erlaubtes
> Signed-Integer-Format vorschreiben.

Tut er aber mit Absicht nicht. Er läßt auch Einerkomplement und 
Sign/Magnitude-Darstellung zu. Würde er das nicht tun, wäre auf 
entsprechenden Prozessoren ein C-Compiler nicht mehr sinnvoll umsetzbar.

> Ich kenne keinen seit der Einführung von C produzierten
> Mikroprozessor, der nicht im Zweierkomplement rechnet (lasse mich
> aber gerne eines Besseren belehren), wo läge also das Problem?

Nur weil du keinen kennst, heißt das nicht, daß es keinen gibt. In einer 
Diskussion im Usenet zu dem Thema wurden da auch Architekturen genannt, 
aber ich weiß nicht mehr welche, weil ich damit nicht arbeite.

> Als Bitoperationen haben die Schiebebefehle aber ohnehin nichts mit
> Arithmetik und damit auch wenig mit der internen Zahlendarstellung
> zu tun.

Heißt der ASM-Befehl, um den es hier geht, deshalb üblicherweise 
"arithmetischer Shift"? ;-)

> Hat ein Prozessor also eine andere Zahlendarstellung als das
> Zweierkomplement, bedeutet das für meine obige Spezifikation nur,
> dass man den >>-Operator nicht für Divisionen durch Zweierpotenzen
> missbrauchen kann. Aber das sollte man ja sowieso nicht.

Aber ich dachte, gerade darum ginge es dir. Wenn du ihn nicht dazu 
verwenden willst, sollte dich beim Schieben auch das Vorzeichenbit nicht 
interessieren. Dann brauchst du auch nur den vorzeichenlosen Shift, weil 
man Bitbasteleien eh am besten mit vorzeichenlosen Zahlen macht.

>> Das wäre aber sehr schlecht, denn erstens erwartet man meistens
>> eine Rundung gegen 0,
>
> Wer ist "man"? Du?
>
> Ich jedenfalls nicht.

Ok, eine nearest-Rundung wäre auch nicht überraschend.

> Wenn ich es nicht besser wüsste, würde ich erwarten, dass das
> Ergebnis unabhängig vom Vorzeichen immer abgerundet wird, ähnlich
> wie es die Floor-Funktion bei FP-Zahlen macht.

Das wäre jetzt z.B. das, was ich überhaupt nicht erwarten würde, sondern 
zumindest, daß beim negieren eines der Operanden auch das Ergebnis nur 
negiert wird und vom Betrag her auf jeden Fall gleich bleibt.

> Die Prozessoren machen das deswegen so, weil es der C-Standard so
> möchte.

Das glaube ich eher nicht. Es gibt ja auch genügend andere 
Programmiersprachen. Aber selbst wenn. Das wurde ja nicht willkürlich so 
festgelegt.

>> Ich kenne keinen seit der Einführung von C produzierten
>> Mikroprozessor, der nicht im Zweierkomplement rechnet (lasse mich
>> aber gerne eines Besseren belehren), wo läge also das Problem?
>
> Nur weil du keinen kennst, heißt das nicht, daß es keinen gibt. In
> einer Diskussion im Usenet zu dem Thema wurden da auch Architekturen
> genannt, aber ich weiß nicht mehr welche, weil ich damit nicht
> arbeite.

Habe gerade mal gesucht: Ja, es gab die PDP-1 und die UNIVAC 1100/2200,
die beide vorzeichenbehaftete Integers im Einerkomplement darstellten.
Beide wurden Anfang der 60er-Jahre eingeführt, allerdings reichen die
letzten Nachfolger der UNIVAC noch deutlich in die C-Ära hinein.

Damit wäre geklärt, warum das C-Konsortium dieses (heute unübliche)
Zahlenformat im Standard berücksichtigen mussten.

>> Als Bitoperationen haben die Schiebebefehle aber ohnehin nichts mit
>> Arithmetik und damit auch wenig mit der internen Zahlendarstellung zu
>> tun.
>
> Heißt der ASM-Befehl, um den es hier geht, deshalb üblicherweise
> "arithmetischer Shift"? ;-)

In Assembler wird der Befehl ja tatsächlich für Divisionen eingesetzt.
Aber in C gibt es ja die /-Operation, die von einem halbwegs aktuellen
Compiler, wo möglich, in eine Shift-Operation übersetzt wird, so dass
die >>-Operation eigentlich den Bitspielereien vorbehalten sein sollte.

>> Hat ein Prozessor also eine andere Zahlendarstellung als das
>> Zweierkomplement, bedeutet das für meine obige Spezifikation nur,
>> dass man den >>-Operator nicht für Divisionen durch Zweierpotenzen
>> missbrauchen kann. Aber das sollte man ja sowieso nicht.
>
> Aber ich dachte, gerade darum ginge es dir.

Nicht primär.

Zum einen ging es mir um die abrundende Division. Schön, aber nicht
unbedingt erforderlich wäre es zusätzlich, wenn >> einer Division durch
eine Zweierpotenz entspräche, genauso wie << einer Multiplikation mit
einer Zweierpotenz entspricht, auch für negative Zahlen. Das haben die
Hersteller gängiger C-Compiler für Zweierkomplementprozessoren auch
bestmöglich realisiert, indem sie >> für vorzeichenbehaftete Zahlen
anders übersetzen (nämlich in einen ASR) als für vorzeichenlose (LSR),
obwohl nach Standard (implementation-defined) auch für beide Fälle
einheitlich ein LSR erlaubt wäre. Damit entspricht >> zwar auch für
vorzeichenbehaftetes a weitgehend einer Division, aber eben nicht exakt,
wegen der Rundung.

Zum anderen ging es mir um die Frage, ob es einen C-Ausdruck gibt, der
unabhängig vom verwendeten Compiler das gleiche wie der ASR-Befehl
gängiger Prozessoren tut, und der zumindest von einigen ausgewählten
Compilern auch tatsächlich in einen ASR übersetzt wird. Wobei diese
Frage eher akademischer Natur ist.

>> Die Prozessoren machen das deswegen so, weil es der C-Standard so
>> möchte.
>
> Das glaube ich eher nicht. Es gibt ja auch genügend andere
> Programmiersprachen. Aber selbst wenn. Das wurde ja nicht willkürlich
> so festgelegt.

In BCPL bspw. war die Division noch implementationsabhängig:

  The division operator / yields the correct result of [the division of
  E1 by E2 if] El is divisible by E2; it is otherwise implementation
  dependent but the rounding error is never greater than 1.

  The operator rem yields the remainder of El divided by E2; its exact
  specification is Implementation dependent.

Das könnte darauf hindeuten, dass es damals, also vor der Einführung von
C, Rechner mit unterschiedlichem Rundungsverhalten bei Divisionen gab.


Aber was soll's: Es ist nun einmal alles so wie es ist, und da ich nicht
erwarte, dass C, die Compiler und die Prozessoren wegen mir geändert
werden, finde ich mich ja auch gerne damit ab :)

Nicht dass ein falscher Eindruck ensteht: Alles in allem ist C für mich
immer noch die beste Hochsprache für hardwarenahe und eine der besten
für viele sonstige Anwendungen. Da sehe ich gerne über ein paar kleine
Schönheitsfehler hinweg, die vielleicht sogar nur mir als solche
erscheinen ;-)

> Um die Lage weiter zu komplizieren und meiner obigen Ungleichung eine
> weitere hinzuzufügen, ist i.A.

> Dies tritt idR dann auf, wenn der Shift-Offset zur Compilezeit
> unbekannt ist und die Bitbreite des Operanden überschreitet.

Ja, das ist klar. Da ist erst kürzlich jemand hier im Forum
darübergestolpert.

> Bei GCC kannst du jedoch recht sicher sein, daß ein >> eines signed in
> einen ahift übersetzt wird, sofern die Maschine das kann.

Ja, und der C-Compiler von MS macht es auch so (s. Beitrag von Klaus
Wachtler), und wahrscheinlich kann man dies auch auf die meisten anderen
Compiler extrapolieren.

1 >> 1 = 0

aber

(-1) >> 1 = -1

ist es nicht hier falsch, da (-1) >>1 = -0.5 in Dezimal also 1.11 in 
Zweierkomplement ?