Algorithmus Binärdarstellungen prüfen

  • VB.NET
  • .NET (FX) 4.5–4.8

Es gibt 12 Antworten in diesem Thema. Der letzte Beitrag () ist von Haudruferzappeltnoch.

    Algorithmus Binärdarstellungen prüfen

    Hallo,

    ich habe einen kleinen Algorithmus der 5 Ganzzahlen auf eine bestimmte Eigenschaft prüfen soll.
    Eine Ganzzahl ist bekanntermaßen darstellbar als
    N = 2^0 + 2^1 + ... + 2^(n-1)
    wobei
    n
    die Bitgröße ist.
    Der Algorithmus ist eine Funktion die True zurückgibt, wenn jede 2er Potenz mindestens 3 mal im Input vorkommt, also in 5 Ganzzahlen.

    Ich lande im Schnitt bei 14,5 Mikrosekunden, geht das noch besser? (Bei n=7!)

    VB.NET-Quellcode

    1. Private Function Check(arr As Integer(), n As Integer) As Boolean
    2. Dim f As Integer
    3. For i = n - 1 To 0 Step -1
    4. For j = 0 To arr.Length - 1
    5. If arr(j) - 2 ^ i >= 0 Then f += 1 : arr(j) -= CInt(2 ^ i)
    6. Next
    7. If f < 3 Then Return False
    8. f = 0
    9. Next
    10. Return True
    11. End Function


    Viele Grüße

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Haudruferzappeltnoch“ ()

    Ich habe es nicht getestet, aber was mir aufgefallen ist.

    Beide 2 ^ i lassen sich auch schreiben als 1 << i, und Bitwise-Operationen sind meistens ein bisschen schneller, vor allem, wenn's den noch richtig grosse und viele Zahlen sind.

    Freundliche Grüsse

    exc-jdbi

    @Haudruferzappeltnoch Sieh Dir mal das BitArray an:
    learn.microsoft.com/de-de/dotn…ommendations&view=net-7.0
    ====
    Arbeitest Du mit anderen Basen als n = 2?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „RodFromGermany“ ()

    RodFromGermany schrieb:

    Arbeitest Du mit anderen Basen als n = 2?
    Ich weiß nicht wie man sich die Basis mit der man arbeitet aussuchen könnte. Der Computer macht doch alles in Bits?

    @exc-jdbi ~Faktor 3: 5,5 Mikrosekunden

    VB.NET-Quellcode

    1. Private Function Check(arr As Integer(), n As Integer) As Boolean
    2. Dim f As Integer
    3. For i = n - 1 To 0 Step -1
    4. For j = 0 To arr.Length - 1
    5. Dim t = arr(j) - (1 << i)
    6. If t >= 0 Then f += 1 : arr(j) = t
    7. Next
    8. If f < 3 Then Return False
    9. f = 0
    10. Next
    11. Return True
    12. End Function

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „Haudruferzappeltnoch“ ()

    Haudruferzappeltnoch schrieb:

    Der Computer macht doch alles in Bits?
    Für die PC-interne Darstellung ist n = 2, das kannst Du dann fest einprogrammieren.
    Ich sehe bei diesem Problem nur grauen Nebel. Kannst Du das mal ein wenig aufhellen?
    Wie ist da das BitArray nützlich?
    Und:
    Bei a And b bleiben alle gemeinsamen Bits stehen.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Hab die jetzt gerade noch kurz testet. Weiter würde ich das nicht noch wollen zu "Bitwiserisieren" (was für ein Wort).

    Edit: Angepasst.

    Spoiler anzeigen

    C#-Quellcode

    1. var truefalse = CheckedBits(arr, 5, 3);
    3. private static bool CheckedBits(int[] arr, int n, int c)
    4. {
    5. for (int i = n - 1, f = 0; i >= 0; i--, f = 0)
    6. {
    7. for (int j = 0; j < arr.Length; j++)
    8. {
    9. var t = arr[j] - (1 << i);
    10. if (t >= 0) { f++; arr[j] = t; }
    11. }
    12. if (f < c) return false;
    13. }
    14. return true;
    15. }

    VB.NET-Quellcode

    1. Private truefalse = CheckedBits(arr, 5, 3)
    3. Private Shared Function CheckedBits(ByVal arr As Integer(), ByVal n As Integer, ByVal c As Integer) As Boolean
    4. Dim i = n - 1, f = 0
    6. While i >= 0
    7. For j = 0 To arr.Length - 1
    8. Dim t = arr(j) - (1 << i)
    9. If t >= 0 Then
    10. f += 1
    11. arr(j) = t
    12. End If
    13. Next
    14. If f < c Then Return False
    15. i -= 1
    16. f = 0
    17. End While
    18. Return True
    19. End Function


    So überschlagsmässig, die Bitwise-Operationen, die man dafür bräuchte. Kann ich aber nicht empfehlen. Die sollten sich leicht auch in Vb.Net umschrieben lassen.
    Spoiler anzeigen

    C#-Quellcode

    1. static int sign(int number)
    2. {
    3. var s= highest_one_bit(number);
    4. if (s == 0) return 0;
    5. if (s > 0) return 1;
    6. return -1;
    7. }
    9. static int unset_n_bit(int number, int n) =>
    10. //number | (1 << n); // Das wäre setbit an n
    11. number & ~(1 << n);
    13. static bool greater_then(int left, int right) =>
    14. highest_one_bit(left) > highest_one_bit(right);
    16. static int highest_one_bit(int number)
    17. {
    18. //Für uint oder int
    19. number |= number >> 1;
    20. number |= number >> 2;
    21. number |= number >> 4;
    22. number |= number >> 8;
    23. number |= number >> 16;
    24. return number - (number >>> 1); //Ab .Net 5.0
    25. }
    27. int count_bits_set(int[] number, int c) =>
    28. number.Where(x => count_bits_set_sum(x) >= c).Count();
    30. int count_bits_set_sum(int number)
    31. {
    32. int result;
    33. for (result = 0; number != 0; result++)
    34. number &= number - 1;
    35. return result;
    36. }



    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „exc-jdbi“ ()

    @Haudruferzappeltnoch Beschreib doch mal verbal, was da eigentlich ablaufen soll.
    Ich sehe da die Möglichkeit, mit (sehr schnellen) Bit-Operationen was zu erreichen, wenn ich wüsste, was.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Ich weiß noch nicht wie das BitArray nützlich ist, ich muss die ja erstmal erzeugen (ich brauche ein BitArray für jede Ganzzahl) und ich muss noch ausprobieren wie ich damit rechne.

    And Not statt - macht mir alles kaputt ich weiß noch nicht warum.

    Ein Beispiel: Geprüft werden die Zahlen {127,72,65,44,13}. Die gehen als arr rein in die Funktion. n = 7, das heißt auch gleichzeitig, dass in arr keine Zahlen größer 127 vorkommen.
    Ich gehe jede 2er Potenz einzeln durch: For i = n - 1 To 0
    Hier wird jede Ganzzahl von arr geprüft, ob es > ist als diese Potenz. Es muss mindestens 3 mal True dabei rauskommen, dann ist f >= 3 und die Prüfung läuft weiter.
    127,72,65 sind größer 2^6. Ich erhalte f=3, arr sieht danach so aus: {63,8,1,44,13}
    65, 44 sind größer als 2^5, leider ist f = 2. Prüfung beendet mit False.
    2^5 ist nur zweimal in dieser Ganzzahlkombination enthalten. Gewünscht ist jedoch 3+

    Edit: Tschuldigung meine f nicht a

    @exc-jdbi
    Dein Code läuft in der ersten Schleife immer von 4 bis 0, aber die Bitgröße der größten Ganzzahl ist die Zahl der Schleifenläufe, die wird als n mitübergeben, du übergibst stattdessen die Kondition c. Die ist fest 3

    Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „Haudruferzappeltnoch“ ()

    Du kannst Dir im Rechner vom Betriebssystem die Binär-Darstellung Deiner Zahlen ansehen.
    Danach kannst Du ggf. eine bessere Problembeschreibung posten.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Danke habe es oben einigermassen angepasst.

    Sorry edit:

    Ja das ist so, denn For i = n - 1 To 0 geht immer um eins nach untern, und nach 6 kommt 5, wie du es oben beschrieben hast, darum ergibt es ein false. Willst du da nicht bei 7 anfangen, weil 2^7 ergibt ja die 128.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „exc-jdbi“ ()

    Ja gut.
    Wähle n: n=7
    Wähle 5 Ganzzahlen, wichtig für alle muss gelten >= 0 und < 2^n: 127,72,65,44,13
    Betrachte die Binärdarstellung in einer tabellarischen Darstellung:


    Diese Ganzzahlkombination ist durchgefallen

    @exc-jdbi
    Nein wenn n=7 ist dann muss und darf ich 2^7 nicht prüfen, weil dieser Bit ist immer 0, denn alle Ganzzahlen sind echt kleiner 128
    Wenn n = 2 dann darf ich 2^3 auch nicht prüfen, denn alle Ganzzahlen sind kleiner 8 gewählt

    Wenn ihr euch fragt wie ich die Laufzeit der Prüfung ermittel: Ich laufe alle möglichen Kombinationen (~310 Mio) an 5 positiven Ganzzahlen kleiner 2^7 durch und berechne den Schnitt aller Prüfungen.

    Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von „Haudruferzappeltnoch“ ()

    Haudruferzappeltnoch schrieb:

    Betrachte die Binärdarstellung in einer tabellarischen Darstellung:
    OK, nun habe ich Dein Problem verstanden, BitArray ist damit aus dem Rennen.
    Dies hier ist etwas übersichtlicher:

    VB.NET-Quellcode

    1. Private Function Check(arr As Integer(), n As Integer) As Boolean
    2. For i = n - 1 To 0 Step -1
    3. Dim f = 0
    4. For j = 0 To arr.Length - 1
    5. If (arr(j) And (1 << i)) <> 0 Then
    6. f += 1
    7. End If
    8. Next
    9. If f < 3 Then Return False
    10. Next
    11. Return True
    12. End Function
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

Facebook
Telefonspende