Bitverschiebung
-
Hey Leute ich möchte mich mal informieren.
In der Schule lerne ich C programmieren, auch hobbymäßig beschäftige ich mich mit ca. 8 verschiedenen Programmiersprachen (darunter auch Auszeichnungssprachen) und immer wieder werde ich mit dem Kapitel "Bitverschiebung" konfrontiert (natürlich nicht in allen Sprachen).
Nun zu meiner Frage: Was bring sich die Bitverschiebung genau? bzw. könnt ihr mir Beispiele nennen wo die Bitverschiebung in großen Programmen angewendet wird und für was. Oder für was diese generell verwendet wird.
Klar zum kippen, verschieben, verunden etc. von Bits, aber warum?Ist reine Neugierde
Mit freundlichen Grüßen
-
Theoretisch benötigen tut man das nicht, gibt ja die Multiplikation. Die Operation ist allerdings wesentlich schneller auf den mir bekannten CPUs. Wann man so etwas in "echtem" Code sieht? Bei binären Protokollen, die die Bits genau an irgendeiner Stelle haben wollen vielleicht, ganz sicher bei einigen Verschlüsselungs-/Hashalgorithmen. Ansonsten wohl eher selten.
-
Erst mal danke für die schnelle und informative Antwort.
Dass heißt eine Berechnung geht als Bitoperation, keine Ahnung wie ich das nennen soll, schneller als die Berechnung ausgeschrieben mit ganz normalen Dezimalzahlen und mit "+", "-" etc. sry ist ein bisschen eigenartig ausgedrückt.
Mit binären Protokollen meinst du Dateien (Textdateien etc.) wo du den Zeiger an eine bestimmte Stelle setzen kannst?
-
Nur mal so nebenbei, folgendes Programm
int main() { for(int i = 0; i < 1000000000; ++i) volatile int x = i << 1; }braucht bei mir 0.92 Sekunden.
int main() { for(int i = 0; i < 1000000000; ++i) volatile int x = i * 2; }braucht 0.56 Sekunden. (g++ 4.6.2, -O3)
-
Oha das macht ja einen mächtigen Unterschied vorallem wenn das größere und mehr Berechnungen sind. Also das war mir eigentlich nicht bewust. Da sollte ich mich mit dem Thema noch weiter beschäftigen.
Danke für das Beispiel
-
Oh ich merke gerade, ich hab mich verschaut o.O. Dann ist die Bitverschiebung ja um ein Hauseck langsamer...
-
Incocnito schrieb:
Nur mal so nebenbei, folgendes Programm
Joa, das ist in der Tat interessant. Hier mal der Code der von VS generiert wird (VS gibt ähnliche Ergebnisse):
for(int i = 0; i < 1000000000; ++i) 00E2123D xor ecx,ecx 00E2123F nop volatile int x = i << 1; 00E21240 lea eax,[ecx+ecx] 00E21243 inc ecx 00E21244 mov dword ptr [esp+30h],eax 00E21248 cmp ecx,3B9ACA00h 00E2124E jl main+20h (0E21240h)013B123D xor ecx,ecx 013B123F nop for(int i = 0; i < 1000000000; ++i) volatile int x = i * 2; 013B1240 mov dword ptr [esp+30h],ecx 013B1244 add ecx,2 013B1247 cmp ecx,77359400h 013B124D jl main+20h (013B1240h)Interessant deshalb, weil bei der * 2 Version eine Optimierung gemacht wird, die man so erstmal nicht erwarten würde. Der addiert einfach immer 2 auf i, und [hier stand Quatsch] muss deshalb nicht mehr rechnen. Komisch dass er den Trick bei der shift Version nicht rafft. Aber wie dem auch sei, einen Vergleich zwischen shift und Multiplikation hast du so nicht zustande gebracht.
-
Der durchläuft die Schleife nicht halb so oft, sondern er läuft in Zweierschritten von 0 bis 2 Milliarden statt in Einerschritten von 0 bis 1 Milliarde.
i * 2 und i << 1 sind bei vorzeichenbehafteten Integern nicht äquivalent, und ich weiß nicht, ob MSVCs Optimiser rafft, dass es im betrachteten Wertebereich trotzdem ginge. Versuch's mal mit unsigned, da könnte er das eher merken.
-
seldon schrieb:
Der durchläuft die Schleife nicht halb so oft, sondern er läuft in Zweierschritten von 0 bis 2 Milliarden statt in Einerschritten von 0 bis 1 Milliarde.
Stimmt natürlich.
seldon schrieb:
i * 2 und i << 1 sind bei vorzeichenbehafteten Integern nicht äquivalent, und ich weiß nicht, ob MSVCs Optimiser rafft, dass es im betrachteten Wertebereich trotzdem ginge. Versuch's mal mit unsigned, da könnte er das eher merken.
Nope, unsigned ändert nichts.