3. Bit Mask

Bit Mask

  • J

    Hey,
    ich habe eine Bit Folge mit beliebiger Länge gegeben. In dieser können die Bits beliebig gesetzt sein.
    Z.B.: 0b0011001.
    Nun will ich überprüfen, ob in dieser Bit Folge vier Einsen hintereinander vorkommen. Z.B.: 0b0111101. Dabei suche ich die schnellste Möglichkeit dies zu tun.

    EDIT:
    Nach längerem Überlegen bin ich auf folgende Lösung gekommen:

    bool four_bits_in_a_row_set(int a)
{
    return (a & (a << 1) & (a << 2) & (a << 3));
}

    Das wären dann 6 Operationen.
    Aber vielleicht fällt jemanden noch etwas schnelleres ein?

    Gruß,

    Julian

    0
  • T

    Schreibe mal alle möglichen Kombinationen auf, bei welchen 4 Einsen hintereinander zu finden sind (Länge 7 Bit). Dann überlege dir, wie du deine Eingabe mit jeder der Kombinationen prüfen kannst.

    // edit

    Weiter kannst du dir überlegen, wie du die 4er-Kombinationen Erzeugen kannst.

    0
  • J

    Ich verstehe nicht ganz, worauf du hinaus willst 😞
    1111000
    1111001
    1111010
    1111011
    1111101
    1111110
    1111111
    0111100
    0111101
    0111110
    0111111
    0011110
    0011111
    0001111

    Und nun?
    Mir fällt da eigentlich nur folgendes ein:
    (bitfolge & 1111000) == 1111000 ||
    (bitfolge & 0111100) == 0111100 ||
    (bitfolge & 0011110) == 0011110 ||
    (bitfolge & 0001111) == 0001111

    Gibt es da nichts mit weniger Operationen?

    Edit: Ich bin so versessen auf eine Lösung mit weniger Operationen, da ich denke, dass ich mal eine schnellere gesehen habe.

    0
  • T

    JulianH schrieb:

    Ich verstehe nicht ganz, worauf du hinaus willst 😞

    Naja, ich habe mich unklar ausgedrückt. Ich meinte eigentlich Masken, die die 4er-Kombinationen erkennen. Eine einfache Operation die alles auf einmal macht gibt es aber nicht. Allerdings spielen in den Masken auch nur die 1er eine Rolle ...

    Zum Beispiel sind die Eingaben
    0111100
    0111101
    0111110
    0111111

    alle mit der Maske x1111xx abgedeckt.

    D. h. es gibt eigentlich nur folgende Masken:
    xxx1111
    xx1111x
    x1111xx
    1111xxx

    Jetzt musst du nur noch herausfinden, wie du maskieren kannst und als Erweiterung kannst du die Masken generieren, anstatt sie explizit hinzuschreiben.

    // edit: OK, hab übersehen, dass du ja schon nur die relevanten Masken benutzt.

    0

  • 0111100 ist in C++ keine gültige Zahlendarstellung für Binärzahlen. Du musst das Bitmuster schon im richtigen Format angeben. Lass dir 0111100 mal als Zahl ausgeben, das ist nicht 120/0x78 😉

    0
  • J

    Ich hab nach langem Überlegen doch was gefunden:
    a=Bit Folge
    (a & (a<<1) & (a<<2) & (a<<3)) > 0

    Gibt es noch was schnelleres?

    0
  • J

    DocShoe schrieb:

    0111100 ist in C++ keine gültige Zahlendarstellung für Binärzahlen. Du musst das Bitmuster schon im richtigen Format angeben. Lass dir 0111100 mal als Zahl ausgeben, das ist nicht 120/0x78 😉

    int a = 1100b

    Sollte compilieren.
    Edit:
    Ich meinte natürlich

    int a=0b1100

    😃

    0
  • J

    Mir ist heute klar geworden, wie sehr wir hier aneinander vorbei geredet haben (ich war gestern wohl etwas unter Strom).

    Ich habe oben mal meine Frage editiert und nochmal anständig nachgefragt.

    0
  • Mod

    Die Antworten, die dir gegeben wurden, passen immer noch. Wenn du die Zahl mit 15 << N verUNDest und dabei immer noch 15 << N heraus kommt, dann waren die 4 Bits N Stellen vor dem Ende allesamt gesetzt.

    Das ist eine Bitverschiebung, eine UND-Operation und ein Vergleich. Die Bitverschiebungen kannst du dabei sogar schon zur Compilezeit berechnen, dann sind es nur 2 Operationen. Das muss aber nicht notwendigerweise schneller sein, da kurzer Code, der dafür mehr berechnet, auch schneller sein kann, als Code, der aufgrund vieler vorberechneter Konstanten sehr lang ist.

    0
  • J

    Ich verstehe nicht was du meinst.
    Was soll mir 15 << N == 15 << N helfen?
    Und was ist mit dem Fall, dass die 4 Bits nicht am Ende in Folge sind?

    EDIT:
    Ich habe, jetzt nach deinem Edit noch mehr, echt ein Problem dir zu folgen.

    EDIT2:
    Ok ich habe jetzt begriffen worauf du anspielen wolltest. Dennoch brauche ich dann mit deiner Lösung bei einer Länge von nur 20 Bits 17x den Schritt, den du beschrieben hast, um die komplette Bitfolge zu überprüfen. Also O(n).

    In meiner Lösung bleibt die Ausführungszeit hingegen konstant.

    Und außerdem ist die Antwort in der du dich in deiner beziehst, von mir.

    Also mal im ernst, wenn ihr keinen bock habt, euch Gedanken zu machen, postet doch bitte einfach nichts.

    0
  • Mod

    Boah, du bist mit deinen dauernden Edits kreuz und quer im Thread echt nicht sehr hilfreich. Man weiß nicht, was genau deine momentan aktuelle Frage, welcher Code gerade aktuell ist, oder wobei du Probleme hast. Und wenn man versucht, das irgendwie nachzuvollziehen und dabei nicht exakt den Stand rekonstruieren kann, den du im ganzen Thread verteilt hast, pflaumst du einen auch noch an. Da habe ich ja echt Motivation, dir zu helfen 🙄

    0
  • ?

    JulianH schrieb:

    postet doch bitte einfach nichts.

    machen wir doch gerne. tschüss.

    0
  • J

    ausdiemaus schrieb:

    JulianH schrieb:

    postet doch bitte einfach nichts.

    machen wir doch gerne. tschüss.

    Dann lass es doch endlich sein.

    0
  • Mod

    Ich mache hier mal zu. Der TE hat deutlich gemacht, dass er keine Hilfe möchte, jetzt muss man nicht weiter angucken, wie die Trolle angelaufen kommen und auf ihm einhacken.

    0
Anmelden zum Antworten