bitweises Schieben

[arrayhunter]

high,

kann mir jemand erklären, wie das bitweise schieben funktioniert ?

programmiersprache ist egal, mir geht es um das Prinzip

das check ich irgendwie noch net !

[Woodstock]

Was meinst Du denn mit Bitweises schieben? Ich habe diesen Ausdruck noch nie gehört. Ich habe schon Variablen bitweise beschrieben. Ist es das was Du meinst?

Bine

[arrayhunter]

ach so ich meinte schon schieben

z.B.

ausgabe=zahl>>1;

[Crush]

Die Bits werden tatsächlich in die Richtung (links oder rechts) verschoben. Was rausgeht wird ins Carry-Flag des Prozessors übertragen (kann aber nur in Assembler bequem abgefragt werden). Von der anderen Seite wird bei C ein 0er-Bit eingeschoben. Will man übertragene Bits von anderswo "von der anderen Seite" einfügen, muß man diese in C direkt setzen. Die Bits sind von rechts nach links durchnummeriert (ist so Standard) und zwar von 0 bis x (das hängt von der Größe des Operanden ab, kann ja Byte, int, long oder sonstwas sein). Richtung 0 zählt als rechts, Richtung der höherwertigen Bits als links. Ist also nix wirklich kompliziertes und mit diesen << und >> Operatoren auch gut ausgedrückt.

Künstlich muß man in C echte Rotationen realisieren. Das bedeutet, daß die Bits die rausgeschoben werden an der anderen Seite wieder eingefügt werden - was Prozessoren aber an sich von Natur aus schon können (halte ich für ein Manko von C).

[nic_power]

Bitweises Schieben ist eine Operation, die direkt durch die CPU implementiert wird. D.h. eine Shift-Operation in C wird idealerweise auf genau einen Assemblerbefehl abgebildet. Die Syntax ist dabei stark von der CPU abhaengig:

DEPW,Z  %r19,%sar,32,%r22

Shiftet beispielsweise den Wert in Register R19 um %sar Bits nach links und legt das Ergebnis in Register R22 ab. bzw.

sll %l0,%o0,%l0

Shiftet Register %l0 um %o0 Bits nach links und speichert das Ergebnis in Register %l0.

Aufgabe fuer die Hacker: aus welchen Architekturen stammen die Beispiele (Beim zweiten Beispiel handelt es sich um die in meinen Augen "schoenste" RISC-Architektur die es gibt)?

Nic

[Crush]

Ich fand die Motorla 68K-Serie trotzdem immer noch am "schönsten" überhaupt.

lsr #4,op = logische Rechtsverschiebung um 4 Bits

asr #2,op = arithmetische Rechtsverschiebung (Vorzeichengenau) um 2 Bits

ror #1,op = Rechtsrotation des Operanden um 1 Bit (was rechts rausgeht wird links eingefügt)

roxr #1,op = Rechtsrotation mit dem Carry-Register als Zusatz-Bit, dessen Inhalt reinrotiert wird und das rechts in Carry kommt.

[nic_power]

Hallo,

Sowas (logisches und arithmetisches shift) gibt es natuerlich auch bei den beiden oben genannten Architekturen. Ich habe aber versucht einfache Beispiele zu finden, die auch auf die urspruengliche Fragestellung passen. Insbesondere die erste Architektur "glaenzt" durch komplexe Assemblerinstruktionen (bsp: a=b*c+d, mit Vorzeichenwechsel in einem Takt), obwohl es sich um eine reine RISC-Architektur handelt.

Nic

[Crush]

Nr.1 ist vermutlich ein HP PA-RISC 8600 (oder auch kleiner) und

Nr.2 ein MIPS (R3000) Prozessor.

Komplexe Befehle sind zwar schön und gut aber können einem auch die Übersicht über die Programmstruktur unter Umständen erschweren. Natürlich bietet Motorola so extrem komplexe Befehle nicht an. Aber eines habe ich in meinem Leben gelernt: Man kann sich - einmal in ASM eingearbeitet - in jeden Prozessorbefehlssatz ruckzuck zurechtfinden. Eigentlich hat jeder Prozessor seine eigene "Schönheit".

Richtig oder falsch?

Wichtig ist für Blast nur zu wissen, daß man in C eigentlich in der effizienten Anwendung solcher direkten Bitoperationen ziemlich beschnitten ist. Deshalb bietet nahezu jeder C/C++-Compiler auch inline-Assembler an.

[nic_power]

Original geschrieben von Crush

Nr.1 ist vermutlich ein HP PA-RISC 8600 (oder auch kleiner) und

Nr.2 ein MIPS (R3000) Prozessor.

Nicht schlecht, Nr. 1 ist ein Volltreffer (PA-RISC) . Das zweite ist eine SPARC-CPU (wobei ich nicht ausschliessen will, dass der entsprechende MIPS-Befehl den gleichen Namen traegt).

Nic

[Crush]

Ich wollte zuerst auf SPARC tippen, aber den Befehl gibt´s bei beiden - es bestand ziemlich 50:50 Chance - war aber auch nur rein interessehalber zusammengesucht. Mit den Dingern habe ich noch nie zu tun gehabt. Trotzdem irgendwie exotisch. Momentan habe ich mir mal die Docs über PowerPC runtergezogen weil ich mir dachte, daß man den vielleicht auch mal als Emulation für MAC und Amiga-Emus umsetzen sollte ... vielleicht fang´ ich irgendwann tatsächlich damit an.

[Klotzkopp]

@Crush und nic_power: Bleibt bitte beim Thema. Oder macht im Sonstige-Forum einen neuen Thread auf, so was wie "Die bizarre Schönheit der Assemblersprache im Wandel der Architekturen"

@blast:

Unsere beiden Assembler-Freaks haben jetzt zwar technisch bis ins kleinste erklärt, was bitweises Schieben ist, aber ein Aspekt ist bisher IMO zu kurz gekommen: Was das ganze soll.

Bitweises Schieben bedeutet, bei einer Zahl im Dualsystem alle Stellen nach links oder rechts zu verschieben. Das ändert den Wert immer um den Faktor zwei bzw. 1/2 (je nach Schieberichtung).

10 << 1 ergibt 20

10 >> 1 ergibt 5

10 << 2 ergibt 40

10 >> 2 ergibt 2

Im letzten Fall zeigt sich die Besonderheit, dass Bits, die aus dem Wertebereich der Zahl "herausgeschoben" werden, verloren sind. Das gilt auch für das obere Ende.

Man könnte also auch einfach *2 bzw /2 (oder 4, 8, usw.) schreiben. Ein Beispiel, bei dem Schieben sinnvoller ist als Multiplizieren:

unsigned long l = 123456;

for( int b = 0; b <= 31; b++ ) {

  if( l & ( 1 << b ) ) {

    printf( "Bit %d ist gesetzt\n", b );

  }

}

[/CODE]




Wenn man nicht mit Schieben arbeitet, wird das Ausrechnen der Zweierpotenz schwieriger, weil man in einer Schleife multiplizieren muss:



[CODE]

unsigned long l = 123456;

for( int b = 0; b <= 31; b++ ) {

  unsigned long zweierpotenz = 1;

  for( int i = 0; i < b; i++ ) {

    zweierpotenz *= 2;

  }

  if( l & zweierpotenz ) {

    printf( "Bit %d ist gesetzt\n", b );

  }

}

Alternativ könnte man auch eine Potenzfunktion aus einer mathematischen Bibliothek einbinden. Das wäre aber unter der Haube auch nicht besser als die Multiplikationsschleife.

[nic_power]

Hallo,

hast ja recht, wir haben uns ein bisschen "verquatscht". Aber ein paar Anmerkungen seien noch gestattet. In C arbeiten die Shift-Operationen ausschließlich mit Integerzahlen (int, char, long, etc),

float oder doubles koennen nicht geshiftet werden. Fuer Fließkommazahlen gibt es die Funktionen aus der Mathematikbibliothek (pow). Man sollte also nicht versuchen, Integer Shifts ueber Fließkommafunktionen zu "simulieren" oder vice versa. Auf Grund der verschiedenen internen Darstellungsformate und Wertbereiche von integers und floats ergeben sich unerwuenschte, nicht vorhersagbare Nebeneffekte.

Nic

[Crush]

Vielleicht noch als Ergänzung etwas anderes.

Man kann in C Bitfelder definieren. Diese Bitfelder haben als Grenze allerdings die systemabhängige Größe eines Int. Spricht man diese Bitfelder dann an, wird vom Compiler der Startbereich des Bitfelds nach rechts bis ins Bit 0 geschoben und die Bitfeld-fremden Bits mit einem AND ausgeblendet. So kann man zwar effizienter mit dem Speicher umgehen, allerdings unter Performance-Verlust. Noch mehr abgebremst wird man bei schreibendem Zugriff auf das Feld, da hier natürlich nach dem 1. Vorgang die Bits wieder nach links an die Orginalposition geshiftet wird und der Restliche Inhalt reingeORT wird. Diese ganze Bitpfriemelei läuft allerdings für den Programmierer "versteckt" im Hintergrund ab.

Sollte man tatsächlich einmal das Shiften zum Ausmulitplizieren von 2hochx verwenden, dann darf man nicht vergessen, daß das Ganze in C vorzeichenlos abläuft. Der Geschwindigkeitsvorteil ist allerdings im Gegenzug wesentlich schneller als der Prozessorinterne Multiplikationsbefehl und mehr als ein Turbo im Vergleich zur FPU (die ja erstmal die Zahl zum 80-Bit-IEEE-float konvertieren muß, dann rechnen und dann wieder zurückkonvertieren).

Man ist sogar immer noch schneller, wenn man Kombinationen davon verwendet um auch beispielsweise eine Zahl * 20 zu berechnen.

unsigned int v = 123;

v = (v<<2) + (v<<4); // v = v*4 + v*16

und genau dasselbe wäre natürlich:

v <<= 2; // v = v*4

v += v<<2; // v = v + v*4

Das ist allerdings der Leserlichkeit nicht mehr dienlich.

[nic_power]

Original geschrieben von Crush

Vielleicht noch als Ergänzung etwas anderes.

Man kann in C Bitfelder definieren. Diese Bitfelder haben als Grenze allerdings die systemabhängige Größe eines Int. Spricht man diese Bitfelder dann an, wird vom Compiler der Startbereich des Bitfelds nach rechts bis ins Bit 0 geschoben und die Bitfeld-fremden Bits mit einem AND ausgeblendet. So kann man zwar effizienter mit dem Speicher umgehen, allerdings unter Performance-Verlust. Noch mehr abgebremst wird man bei schreibendem Zugriff auf das Feld, da hier natürlich nach dem 1. Vorgang die Bits wieder nach links an die Orginalposition geshiftet wird und der Restliche Inhalt reingeORT wird. Diese ganze Bitpfriemelei läuft allerdings für den Programmierer "versteckt" im Hintergrund ab.

Das haengt aber sehr stark von der Prozessorarchitektur ab. Kein Compiler auf einer HPPA-Architektur wuerde den von Dir oben beschriebenen Code erzeugen, da es fuer Bitfeldmanipulationen eigene Assembler-Instruktionen gibt. Diese erlauben es, bestimmte Bereiche von Registern direkt zu lesen und zu schreiben, ohne dass zusaetzliche Operationen (shift, or, and) durchgefuehrt werden muessen.

Eigentlich sollte man es dem Compiler ueberlassen die optimale Code-Sequenz auszuwaehlen, da dieser die CPU meist besser kennt als der Programmierer und man sonst Gefahr laeuft "suboptimalen Code" zu erzeugen. Moderne Prozessoren sind dermaßen komplex geworden, dass man hoellisch aufpassen muss, um nicht "handoptimierten" Code zu erzeugen, der die CPU ausbremst (Multiplikationen mit kleinen Integerzahlen sind da ein schoenes Beispiel). Aber vielleicht sollten wir doch besser einen eigenen Thread aufmachen, um nicht allzusehr offtopic zu werden (fragt sich nur, in welches Forum der passen wuerde).

Nic

[Crush]

Stimmt schon ... ich bin auch von X86-Systemen ausgegangen. Motorola unterstützt Bitfelder auch von Haus aus. Um das ganze nicht ins uferlose abgleiten zu lassen mach ich hier deshalb Schluß mit dem Thema in der Hoffnung die herkömmliche Frage halbwegs beantwortet zu haben.