Bitlogische & Verschiebungsoperatoren

[hdi]

Hi,

mal ne Frage zu den bitlogischen Operatoren:

~ Komplement
& UND
| ODER
^ ODER (exklusiv)

und den Shifting-Operatoren:

<< Linksverschiebung
>> Rechtsverschiebung mit Vorzeichen
>>> Rechtsverschiebung ohne Vorzeichen

In was für Anwendungsfällen braucht man sowas? Ich hab die noch nie genutzt und wüsste auch nicht wozu?!

Danke

 

[Bierhumpen]

Gabs doch erst von ein paar Tagen: http://www.java-forum.org/java-basics-anfaenger-themen/103259-bringen-bit-operatoren.html
Boolesche Algebra ? Wikipedia

 

[ice-breaker]

z.B. für binäre Netzwerkprotokolle

 

[XHelp]

Also durch Shiften kannst du sehr effizient durch 2 teilen, bzw durch Potenzen von 2 (oder multiplizieren)

 

[Marco13]

Wofür sie oft verwendet wurden und werden (auch wenn es ... Tendenzen gibt, das i.a. nicht mehr zu tun) ist für flags:

private static final int EFFICIENT = (1<<0);
private static final int COMPACT = (1<<1);
private static final int UNREADABLE = (1<<2);

private int flags = 0;

private boolean is(int flag)
{
    return ((flags & flag) != 0);
}

private boolean set(int flag)
{
    flags |= flag;
}

void init()
{
    set(EFFICIENT);
    set(COMPACT);

    System.out.println(is(EFFICIENT)); // true
    System.out.println(is(UNREADABLE)); // false
}

Z.B. bei den Modifiern in MouseEvents und KeyEvents.


Eine interessante Zusammenfassung zu allen möglichen interessanten Dingen, die man damit machen kann, findet sich hier: Bit Twiddling Hacks

 

[Gast2]

In was für Anwendungsfällen braucht man sowas? Ich hab die noch nie genutzt und wüsste auch nicht wozu?!

solange Du reines Java mit GUI machst wirst Du das wohl auch nie verwenden müssen ... wenn Du aber Hardware programmieren willst - sei es erstmal via COM-Port mit Java - dann wirst Du es wohl eher gebrauchen dürfen ... wechselst Du komplett in den Embedded Bereich, dann wirst Du das wohl benötigen ... spätestens wenn Du direkt den Prozessor und dessen Register programmierst

Also durch Shiften kannst du sehr effizient durch 2 teilen, bzw durch Potenzen von 2 (oder multiplizieren)

das galt vor ein paar Jahren zu 100% ... inzwischen sind AMD und Intel soweit das man sich darüber keine Gedanken mehr machen muss - ich mache es zwar immer noch, aber eher aus Gewohnheit ... selbst im Embedded Bereich sind die Prozessoren inzwischen in dieser Hinsicht optimiert worden

 

[musiKk]

In der Bildbearbeitung wird das auch oft eingesetzt. In einem [c]BufferedImage[/c] mit RGB-Farben werden die drei Farben in einem int abgelegt. Um an die einzelnen Teile zu kommen, muss man binär shiften und/oder "unden".

Wofür sie oft verwendet wurden und werden (auch wenn es ... Tendenzen gibt, das i.a. nicht mehr zu tun) ist für flags:

<snip>

Z.B. bei den Modifiern in MouseEvents und KeyEvents.

Gruselig. SWT macht das ja auch so (wobei das wohl der Rückwärtskompatibilität geschuldet ist). In C# kann man das afaik komplett mit Enums abbilden, in Java leider nicht.

das galt vor ein paar Jahren zu 100% ... inzwischen sind AMD und Intel soweit das man sich darüber keine Gedanken mehr machen muss

Ist zwar Sache der Compiler- und nicht CPU-Bauer, aber ansonsten stimmts. Das ist so eine typische "Optimierung", die abgeschafft gehört. Es gibt genug Beispiele, die deutlich machen, wie gut die heutigen Compiler sind und dass so kleine Hacks die Optimierung behindern können.

 

[Gast2]

Ist zwar Sache der Compiler- und nicht CPU-Bauer,

stimmt -bin gedanklich nicht aus dem Shiften und Division durch 2 raus gekommen ... Division selber ist nicht ganz trivial ... das kostet

Es gibt genug Beispiele, die deutlich machen, wie gut die heutigen Compiler sind und dass so kleine Hacks die Optimierung behindern können.

PPC-Compileroptimierung aus dem Studium ... Multiplikation einer Zahl mit 12 ... ich mach das mal mit Java

// einfach
int result = zahl * 12;

// optimiert
int result1 = zahl << 3;  // 8-fache
int result2 = zahl << 2;  // 4-fache
int result = result1 + result 2;  // 8-fache + 4-fache = 12-fache

unterm Strich verbraucht man mehr Speicher, aber die nötigen CPU Zyklen brechen ein ... Shiften und Addieren brauchen nunmal nicht wirklich CPU-Zyklen

 

[Marco13]

Wobei man immer nicht weiß, was der JIT noch draus macht. Es gibt sicher nur wenig(st)e Fälle, wo das einen Vorteil bringt. Aber Sun macht's selbst: In Integer#getChars kommt sowas vor wie

       for (;;) { 
            q = (i * 52429) >>> (16+3);
            r = i - ((q << 3) + (q << 1));  // r = i-(q*10) ...
            buf [--charPos] = digits [r];

Sieht schon interessant aus

 

[maki]

Diese Operatoren werden zB. genutzt, um Endian Encoding hin- und her zu wandeln(big Endian/Little Endian), oder generell um zu enkodieren/dekodieren.

Performanzoptimierungen?
Ich hoffe das wid auch nachgemessen, den "mechanisches" optimieren ("hab ich im Studium so gelernt") ohne Überprüfung ist kein Optimieren, sondern Quellcode verschleiern

 

[ice-breaker]

Gruselig. SWT macht das ja auch so (wobei das wohl der Rückwärtskompatibilität geschuldet ist). In C# kann man das afaik komplett mit Enums abbilden, in Java leider nicht.

aus welchem Grunde sollte es in Java nicht auch komplett mit Enums gehen?
Enum + EnumSet

Ist zwar Sache der Compiler- und nicht CPU-Bauer, aber ansonsten stimmts. Das ist so eine typische "Optimierung", die abgeschafft gehört. Es gibt genug Beispiele, die deutlich machen, wie gut die heutigen Compiler sind und dass so kleine Hacks die Optimierung behindern können.

ähm, nen Bitshift um 1 Stelle nach rechts als Ersatz für eine Division würde ich nicht zu den Optimierungen zählen, die man lassen sollte, die Lesbarkeit ist doch kein Stück beeinträchtigt, und je nach fehlender Optimierung der VM oder Prozessorarchitektur kann es schneller sein.
(Im Gegensatz zu C - unsigned int - kann die JVM nicht generell davon ausgehen, dass die Ganzzahl immer positiv ist und somit die Division durch eine 2 mit einem Bitshift ersetzen, der Programmierer kann es aber)

unterm Strich verbraucht man mehr Speicher, aber die nötigen CPU Zyklen brechen ein ... Shiften und Addieren brauchen nunmal nicht wirklich CPU-Zyklen

willst du damit sagen deine Bitshift-Methode ist schneller oder langsamer als die arithmetische Version mit der ALU.

 

[maki]

Wenn ich mich an die Schulbank zurückerinnere, setzten ALUs doch Multiplikation mit Addition und Division mit Subtraktion um, zumindest war das damals noch so..

Das man mit Shift ops. u.U. den einen oder anderen Zyklus einsparen konnte war damals klar, aber lesbar ist anders.

IMHO gilt da die alte Regel, Optimieren nur wenn es nötig ist und gleichzeitig etwas messbares bringt.

 

[ice-breaker]

Das man mit Shift ops. u.U. den einen oder anderen Zyklus einsparen konnte war damals klar, aber lesbar ist anders.

jup die Frage ist eben nur wie es heute aussieht.
Das doofe ist ja, dass alles Material Jahrzehnte alt ist, aber die Prozessorbauer auch nicht geschlafen haben und können durch den sinkenden Fertigungsprozess mehr Bausteine auf die gleiche Fläche packen und somit weit mehr Operationen parallel ausführen.

IMHO gilt da die alte Regel, Optimieren nur wenn es nötig ist und gleichzeitig etwas messbares bringt.

natürlich, das sollte man nie vergesse

 

[maki]

jup die Frage ist eben nur wie es heute aussieht.
Das doofe ist ja, dass alles Material Jahrzehnte alt ist, aber die Prozessorbauer auch nicht geschlafen haben und können durch den sinkenden Fertigungsprozess mehr Bausteine auf die gleiche Fläche packen und somit weit mehr Operationen parallel ausführen.

Ja, damals war Duffs Device auch noch Pflichtlektüre, heute höchtens noch als Negativbeispiel *g*

 

[musiKk]

aus welchem Grunde sollte es in Java nicht auch komplett mit Enums gehen?
Enum + EnumSet

Stimmt, mit dem EnumSet geht das auch. Braucht damit eben noch eine zusätliche Klasse.

ähm, nen Bitshift um 1 Stelle nach rechts als Ersatz für eine Division würde ich nicht zu den Optimierungen zählen, die man lassen sollte, die Lesbarkeit ist doch kein Stück beeinträchtigt, und je nach fehlender Optimierung der VM oder Prozessorarchitektur kann es schneller sein.

Gut, ist wie vieles natürlich Geschmackssache. Ich bin auf jeden Fall der Meinung, dass man es kennen sollte, aber ich würde trotzdem keinen shift verwenden. Das hat für mich auch eine bestimmte Semantik: "Oha, hier geht Bit Twiddling los...". Das ist halt die halbe Sekunde beim Lesen von Quelltext, auf die es mir mehr ankommt als die eventuell gar nicht mal vorhandene Mikrosekunde, die ich zur Laufzeit spare.

 

[Ark]

In der Bildbearbeitung wird das auch oft eingesetzt. In einem [c]BufferedImage[/c] mit RGB-Farben werden die drei Farben in einem int abgelegt. Um an die einzelnen Teile zu kommen, muss man binär shiften und/oder "unden".

Gerade in solchen Fällen bin ich sogar der Meinung, dass Bitshifts etc. den Code nicht nur schneller, sondern vor allem auch lesbarer machen. Ein Bitshift sagt nun einmal "diese Zahl muss daunddort hoch", und ein UND sagt "mich interessiert nur derundder der Teil". Eine Multiplikation mit 65536 oder Modulo 256 würden weitaus weniger lesbar aussehen - denke ich.

Noch eine Bemerkung zur Haltung "Bitshifts sind nicht nötig, da kann der Compiler was optimieren": Er kann nur vielleicht, aber eigentlich muss er gar nichts. Und für die Optimierung braucht er auch Zeit. Außerdem gibt es noch etwas zu beachten: Das Pipelining in der CPU kann nur dann gut funktionieren, wenn die entsprechenden Ressourcen auch frei sind. Nun ist es gut möglich, dass z.B. durch eine Multiplikation das Addierwerk besetzt wird, das der nächste Befehl hätte gebrauchen können. Weil es aber eben besetzt ist, muss der Befehl warten. (Out-of-order-execution ist auch nur begrenzt möglich, und die Optimierung dahingehend kostet auch Zeit.) Möglicherweise könnte ein Prozessor aber zugleich einen Bitshift ausführen. Und selbst wenn das nicht möglich ist: eine Multiplikation/Division kostet nun einmal viel Zeit, und wenn der Befehl nicht vereinfacht/wegoptimiert werden kann, haut das schon rein.

Als es um die Berechnung von Fraktalen ging, war bei mir ein Fall, bei dem ich einfach nur das Ergebnis einer Multiplikation gespeichert habe, um eine zweite (und nur diese zweite) Berechnung zu verhindern. Obwohl diese Multiplikation als fast nichts im Vergleich zu den anderen Berechnungen erschien, lohnte sich das Zwischenspeichern deutlich. Man sollte sich also nicht darauf verlassen, dass ein Compiler wirklich alles optimiert, was man optimieren könnte.

Ark

 

[musiKk]

Eine Multiplikation mit 65536 oder Modulo 256 würden weitaus weniger lesbar aussehen - denke ich.

Die Alternative zu den Binäroperationen wäre ja eher eine entsprechende Methode zu verwenden (die selbst natürlich auch wieder auf Binäroperationen setzt, aber ein großer Teil aller Entwickler schaut sich sicher nie auch mal die Implementierung dessen, was er benutzt, an) und das wäre bei solchen Dingen wirklich ein Performancekiller.

Noch eine Bemerkung zur Haltung "Bitshifts sind nicht nötig, da kann der Compiler was optimieren": Er kann nur vielleicht, aber eigentlich muss er gar nichts. Und für die Optimierung braucht er auch Zeit.

Die soll er auch bekommen. Zur Laufzeit ist das ja egal.

Man sollte sich also nicht darauf verlassen, dass ein Compiler wirklich alles optimiert, was man optimieren könnte.

Das stimmt schon. Und Dein Beispiel ist ja auch genau so, wie es immer gepredigt wird: Erst lesbar programmieren und dann die Schwachstellen finden und gezielt optimieren. Dennoch vermute ich einfach, dass das >95% aller Programmierer nicht können und durch Halbwissen unleserlichen und evtl. auch ineffizienten Code produzieren. Vor allem in Verbindung mit der ersten Regel der Optimierung.
Ich bin das auch im Zusammenhang mit Fraktalen durchgegangen: Erst lesbar mit einer Klasse für komplexe Zahlen, später nur noch inline zwei [c]double[/c]-Variablen für Real- und Imaginärteil. Die Performancesteigerung war natürlich beachtlich.

 

[ice-breaker]

Ich bin das auch im Zusammenhang mit Fraktalen durchgegangen: Erst lesbar mit einer Klasse für komplexe Zahlen, später nur noch inline zwei [c]double[/c]-Variablen für Real- und Imaginärteil. Die Performancesteigerung war natürlich beachtlich.

Für so etwas wäre es schön die JVM anweisen zu können eine Klasse wegzuoptimieren, sollte dies nicht klappen, wird es geloggt, dann muss man eben die Klasse so umbauen, dass es möglich ist.

 

[Marco13]

Hm. So einfach ist das nicht. Dem, was in C einem "inline" entspricht, steht erstmal die Polymorphie im Weg. Es wäre vielleicht theoretisch möglich, wenn man eine Klasse als final deklariert, und sie nur Methoden von anderen finalen Klassen aufruft....

 

[musiKk]

Also um beim Beispiel komplexe Zahlen zu bleiben: Wenn die Klasse final und immutable ist, dann könnte man da sicher etwas reißen. Die verschiedenen Methoden zum Addieren, etc. könnte man dann praktisch "inlinen"... vielleicht.

 

[XHelp]

Was die Optimierung durch den Compiler angeht (common subexpression elimination um genau zu sein):
Das Geschehen liegt schon eine ganze Weile zurück. Es ging darum verschiedene Compiler für Fortran zu testen. Das Programm stellte eine komplizierte Berechnung an und das wars. Da am Anfang keine Ausgabe existierte, war ein Compiler gerissen und hat das Programm zum

exit(0)

optimiert. Nach dem eine Ausgabe eingebaut war, glänzte ein anderer Compiler durch Raffinesse: er kompilierte 3 Stunden lang und der optimierte Code war:

printf(endergebniss)

.
Natürlich muss man die Zeit berücksichtigen, aber worauf ich hinaus will: der Compiler tut nicht immer das, was man von ihm erwartet.