www.mikrocontroller.net

Forum: Compiler & IDEs Dividieren durch Schiften


Autor: FrageMan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

man kann eine Zahl anhand des Nach-rechts-schiftens dividieren.
z.B. a >> 3 heisst, dass ich die Zahl a durch 8 dividiere

Frage:
Funktioniert das auch mit negativen Zahlen (long)?

Danke!

Autor: Benedikt K. (benedikt) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
FrageMan wrote:

> Frage:
> Funktioniert das auch mit negativen Zahlen (long)?

Wenn du Glück hast.
Ja, es ist wirklich so, es ist dem Compiler überlassen ob er das richtig 
macht oder nicht. Viele Compiler machen das richtig, wenn es z.B. einen 
Arithmetischen Shift gibt, aber eben nicht alle. Im Sinne einer 
Portierbaren Lösung sollte man das daher vermeiden.

Autor: Detlev T. (detlevt)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie Benedikt schon bemerkt hat, ist das Verhalten 
"implementationsspezifisch". Am Besten ist, du programmierst eine 
Integer-Division durch 2^n und überlässt es der Optimierung des 
Compilers, daraus den richtigen Prozessor-Code zu machen.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Selbst wenn ein arithmetischer Shift gemacht wird, solltest du beachten, 
daß das nicht analog zu posiiven Zahlen wirkt. Beispiel:

1 >> 1 = 0

aber

(-1) >> 1 = -1

oder anders ausgedrückt: i.d.R ist

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der Einwand von Johann L. ist korrekt.

Davon abgesehen klappt es mit dem Shiften, wenn man es richtig macht.

Es ist nämlich keineswegs Glückssache in C, sondern klar geregelt:
- Beim Shiften nach links werden generell von rechts Nullen nachgezogen
- Beim Shiften eines signed-Wertes (short, int, long, long long,
  signed, signed short, signed int, signed long, signed long long,
  signed char) nach rechts wird immer das bisherige oberste Bit
  zum Auffüllen links verwendet, also eine 0 bei positiven und eine
  1 bei negativen Zahlen.
- Beim Shiften eines unsigned-Wertes (unigned, unsigned int,
  unsigned char, unsigned short, unsigned long, unsigned long long)
  nach rechts wird links mit 0 aufgefüllt.

Hast du also eine vorzeichenbehaftete Zahl, dann wird beim Rechtsshiften
eine positive Zahl positiv bleiben und eine negative wird negativ
bleiben.
Das wird von allen C-Standards so vorgeschrieben (außer daß in älteren
Varianten kein long long zu finden ist natürlich).

(Das einzige ungeregelte daran ist die Frage, ob ein char (ohne signed
oder unsigned davor) als signed char oder als unsigned char zu
behandeln ist.
Das ist vom Compiler abhängig bzw. kann meistens über Compilerparameter
eingestellt werden.)

mfgkw

Autor: Marcus Harnisch (mharnisch) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Warum nimmst Du nicht einfach den Divisionsoperator? Compiler sind 
heutzutage durchaus in der Lage, zu erkennen, dass die Division 
gegebenenfalls durch Schiebeoperationen ersetzt werden kann? Vorteil: Es 
funktioniert.

Gruß
Marcus
http://www.doulos.com/arm

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Klaus Wachtler wrote:

> - Beim Shiften eines signed-Wertes (short, int, long, long long,
>   signed, signed short, signed int, signed long, signed long long,
>   signed char) nach rechts wird immer das bisherige oberste Bit
>   zum Auffüllen links verwendet, also eine 0 bei positiven und eine
>   1 bei negativen Zahlen.

Kühne Aussage.  Du hast sicherlich auch sofort die entsprechende
Stelle im Standard parat, die deine Aussage hinterlegt, oder?

Falls nicht: ich könnte dir dafür sofort die Stelle zitieren, die
deine Aussage widerlegt...

Autor: Stefan Ernst (sternst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Klaus Wachtler wrote:

> Es ist nämlich keineswegs Glückssache in C, sondern klar geregelt:
> ...
> - Beim Shiften eines signed-Wertes (short, int, long, long long,
>   signed, signed short, signed int, signed long, signed long long,
>   signed char) nach rechts wird immer das bisherige oberste Bit
>   zum Auffüllen links verwendet, also eine 0 bei positiven und eine
>   1 bei negativen Zahlen.
> ...
> Hast du also eine vorzeichenbehaftete Zahl, dann wird beim Rechtsshiften
> eine positive Zahl positiv bleiben und eine negative wird negativ
> bleiben.
> Das wird von allen C-Standards so vorgeschrieben (außer daß in älteren
> Varianten kein long long zu finden ist natürlich).

Das stimmt einfach nicht.
Im aktuellen Standard steht:
The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type
or if E1 has a signed type and a nonnegative value, the value of the result is the integral
part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the
resulting value is implementation-defined.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ok, bzgl. des Standards war ich wohl zu vorlaut (je nachdem, aus
welchem du da jetzt zitierst) und habe auch keinen hier greifbar.

Faktisch ändert es aber nichts, solange die Compiler sich so
verhalten wie von mir beschrieben.

Relevant dürfte hier ja vor allem der gcc sein.
Unter 
http://gcc.gnu.org/onlinedocs/gcc-4.3.2/gcc/Intege...
steht:
Signed `>>' acts on negative numbers by sign extension.

Zum Vergleich Visual Studio VS2005 (aus der Online-Hilfe):
Shifting a negative value to the right yields half
the absolute value, rounded down.
For example, –253 (binary 11111111 00000011) shifted right one
bit produces –127 (binary 11111111 10000001).
A positive 253 shifts right to produce +126.

Right shifts preserve the sign bit. When a signed integer
shifts right, the most-significant bit remains set.
When an unsigned integer shifts right, the most-significant
bit is cleared. 

Also könnte man schon so arbeiten.
Gegen eine Division spricht natürlich immer noch nichts...

mfgkw

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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?

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gast wrote:

>>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.

Sie sparen nichts damit.  Genau das ist ja der Punkt.  Ein ordentlicher
Compiler entdeckt eine Division durch konstante 2**N zur Compilezeit
und implementiert sie als Schiebeoperation, falls das Sinn hat.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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):
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.
b = a/2;

ist zwar standardkonform, liefert aber ein anderes Ergebnis und ist
weniger effizient, da der Compiler zusätzliche Befehle zur
Vorzeichenkorrektur generiert.
b = a<0 ? (a-1)/2 : a/2;

bzw.
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 ;-)

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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?

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> 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
(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 ;-)

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> 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 ;-)

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
yalu wrote:

> 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.

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. Zum Beispiel ist 
0xffff, wenn man es 20 mal nach rechts shiftet, zu 0 geworden. Hingegen 
ergibt sich nicht unbedingt 0, wenn man es um 20 nach rechts shiftet. 
Auf vielen Maschinen ein Tribut an die Effizenz der Shift-Instruktion 
und ihren Silizium-Verbrauch.

Auch darin unterscheidet sich ein Shift von einer Division (hier durch 
2^20)

> 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.

Generell nein. Nur ein recht nativer Compiler übersetzt 
C-Code-Schnippsel in vordefinierte Assembler-Schnippel.

Ein gutes Beispiel dafür ist BASCOM für BASIC, gcc -O0 ein etwas 
schlechteres für C/C++.

Bei einem optimierenden Compiler gibt es aber i.d.R. keine 1:1 Zuordnung 
zwischen C-Quelle und Asm. Praktisch alles an n:m Abbildungen ist 
denkbar, darunter auch n:0.

Das einzige, was bei gcc sicher einen arithmetischen Shift zu erzeugen 
in der Lage wäre, wäre ein nicht portierbares __builtin_ashr oder so, 
das es jedoch nicht gibt. Gleiches gilt für rotate, daß sich zwar auch 
für avr-gcc erzeugen lässt, aber Sicherheit hat man eben keine.

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

avr-gcc definiert dan ashift für 8-, 16- und 32-Bitwerte ("ashrqi3", 
"ashrhi3" und "ashrsi3" im md)

Der Code, den er erzeugt, findest du beim Suchen nach diesen Strings in

http://gcc.gnu.org/viewcvs/trunk/gcc/config/avr/av...

Für r24 >>= 7 wird zum Beispiel ausgegeben
   lsl  r24
   sbc  r24, r24

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.