Frage zu Bit Operatoren in der Programmierung

[DennisXX]

Hi Folks !

Ich habe mich schon des öfteren gefragt, wofür man in der Programmierung (egal um welche konkrete Programmiersprache es geht), sogenannte Bit Operatoren benötigt und was man damit machen kann!? Mir sind diese Dinge in fast jeder Programmiersprachenereferenz übder den Weg gelaufen, aber so richtig habe ich davon noch nie den Sinn verstanden.

Ist das eher ein nettes Zusatzfeature in der Programmierung, oder kann und muss man diese Sache ernsthaft gebrauchen?

Greetz
Dennis

 

[Fu3L]

Wenn sie dir in jeder Sprache über den Weg laufen, werden die wohl ihre Berechtigung haben.

Mit denen kannst du bestimmte Operationen eben sehr schnell ausführen, weil diese bit-operatoren sehr "maschinennah sind"

Natürlich wäre es bei heutigen Prozessoren Quatsch für jedes x*2 zu schreiben x << 1, weil das zu verstehen zu umständlich ist, wenn jemand deinen Code liest. Aber sowas wie folgender Code kann bei millionenfachem Aufruf schon einen Effekt haben:

//Entweder so:
if(x%2==0) {

//oder so, selbst mit Methodenaufruf viel schneller (vllt inline?)
if(isEven(x)) {

//Mit dieser Methode:
public boolean isEven(long x) {
  return (x >> 1) << 1 == x;
}

Edit: Habs nochmal getestet: Folgendes, ohne aufwändige Modulo-Operation, ist auch nur ganz minimal schneller, nichts im Vergleich zu den Bit-Operatoren.

public boolean isEven(long x) {
  return (x/2)*2 == x;
}

 

[DennisXX]

Hi Folks !

Also wenn ich ehrlich bin Fu3L habe ich ein Codebeispiel noch nicht so ganz verstanden. Würdest du dich evtl. dazu bereiterklären, dass etwas ausführlicher zu beschreiben?

Hab vielen Dank !

Greetz
Dennis

 

[Fu3L]

Ich habe dort zwei Möglichkeiten dargestellt, um zu testen, ob eine Zahl gerade ist (englisch: even ).
Die eine wie man sie oft findet und die fast jeder sofort versteht mit der Modulo Operation. Bei der anderen Möglichkeit habe ich absichtlich noch einen Methodenaufruf eingefügt, weil der das Verständnis fördern soll, da es bei bit-operatoren nicht sofort für jeden ersichtlich ist, was dort passiert.
Was die einzelnen bit-operatoren so anstellen, kannst du in deinem Programmierbuch selber nachlesen oder Googlen

 

[Cola_Colin]

Der Geschwindigkeitsaspekt ist imho nur recht selten von Bedeutung.
Wichtig werden diese Operatoren, wenn du irgendwelche Daten auf bit Ebene manipulieren willst.
Man kann über sie gezielt einzelne Bits einer Zahl verändern, oder aber auch solche Umwandlungen machen:

    private static byte[] intToBytes(int i) {
        byte[] dest = new byte[4];
        dest[3] = (byte) (i >>> 24);
        dest[2] = (byte) (i >>> 16);
        dest[1] = (byte) (i >>> 8);
        dest[0] = (byte) (i);

        return dest;
    }

    private static int bytesToInt(byte[] b) {
        int result = 0;

        result |= (0xFF & b[3]) << 24;
        result |= (0xFF & b[2]) << 16;
        result |= (0xFF & b[1]) << 8;
        result |= (0xFF & b[0]);

        return result;   
    }

Das ist dann hilfreich, wenn man irgendwo einen Integer übertragen will, aber eben nur byte Arrays übertragen werden können.

 

[Marco13]

Ja, es gibt viele Bereiche wo man z.B. int in byte zerlegen muss oder bytes zu ints zusammensetzen. Das von Cola_Colin beschriebene muss man auch oft in der Bildverarbeitung machen, wo eine Farbe als RGBA in einem int gespeichert ist, und man den Rot, Grün, Blau und Alpha-Teil als einzlene bytes rauspfriemeln muss.
Was ganz anderes ist, dass es praktisch sein kann, z.B. in einem long die gleiche Information unterbringen zu können, wie in 64 booleans: Man kann Flags (also quasi-boolean-Werte) damit sehr kompakt speichern.
Das Modulo würde ich zwar doch eher mit [c]if ((x&1)==0)[/c] machen. Aber einen Eindruck, was noch alles geht, bekommt man auf dieser Seite: Bit Twiddling Hacks

 

[Empire Phoenix]

Stelll dir for du willst schnell wissen ob zwei objecte collidiren können (physic engine, jbullet) du hast eienn int mit seinen x stellen,
nun machst du bei beiden bitmasken durch bit operationen

0101010101001 ein Haus oder whatever
0100000000000 ein geschoss

jetzt ne und operation drauf:
0100000000000
ergebnis != 0
-> collisionsevente sollen ausgeführt werden.

Vorteil :
Im gegensatz zu dutzenden if's oder vergelichbarer logic kann ich mithilfe einer einzigen operation und einem if, statt ein if pro stelle das ganze überprüfen.

 

[Landei]

Ein schönes Beispiel ist die Klasse [c]java.util.BitSet[/c], mit der man alle möglichen Dinge - vom Primzahlsieb bis zum Bloom-Filter - implementieren kann. Theoretisch hätte man eine ähnliche Funktionalität mit einer [c]List<Boolean>[/c], aber vieeel langsamer und umständlicher. Der Source-Code von BitSet ist voller Bit-Operationen. Ähnliches gilt auch für die Klassen BigInteger und BigDecimal.

 

[Fu3L]

Dann will ich auch nochmal ein Beispiel posten, wo es einfach nur praktisch ist, die bit-Operatoren zu nutzen:
GPU Gems 3: Chapter 1. Generating Complex Procedural Terrains Using the GPU | NVIDIA Developer Zone
In Abschnitt 1.2 soll man für jede Ecke des Quaders eine Stelle der Binärzahl auf 1 oder 0 setzen, je nach Ergebnis. Die resultierende Zahl dient dann weiter um passende Dreiecke aus einem Array auszuwählen. Man kann diese boolean-Werte, die man in den einzelnen Stellen hat, also direkt zusammengefasst nutzen.

In diesem speziellen Fall könnte man auch einfach immer +1, +2, +4, +8 rechnen, aber | (1<<0), |(1<<1), |(1<<2) ginge auch und man weiß dann eben sicher: Da verändere ich genau dieses eine Bit und kann die Position direkt ablesen. (Und es ist sogar ganz minimal schneller, grad paar Durchläufe getestet)

@Marco: Tatsache, die Variante von dir zum Testen auf Gerade oder Ungerade ist auch wieder schneller und danke für den Link (Ist gut für meine Project Euler Programme, da versuch ich immer das Maximum an Geschwindigkeit rauszuholen )

 

[Landei]

"Gerade" testet man meines Wissens am schnellsten mit [c]x & 1 == 0[/c]