Binary Operations

[StupidAttack]

Heyho liebe Community!

Ich code in C, habe aber eine allgemein Info-Frage; die binären Operatoren gibts ja auch in Java.
Ich habe folgenden Datentyp:

unsigned long long example = 0x6911E091631;

Obiger hex Wert entspricht ja in binärer Form:

00000000 00000000 00000110 10010001 00011110 00001001 00010110 00110001

Wie kann ich nur mithilfe der binären Operatoren rausfinden, wie oft, exakt eine 1 neben einer 1 steht (11, aber nicht 111 oder 1111...)
Bsp:

00000000 00000000 00000[B]11[/B]0 10010001 00011110 00001001 00010[B]11[/B]0 00[B]11[/B]0001

Ergebnis : 3

Ich könnte ja zum Bleistift:

int counter(0);
unsigend long long startvl = 0x03;

   for ( int j = 0; j < somevalue; j++) {
      if ( (startvl & example) == startvl )
         counter++;
      startvl <<= 1;
   }

Aber das sieht i-wie plöd aus...

Danke für eure Hilfe!

Edit: Ausserdem zählt obiger Code 111 als zwei 11...Also hier bräuchte ich Hilfe...Ausserdem, geht das nicht irgendwie galanter?

 

[Marco13]

Das ist so speziell dass man vermutlich selbst auf Bit Twiddling Hacks nichts dazu findet (wobei mal mal schauen kann, ob man etwas ähnliches findet, und das ggf. abwandeln kann).

Vermutlich würde ich mit einer Schleife durchlaufen und auf 0x6 (=0110) suchen, und für die obersten und untersten 3 bits je einen extra-Test machen.

 

[fragez]

Warum machst du es nicht so? Oder willst du jetzt die Dezimalzahl wissen, die binär so ...11111111111110110 aussieht?

 

[fastjack]

Warum machst du es nicht so?

er sucht wohl eine Alternative, warum sonst hat er diesen Thread angelegt?!?!

 

[StupidAttack]

Vermutlich würde ich mit einer Schleife durchlaufen und auf 0x6 (=0110) suchen, und für die obersten und untersten 3 bits je einen extra-Test machen.

Danke für die Seite, sieht interessant aus. Den Typ werd ich so umsetzen. Generell wollte ich dir mal in Namen aller hier danken, ist nicht selbstverständlich wie du nie die Geduld verlierst und sogar für blutige Anfänger Google emulierst

Jetzt noch die heilige Performance Frage: Wie du vieleicht ahnst, stellt obige 64 bit Zahl (binär gesehen) ein 8*8 Feld dar. Ich hätte aber auch ein int[8][8] array nehmen können (welches ein vielfaches grösser ist, sogar ein byte[][]).
Nun: Ist die Arrayüberprüfung

if(fiel[i][j] == 1 &&  fiel[i+n][j] == 1)
...(entsprechend das ganze feld)

schneller oder die besprochene Variante, wo ich ja zusätzlich nen datentyp brauche ( unsigend long long startvl ) den ich erhöhe?

Unabhängig davon: Solle ich gänzlich mit Expressions arbeiten? Ist das besser?
Also in dem Stil:

   for ( int j = 0; j < somevalue; j++) {
      if ( ((0x6<<j) & example) == (0x6<<j) )
         counter++;
      startvl <<= 1;
   }

Da hab ich einerseits den Vorteil, dass ich keine Variable habe (der Prozessor sucht keine Adresse sondern rechnet sofort), andereseits muss ich den Wert 2 mal berechnen und muss ihn insgesamt viel mehr lshiften, da er nicht gespeichert wird...

was ist schneller?

Edit: Ich denke, dass es zwischen 0x03 und 0x06 keinen Unterschied gibt. Beide müssen ja zwecks Überprüfung der ganzen Zahl geshiftet werden. So ist (0x03 << 1 == 0x06), die Frage ist wieder offen...

Kann es sein, dass mein Problem so nicht zu lösen ist, sondern nur, wenn man bei den grösstmöglich Flaghaufen anfängt (bei mir 1111) und dann berechent wie viel 111 es geben muss und daraus ne gleichung mit 3 Parameter macht und auf die Anzahl der 11 schliessen kann?

Ich glaub ich habs:

[B]res = anzahl(11)-[ (anzahl(1111)*3 + anzahl(111)*2) ][/B]

Aber ist halt ned so elegant und performant oO

 

[Ark]

Wenn es dir um Performanz geht, solltest du an dieser Stelle Lookup-Tables in Betracht ziehen. Die erstellst du einmal zu Beginn (oder hast sie sogar fest kodiert im Quelltext), dann ist praktisch nur noch ein Schritt pro 8 oder 16 Bit (je nachdem, wie groß du deine Tabelle machst) notwendig.

Muss man diese Verkettungen auch über Bytegrenzen hinweg beachten, dass z.B. 00000001 10000000 ebenfalls als ein Vorkommen gezählt wird? Dann wird die Sache minimal aufwändiger, aber ein LUT-Ansatz sollte nach wie vor erfolgversprechend sein.

Übrigens ist das, was du als lokale Variablen eingibst, die eine Sache, was der/die Compiler daraus macht/machen, eine andere. Letztendlich wird nämlich alles auf Register geschoben, und Variablen und Register leben in völlig verschiedenen Welten, die erst durch den/die Compiler zusammengebracht werden. Es kann sein, dass der Compiler mehr Register benutzt als du Variablen. Es kann sein, dass es andersherum ist. Es kann sein, dass das, was du ausschreibst, um lokale Variablen zu sparen, vom Compiler wieder zusammengefasst wird, indem er intern gleiche Teilausdrücke auf Register abbildet. Es kann auch sein, dass lokale Variablen durch geschickte Ausnutzung von Registern praktisch überflüssig werden.

Du solltest aber davon ausgehen, dass der Compiler nicht optimiert; im Zweifelsfall tut er es nämlich nicht, und was Zweifelsfälle sind, ist so eine Sache. So kann etwa eine Division durch 2 nur dann durch einen Rechtsshift ersetzt werden, wenn der Dividend garantiert nicht negativ ist. Man tut also gut daran, die eine oder andere Optimierung nicht dem Compiler zu überlassen, weil er schlicht nicht alle Randbedingungen kennt. Übrigens ist nicht alles, was danach aussieht, eine reine Performance-Optimierung: Official Google Research Blog: Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

Wenn du wissen willst, was Compiler aus deinem Quellcode machen, kannst du entsprechende Literatur suchen. Da wäre z.B. als Standardwerk das Drachenbuch zu nennen. Aber bereits das (vergleichende) Lesen von Bytecode bringt interessante Dinge zutage.

Ark

EDIT: Ach, ja, wenn es um Performance geht, solltest du eventuell auch in Erwägung ziehen, mehrere Threads zu benutzen. Zumindest kann das unter bestimmten Umständen auf Mehrkernprozessoren sinnvoll sein.

Ark

 

[Marco13]

Ja, eine Lookup table könnte eine Möglichkeit sein, aber die zu definieren könnte schwierig werden. Im schlechtesten Fall hat man für die "Randfälle" (über bytegrenzen hinweg) so viele if's und Arrayzugriffe, dass der mögliche Vorteil wieder aufgefressen wird.

@TO: Wie schon angedeutet ist die Frage, was genau aus einem

if ( ((0x6<<j) & example) == (0x6<<j) )

oder einem

long x = (0x6<<j);
if ( (x & example) == x )

wird, schwer zu beantworten. Bei der "direkten" Übersetzung in den Bytecode würde das zweite erstmal weniger Instruktionen benötigen, aber in C sieht das ganze schon wieder anders aus. Ab einem bestimmten Punkt helfen nur noch Assemblercode lesen, ggf. Profilerläufe und Microbenchmarks (die bei C ja deutlich einfacher und "verläßlicher" sind als in Java).

Meine erste Antwort von oben habe ich nochmal gelesen, und es stimmt: Die Formulierung war etwas ... lapidar und "unpräzise", in dem Sinne, dass das "durchlaufen" und "auf 0x6 (=0110) suchen" nicht näher spezifiziert war. Das "Durchlaufen" bezieht sich auf die relevanten Teile der Eingabe (und nicht des zu suchenden Musters). Es werden also immer einzelne "Nibbles" (halbe bytes, 0xF) der Eingabe mit dem zu suchenden Muster verglichen.
EDIT: Und zwar mit ==, siehe unten

Hier nochmal ein Beispiel in Java. An den Grenzen (0 und 64) muss man nochmal überlegen (bzw. klären, ob "110000..." oder "000011" nun als Treffer gelten oder nicht), aber die kann man ggf. getrennt abfragen

public class ShiftTest
{
    public static void main(String args[])
    {
        // 00000000 00000000 00000110 10010001 00011110 00001001 00010110 00110001
        long value = 0x6911E091631L;
        System.out.println("Result: "+count(value));
    }

    private static int count(long value)
    {
        int counter = 0;
        long pattern = 0x6;

        for (int j = 0; j < 60; j++)
        {
            long v = (value >> j) & 0xF;

            System.out.println("At "+j);
            System.out.println("nibble  "+pad(v));
            System.out.println("pattern "+pad(pattern));

            if (v == pattern)
            {
                counter++;
                System.out.println("found:  "+pad(value));
                System.out.printf("        %"+(64-j-4)+"s^^^^\n", " ");
            }
        }
        return counter;
    }

    private static String pad(long v)
    {
        String s = Long.toBinaryString(v);
        while (s.length() < 64)
        {
            s = "0"+s;
        }
        return s;
    }
}

EDIT: Seltsame Hirnverquerungen zu Vergleichen geändert...

 

[muckelzwerg]

Wie wäre es erstmal mit "j += 3" wenn ein Treffer gefunden wurde?
Vielleicht hab ich was übersehen, aber da kann man doch erstmal vier Bit wegschieben.

Und dann die obligatorische Frage "warum in Java?".
Wenn die Performanz wirklich wichtig ist, könntest Du es vielleicht in C/Assembler machen und über JNI aufrufen.

 

[Ark]

Und dann die obligatorische Frage "warum in Java?".
Wenn die Performanz wirklich wichtig ist, könntest Du es vielleicht in C/Assembler machen und über JNI aufrufen.

Je nach Größe der Eingabe könnte der Aufruf von nativ implementierten Methoden mehr Zeit kosten, als das alles in Java zu belassen. Wichtiger als die Sprache dürfte sowieso der Algorithmus sein, und bevor das nach Assembler portiert wird, sollte man erst einmal schauen, ob Java nicht auch schon reicht.

Ark

 

[muckelzwerg]

"hätte, könnte, würde ..." ich hab doch selbst "könntest Du" geschrieben. Muss man halt mal ausprobieren.
Ist doch eine interessante Frage.

So wie ich das verstanden habe, will StupidAttack es doch sowieso in C schreiben und NICHT in Java? Ihm kann es dann sowieso egal sein. Meine Frage ging an Marco.

 

[Marco13]

Mir ist die Performance dabei "egal" (dass man j+=3 machen kann ist natürlich eine Möglichkeit, aber viel nahe liegender wäre eigentlich, das Nibble mit == mit dem Pattern zu vergleichen (was hab' ich mir nur dabei gedacht? :noe: )). Und in java - weil's einfacher und schneller zu testen ist.

 

[muckelzwerg]

Bis zum "if( ....)" war es doch ganz gut. Aber insgesamt ist es dann halt "& | && == == " statt nur "=="?

 

[Marco13]

Jup, hab's mal angepasst. Manchmal kommen schon Zweifel auf... es ist schon schwierig, so einen Mist zu rechtfertigen.

 

[muckelzwerg]

Ach komm schon. Andere schaffen es nichtmal Unsinn zu schreiben. Und wenn doch, dann merken sie es oft nicht.

Ich hab gerade überlegt, ob man günstiger als mit dem Vergleich pro Nibble wegkommt.
Vielleicht könnte man das maskierte Nibble nutzen, um einen Shift zu machen, immer wenn das Pattern anliegt, oder so ähnlich.

Vielleicht geht es aber auch gar nicht einfacher. Könnte auch sein.