Arithmetische Verschiebung

tomtom

tomtom

ist Papa²
21 April 2006
16.116
657
Hallo ihr da draußen,

habe mich soeben mit der arithmetische Verschiebung beschäftigt. Die Funktionalität habe ich verstanden, aber mir will einfach nichts einfallen, wofür man das gebrauchen könnte.

Hat von euch schon mal einer damit gearbeitet und/oder kann mir kurz erläutern wofür das gut ist?

Danke!
 
Ein Bit-Shift ist schneller, da er in Hardware praktisch geschenkt is.

Anwendung hab ich ein Beispiel, aus den guten alten DOS-Zeiten.
PHP: 
void set_pixel(int x, int y, unsigned char color)
{
  unsigned char far* screen_buffer = (unsigned char far*)0xA0000000l;

  screen_buffer[y*320 + x] = color;
}
Es wird ein Pixel gesetzt. Gezählt wird von der Adresse A000:0000h pixelweise. Im Modus 320x200 muss ich also y mit 320 multiplizieren und x addieren. Der Code ist wie oben.

Jetzt ein bisschen rechnen:
y * 320 + x =
y * (256+64) + x =
(y * 256) + (y * 64) + x =
(y * 2[sup]8[/sup]) + (y * 2[sup]6[/sup]) + x =
(y << 8) + (y << 6) + x
​
PHP: 
void set_pixel(int x, int y, unsigned char color)
{
  unsigned char far* screen_buffer = (unsigned char far*)0xA0000000l;

  screen_buffer[(y<<8) + (y<<6) + x] = color;
}
ist also äquivalenter Code. ...nur es ist locker 20x schneller ;)


Das nur als ein Beispiel.

Immer, wenn du mit Zweierpotenzen multipliziert oder dividierst, kannst (/musst) du den Shift verwenden.

Andere Sache, die mir einfällt: Kleine Mikroprozessoren beherrschen keine Multiplikation (und Division schon gar nicht). Mit Shift-Befehlen kann man trotzdem im Notfall eine derartige Aufgabe lösen, ohne gleich in ner Schleife zu addieren :ugly:
 
Danke für deine Antwort. Nach ein wenig Rumspielerei und gegoogle bin ich auf die gleiche "Lösung" gekommen.

Das Argument mit der Schnelligkeit ist mir dabei auch unter die Augen gekommen, nur kann ich dem nicht viel Abringen, da der Unterschied kaum messbar sein sollte. ;)

Die Sache mit den Mikroprozessoren ist natürlich eine andere. ;)

Jetzt noch zu meiner anderen Frage: Nutzt du den Bit-Shifter?
 
tomtom schrieb:
Das Argument mit der Schnelligkeit ist mir dabei auch unter die Augen gekommen, nur kann ich dem nicht viel Abringen, da der Unterschied kaum messbar sein sollte. ;)
Zum Vergrößern anklicken....
Wie kommst du da drauf ? :hö:
tomtom schrieb:
Jetzt noch zu meiner anderen Frage: Nutzt du den Bit-Shifter?
Zum Vergrößern anklicken....
Ich programmiere zu 99% PHP und da brauch ich einen Bit-Shift alle Schaltjahr einmal, wenn ich mal wirklich was an Bitmasken rummach.

Wer z.B. C (allgemein: hardware-näher) programmiert, dürfte mit Bit-Shifts schon häufiger zu tun haben.

Ich hab grade eben mal getestet:
PHP: 
<?php

$s = microtime(true);

for($i = 1; $i < 1000000; $i++)
  $foo = 3141592654 * 1024;
  //$foo = 3141592654 << 10;
  
$e = microtime(true);

echo number_format($e-$s, 6, ',', '.') . " s";

?>
Die Multiplikation dauert im Schnitt 0,342368 s, der Bit-Shift 0,400205 s; bei PHP is also eher das Gegenteil der Fall 8O

Das ganze nun in C:
PHP: 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void main( void )
{
   clock_t s, e;
   long foo;
          
   s = clock();
     
   for(long i = 0; i < 1000000000; i++)
       foo = 314159 * 1024;
       //foo = 314159 << 10;

   e = clock();
   double duration = (double)(e - s) / CLOCKS_PER_SEC;
   printf("%2.3f s", duration);
}
Liegen beide auch bei so etwa 7,3 Sekunden. Verblüfft mich ehrlich gesagt, obwohl ich alle Optimierungen abgestellt hab.

Auf meinem Linux mit
Code: 
[FONT=Lucida Console]thehacker@kubuntu:~/foo$ gcc -O0 -S -o foo.s foo.c[/FONT]
krieg ich die Antwort:
Code: 
[FONT=Fixedsys]...
.L3:
        movl   $321698816, -16(%ebp)
        addl   $1, -12(%ebp)
...[/FONT]
Das dürfte wohl auf meinem Windows-Rechner für die gleichen Werte verantwortlich sein.

Die beiden Konstanten in Variablen geändert
PHP: 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main( void )
{
   clock_t s, e;
   long foo;
   long i, a, b;

   a = 314159;
   b = 1024;
   // b = 10;
          
   s = clock();
     
   for(long i = 0; i < 1000000000; i++)
       foo = a * b;
       //foo = a << b;

   e = clock();
   double duration = (double)(e - s) / CLOCKS_PER_SEC;
   printf("%2.3f s\n", duration);
   return 0;
}
, führt zu folgenden Assemblierungen
Code: 
[FONT=Fixedsys]...
.L3:
        movl   -16(%ebp), %eax
[/FONT][FONT=Fixedsys]        imull  -12(%ebp), %eax[/FONT]
[FONT=Fixedsys]        movl   %eax, -24(%ebp)[/FONT]
[FONT=Fixedsys]        addl   $1, -20(%ebp)
...[/FONT]
und
Code: 
[FONT=Fixedsys]...
.L3:
         movl   -12(%ebp), %ecx
         movl   -16(%ebp), %eax
         sall   %cl, %eax
         movl   %eax, -24(%ebp)
         addl   $1, -20(%ebp)
...[/FONT]
, also den gewünschten Operationen.
Die Laufzeiten hierbei: 4,330 s für die imull-Operation, 4,810 s für den sall.

.... ich checks ned 8O :hö: :hö:
 
Messung mit Assembler bei 2^64 Schleifendurchläufen:

Mit MUL: 19,063 s
Mit SHL: 15,640 s

Mit Bit-Shift ist es hier ca. 3,4 s schneller.

Code: 
	INVOKE GetTickCount
		MOV A1, EAX
		
		MOV EDX, 0ffffffffh
		asd:
		MOV EAX, 0ffffffh
		XOR ECX, ECX
		;MOV EBX, 1024
		;MUL EBX
		MOV ECX, 10
		SHL EAX, CL
		DEC EDX
		CMP EDX, 0
		JE asd2
		jmp asd
		
		asd2:
		INVOKE GetTickCount
		MOV A2, EAX

Ich sollte den Test mal auf meinem alten 90Mhz PC durchführen :mrgreen:

Wobei ich Bit Shifts kaum benutze.
 
theHacker schrieb:
Wie kommst du da drauf ? :hö:
Zum Vergrößern anklicken....

Deine unten (bzw. oben) stehende Beweisführung zeigt doch, dass es für den Menschen kaum einen Unterschied macht.


Auf jeden Fall danke ich euch beiden für eure Tests. :yes: Nur bin ich der Meinung, dass ich den shift wohl trotzdem nie einsetzen werde.
 
Also ich benutze die Bitverschiebungen recht gerne, vorzugsweise bei Divisionen und an sonstigen Flaschenhälsen. Wenn sich bestimmte Variablen nur im Bereich von Zweierpotenzen bewegen, finde ich Bitshifts z.T. sogar übersichtlicher, als Multiplikationen. Aber ich arbeite ja auch gerne auf Bit-Ebene ...


theHacker schrieb:
Andere Sache, die mir einfällt: Kleine Mikroprozessoren beherrschen keine Multiplikation (und Division schon gar nicht). Mit Shift-Befehlen kann man trotzdem im Notfall eine derartige Aufgabe lösen, ohne gleich in ner Schleife zu addieren :ugly:
Zum Vergrößern anklicken....
Na ja, oft können die Dinger sogar dividieren, sind dabei aber so grotten langsam, dass man einfach tut, als könnten sie es nicht.

Digitale Signalprozessoren verwenden oft ein Festkommaformat, das sich auf einen Wertebereich zwischen -1.0 und +1.0 beschränkt.

Wenn du auf so'nem DSP z.B. einen Wert 0.2 hast und diesen mit einem Faktor von 3 multiplizieren musst, bekommst du Probleme, da du einen Wert von 3 nicht mehr darstellen kannst.

0.60 = 0.20 * 3.00

Wenn du die 3 aber um 2 Bit herunterschiebst, bekommst du einen darstellbaren Faktor von 0.75. Multiplizierst du nun mit diesem Faktor und schiebst das Produkt dann wieder um 2 Bit herauf, erhältst du trotzdem das gewünschte Ergebniss.

0.60 = (0.20 * 0.75) << 2


MfG
Sven
 
In manchen Softwareprojekten werden auch irgendwelche proprietären Protokolle verarbeitet. Da hat manchmal jedes bit oder auch einzelne Bit-Gruppen innerhalb einer Nachricht eine besondere Bedeutung. Auch da kommt mitunter ein Bit-Shift vor.

Wenn man das 8te Bit setzen will ist ein

x |= 1 << 8;

einfach übersichtlicher als ein x |= 256.
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben