# Bit Operationen in der Praxis



## ARadauer (10. Jul 2009)

... 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 (10. Jul 2009)

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 (10. Jul 2009)

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 (10. Jul 2009)

warum wird dann nicht gleich % genommen? performance?


----------



## thE_29 (10. Jul 2009)

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 (10. Jul 2009)

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 (10. Jul 2009)

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 (10. Jul 2009)

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 (10. Jul 2009)

SlaterB hat gesagt.:


> 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 (10. Jul 2009)

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 (10. Jul 2009)

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 (10. Jul 2009)

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 (10. Jul 2009)

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.



SlaterB hat gesagt.:


> 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 (11. Jul 2009)

musiKk hat gesagt.:


> 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 (11. Jul 2009)

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


----------



## Landei (13. Jul 2009)

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

Bit Twiddling Hacks


----------



## Ark (13. Jul 2009)

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

Ark


----------



## Marco13 (13. Jul 2009)

Marco13 hat gesagt.:


> 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 (13. Jul 2009)

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.


----------

