Bit Operationen in der Praxis

[ARadauer]

... wer von euch verwendet eigentlich häufig Operatoren wie &, |, <<, >> usw..
ich weiß was das genau macht aber wozu? Was sind konkrete Anwenungsbereiche wo es sinn macht soetwas einzusetzen?

 

[ARadauer]

zb sowas aus der HashMap

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

wtf? ich weiß was es mit den zahlen macht, aber den sinn versteh ich nicht ganz...

 

[SlaterB]

ein HashCode ist eine lange Zahl, potentiell 498357934089 (übertrieben)

wenn man aber nur 1000 Einträge hat, dann muss man all die langen HashCodes auf die 1000 verfügbaren Plätze verteilen,
da man über die Verteilung nichts weiß ist es das einfachste, die letzten 3 Ziffern zu nehmen, hash % 1000,
hier also Array-Index 089

Bitmethoden machen das gleiche auf Bitebene

(ich selber verwende sowas quasi nie, wahrscheinlich übersehe ich die wenigen sinnvollen Einsatzmöglichkeiten )

 

[ARadauer]

warum wird dann nicht gleich % genommen? performance?

 

[thE_29]

Ich verwende die Dinger paar mal um zwischen C und Java das Little/BigEndian Problem umzugehen (da muss man das umdrehen) oder um abzufragen ob der XXXte Bit gesetzt ist.

Oder auch fürs BCD Verfahren: BCD-Code ? Wikipedia

 

[Geeeee]

Wahrscheinlich aus Performancegründen. Ein Modulo müsste ja auch durch die Division geschickt werden.
Zum Thema allgemein: In Java nutze ich das sehr selten. Zur Zeit gerade bei unsigned <> signed int Transformation aus einem C# ByteStream (oder wie das auch immer da heißt). Aber auch nur, weil ich keine andere Lösung gefunden hab.
In meiner C++-Zeit (hach...damals ) hab ich es öfters benutzt, vor allem bitshifting, um den ekelhaften Divisionen aus dem Weg zu gehen (ging damals um Simulationen und ich wollte sowenig negativen Einfluß auf die Ausführzeit auswirken wie möglich).

 

[Marco13]

Ja, vermutlich ist das der Hauptgrund. % ist deutlich teurer als &. Ganz allgemein kann man sagen, dass die Operationen + und -, aber insbesondere *, / und % eben (u.U. deutlich effizienter) abgebildet werden können, indem man sie durch Bit-Operationen nachbaut - was natürlich nur funktioniert, wenn die Operanden bestimmte Zweierpotenzen sind. Zusätzlich braucht man natürlich für die Berechnung der Zweierpotenzen selbst die Shift-Operatoren - das würde man ja nicht mit Math.pow machen.

Hab' da vor einiger Zeit eine hübsche Übersichtsseite mit Bit Twiddling Hacks gefunden - da sieht man was man damit alles machen kann. Dabei sind auch solche Klassiker: Bei OpenGL müssen Texturgrößen manchmal Zweierpotenzen sein - wie kann man feststellen, ob eine Zahl eine Zweierpotenz ist?
if ((a & (a-1)) == 0) ja();

Bei solchen Methoden wie "Integer.toString(...)" wird in der Methode "getChars(...)" z.B. auch sowas gemacht:
r = i - ((q << 3) + (q << 1)); // r = i-(q*10) ...
Und ich vermute mal, dass man sich solche Krämpfe nicht antun würde, wenn es sich in bezug auf die Performance nicht lohnen würde.

Dazu kommt natürlich noch das nächstliegende: Bits sind die kompakteste Form, viele boolsche Werte auf einmal zu speichern - z.B. die Modifiers bei MouseEvents (SHIFT_DOWN, CONTROL_DOWN usw.) die mit |= kombiniert und mit (a&X)!=0 abgefragt werden können.

 

[SlaterB]

zum einen Performance,
zum anderen, recht eng verbunden, arbeiten die Operatoren auf natürliche Weise im 2er-Systen,

jedes Mal wenn in der Map das Array vergrößert wird steigt es um 2 oder ein Vielfaches davon,
2^7 kann ma kaum als Zahl hinschreiben, in diesem Fall wenger relevant da man ja array.length vorliegen hat,
allgemein gibts da aber Vorteile, auch per Shift: 1 << 7 == 2^7 oder so, +-1 im Exponent..

das & im obigen Beispiel ist übrigends nicht immer dasselbe wie die %-Rechnung, sonst könnte man ja immer & rechnen,
nur bei Zweierpotenzen kommt die Arithmetik hin

public class Test
{
    public static void main(String[] args)
        throws Exception
    {
        int x = 4311;
        int y = 512;
        System.out.println(x % y);
        System.out.println(x & (y-1));

        y = 200;
        System.out.println(x % y);
        System.out.println(x & (y-1));

    }

}

215
215
111
199

 

[ice-breaker]

1 << 7 == 2^7 oder so

Ein Shift nach links (<<) entspricht er Multiplikation um 2, ein Shift nach rechts (>>) entspricht er einer Division durch 2.

Inwieweit das sich nun positiv auf die Performance auswirkt ist fraglich, denn der Java-Compiler könnte ganz einfach sehen, dass es eine Multiplikation um 2 ist und von selbst eine Bit-Operation daraus machen.

 

[SlaterB]

beim Shift vs *2 mag es keinen Performancevorteil geben, da ist es dann aber zumindest eine Handling-Frage,
Math.pow(2,7) oder 2 * 2 * 2 * 2 * 2 * 2 * 2 will man eher nicht schreiben, was beides dann doch bestimmt auch langsamer wäre als genau EIN Shift

 

[Marco13]

Einem ersten Test nach macht er das wohl nicht unbedingt

class BitTest
{
	public static void foo()
	{
	    int x = 7;
	    int y = x * 64;
	    int z = x << 5;
	}
}

->

public static void foo();
  Code:
   0:   bipush  7
   2:   istore_0
   3:   iload_0
   4:   bipush  64
   6:   imul
   7:   istore_1
   8:   iload_0
   9:   iconst_5
   10:  ishl
   11:  istore_2
   12:  return
}

Aber vielleicht macht er es, wenn der JIT mal drüberläuft.

 

[Ark]

Ich bin voll Fan von Bitoperationen. <3 Sie sind schnell und die dazugehörigen Datenstrukturen benötigen wenig Platz. Besser kann es doch gar nicht kommen. Deswegen bereite ich Datenstrukturen gerne so auf, dass auch Bitoperationen genutzt werden können.

Auch ein schöner Anwendungsfall sind (trivial) binäre Schalter, von denen man mal eben 32 Stück in einem int bewegen kann - Synchronisierungsprobleme bei Multithreading ausgeschlossen!

Jaja, Bits haben schon was für sich ... *schwärm*

Ark

 

[musiKk]

Ich verzichte weitesgehend auf Bitoperationen. Nicht, weil sie mir zu hoch sind, sondern weil ich denke, dass komplizierte Konstrukte für andere (und nach einer Weile für einen selbst) relativ schwer durchschaubar sein können. Wenn es wirklich auf Performance ankommt, dann ist natürlich (fast) jedes Mittel recht. Ansonsten gilt aber wie immer "premature optimization is...".
Wenn ich es mir aber überlege, dann habe ich auch bisher keine echten Verwendungszwecke für Bitoperationen gehabt.

beim Shift vs *2 mag es keinen Performancevorteil geben, da ist es dann aber zumindest eine Handling-Frage,
Math.pow(2,7) oder 2 * 2 * 2 * 2 * 2 * 2 * 2 will man eher nicht schreiben, was beides dann doch bestimmt auch langsamer wäre als genau EIN Shift

Da Zahlen im Quelltext eh nur als benannte Konstanten vorkommen sollten, fällt die Performancefrage eh flach, da die Werte genau einmal vom Compiler bestimmt werden. Dennoch ist sowas auch ein idealer Kandidat für einen Shift. Die Zweierpotenzen bis 10 sollte man als Programmierer imho auch kennen. Außerdem denke ich mal, dass man, wenn man mit solchen Zahlen zu tun hat, sich so weit "unten" in den Abstraktionsschichten befindet, dass man solches Wissen voraussetzen kann.

 

[Ark]

Ich verzichte weitesgehend auf Bitoperationen. Nicht, weil sie mir zu hoch sind, sondern weil ich denke, dass komplizierte Konstrukte für andere (und nach einer Weile für einen selbst) relativ schwer durchschaubar sein können.

Unabhängig davon, wie oft man mit diesen Operationen zu tun hat, sollte man sie trotzdem im Schlaf beherrschen. Es sollte genauso in Fleisch und Blut übergehen wie Addition und Subtraktion schon in der Grundschule, das Einmaleins oder eben (in unserem Fach) der Umgang mit Hexadezimal- und Binärzahlen.

Was sagen die anderen? ^^

Ark

 

[musiKk]

Natürlich. Diese Dinge gehören zu den erwähnten Zweierpotenzen: Informatikerallgemeinbildung.

 

[Landei]

Unverzichtbar (auch wenn man manchmal erst nach Java übersetzen muss):

Bit Twiddling Hacks

 

[Ark]

Ich würde sagen, deine Antwort kommt gut drei Tage zu spät ...

Ark

 

[Marco13]

Hab' da vor einiger Zeit eine hübsche Übersichtsseite mit Bit Twiddling Hacks gefunden - da sieht man was man damit alles machen kann.

Redundanz ist redundant....

 

[Gast2]

Eventuell um mehrere boolean auf einmal in einer schleife zu kontrollieren/auszuwerten

Bsp:

       for (MyObject o : list) {
           
             b1|= myObject.isB1();
             b2|= myObject.isB2();
usw.
         }

Bei SWT kommt man in berührung sonst waren sie immer kurz und schön umsowas wie styles(wie bei SWT) zu setzen, aber seit es enums gibt find ich die schöner.