Binäre Zahlenreihe vergleichen?

  • VB.NET

Es gibt 17 Antworten in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

    Binäre Zahlenreihe vergleichen?

    Hallo zusammen,

    ich suche ein Programm, um Zeichenketten (die nur aus 0 und 1 bestehen) zu vergleichen.
    Ich weiß nicht genau, wie ich das erklären soll, daher mal ein kurzes Beispiel:

    Nehmen wir mal an, ich hätte ein Programm, welches zum Speichern eines Spielstands nur Booleans benutzt und die als String mit Nullen und Einsen speichert. Dann könnte der gespeicherte String so aussehen:
    "1101010100"
    Ein anderer String (neuer Spielstand) könnte z. B. so aussehen:
    "0110011001"

    Ich bekomme nun im Programm angezeigt, "Einstellung XY ist aktiv" oder "Einstellung XY ist inaktiv". (Ob "aktiv" für 1 oder für 0 steht, weiß ich nicht)

    Wenn der Spielstand wirklich nur aus 10 Bits bestehen würde, könnte ich leicht von Hand herausfinden, welches Bit für Einstellung XY steht. In Wirklichkeit besteht der aber aus 512 Bits.

    Was ich jetzt suche, ist ein Programm, was folgendes tut:

    1. Ich füge einen der Spielstand-Strings ein.
    2. Ich gebe an, ob in diesem Spielstand Einstellung XY aktiv oder inaktiv ist.
    3. Das Programm gibt mir an, welche Offsets im String für diese Einstellung infrage kommen
    4. Ich wiederhole die Schritte 1 bis 3, bis nur noch ein Offset infrage kommt, und dann weiß ich, wo Einstellung XY gespeichert wird.

    Also nochmal ein Beispiel:
    Jeweils die unterstrichenen Bits kommen in Frage, die anderen wurden schon ausgeschlossen:

    "101001": Einstellung aktiv
    "111100": Einstellung aktiv
    "110010": Einstellung inaktiv
    Nun kommen nur noch Bit 3 und 5 infrage
    "000100": Einstellung aktiv
    Nun ist klar, dass "Einstellung XY" in Bit 5 gespeichert wird.

    Und so ein Programm suche ich - ich gebe jede Menge dieser Strings und den jeweiligen Status von Einstellung XY ein, und sobald das Programm genug Werte hat, gibt es mir aus, an welchem Offset das gespeichert ist.

    - Gibt es so ein Programm?
    - Wenn nein, kann mir jemand einen Ansatz geben, wie man sowas in C# selber schreiben könnte?

    (Hoffentlich hab ich das jetzt gut genug erklärt. Wenn irgendwas noch unklar ist, erkläre ichs gern nochmal [anders])

    Leseratte

    Edit by ~blaze~:
    *Thema aus Offtopic verschoben*

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

    Leseratte schrieb:

    Gibt es so ein Programm?
    Es ist ganz ganz einfach.
    Konvertiere Deine 0-1-Zeichenketten in je einen Integer-Wert, diese solche kannst Du dann einfach vergleichen:

    VB.NET-Quellcode

    1. Dim bin = "1101010100"
    2. Dim myInt = Convert.ToInt32(bin, 2)
    3. MessageBox.Show(bin & Environment.NewLine & myInt.ToString)
    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!

    Wobei du dann noch nen Enum anlegen kannst:

    VB.NET-Quellcode

    1. <Flags()>_
    2. Enum DeinEnum
    3. Eigenschaft1=1
    4. Eigenschaft2=2
    5. ...
    6. End Enum

    Dann kannst du es so benutzen:

    VB.NET-Quellcode

    1. Dim myEn As DeinEnum = DirectCast(Convert.ToInt32(bin,2),DeinEnum)
    2. If (myEn And DeinEnum.Eigenschaft2) > 0 Then
    3. ...
    4. End If

    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---

    Ich befürchte, ihr habt noch nicht so ganz verstanden, was ich vorhabe:

    Ich habe keine Ahnung, welches der Bits für die Eigenschaft steht. Ich weiß nur, in welchen Strings die Einstellung aktiv ist und in welchen nicht. Und ein 512-Bit-String wird wohl kaum in einem 32-Bit-Integer passen.

    Leseratte schrieb:

    Und ein 512-Bit-String
    Poste bitte eine vollständige Problembeschreibung, auf die eine Reaktion Deinerseits auf unsere Vorschläge wie

    Leseratte schrieb:

    Ich befürchte, ihr habt noch nicht so ganz verstanden, was ich vorhabe:
    nicht erforderlich bzw. möglich ist.
    --------------------

    Leseratte schrieb:

    Ich habe keine Ahnung, welches der Bits für die Eigenschaft steht.

    Genau deswegen heißen diese Dinger unspezifisch Eigenschaft1 und Eigenschaft2.
    Ab Framework 4.0 gibt es da noch ganz elegante Enum-Operationen wie HasFlag(...).

    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!

    Du hast doch damit bereits ein Ansatz, jetzt kannst du die Bits und die zugehörigen Einstellungen zu speichern. Dann gehst du hin und sortierst es so, dass sich immer nur 1 bit verändert(GrayCode z.B.:) dann musst du nurnoch gucken welche Eigenschaft sich geändert hat und hast das Ergebnis.
    512-Bit String heißt 64 Bytes heißt ein Long. Oder ist der String 512 Zeichen lang?
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---

    Gut.

    Ich habe einen String, der nicht wie im Beispiel aus 10 Bit, sondern aus 512 Bit besteht. (Deshalb kann ich den nicht einfach in einen Int32 laden).
    Irgendeins dieser 512 Bit gibt an, ob eine bestimmte Einstellung (nennen wir sie mal Einstellung X) aktiviert ist.
    Ein mir vorliegendes Programm gibt mir diesen 512-Bit-String zufällig generiert aus, zusammen mit der Information, ob Einstellung X aktiv ist (Ich habe keinen Code, kann also nicht prüfen, wie das generiert wird).

    Das bedeutet: Ich habe viele 512-Bit-Strings, und zu jedem String die Info, ob Einstellung X aktiv oder inaktiv ist. Diese Einstellung ist in einem der 512 Bits gespeichert - ich habe aber keine Ahnung, in welchem.

    Was ich nun suche (oder selber basteln möchte), ist ein Programm, wo ich diese langen Strings einfüge, zusammen mit der Information, ob Einstellung X in dem jeweiligen String aktiv ist oder nicht, und das Programm gibt mir dann (sobald ich genug Datensätze eingefügt habe) aus, in welchem Offset Einstellung X gespeichert ist.

    Ich mache nochmal ein einfaches Beispiel mit nur 3 Bit. Die Daten liegen dann z. B. in folgendem Format vor:

    Quellcode

    1. 001; aktiv
    2. 101; aktiv
    3. 110; inaktiv
    4. 011; aktiv


    Und die nun folgende Überlegung soll dann mit den komplizierteren 512-Bit-Strings von einem Programm durchgeführt werden:

    Da in Datensatz 1 und 2 die Einstellung jedes Mal "aktiv" lautet, kann das erste Bit nicht die Lösung sein (denn es ist unterschiedlich).
    Da in Datensatz 3 und 4 die Einstellungen unterschiedlich sind, kann das zweite Bit auch nicht die Lösung sein (denn das Bit ist immer "1")
    Das Dritte Bit allerdings ist in allen "aktiv"-Fällen 1 und in allen "inaktiv"-Fällen 0. Das trifft auf kein anderes Bit zu

    Ergebnis: Bit 3 ist die Einstellung XY.

    Und genau diese Überlegung soll nun von einem Programm mit einem längeren String und mehr Datensätzen durchgeführt werden.

    jvbsl schrieb:

    sich immer nur 1 bit verändert(GrayCode z.B.:) dann musst du nurnoch gucken welche Eigenschaft sich geändert hat und hast das Ergebnis.


    Wenn ich aber 512 Bits habe und die so sortieren will, brauche ich auch > 512 Datensätze, das wäre etwas aufwändig. Es kann ja z. B. bei 2 Datensätzen wo Byte Nummer X gleich aber die Eigenschaft unterschiedlich ist, das Byte Nummer X aus der Liste der möglichen Stellen entfernt werden, dann bräuchte man weniger Datensätze.

    Der String besteht aus 512 Zeichen, die entweder 0 oder 1 sind. Also 512 Bit.

    Leseratte schrieb:

    Der String besteht aus 512 Zeichen
    512 / 64 = 8, also mach Dir eine Klasse, die als DataMember 8 ULong-Werte hat oder wie auch immer, jedenfalls 512 Bit.
    Diese Klasse braucht Prozeduren, die eine Komvertierung von 512 "String-Bits" nach 8 ULong und umgekehrt sowie die Testmöglichkeit für jedes dieser 512 Bits bzw. Gruppen davon.
    Außerdem brauchst Du einen Vergleichsoperator, also implementiere das IComparable-Interface.
    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!

    Hi
    reicht's nicht einfach, ein (U)Long herzunehmen? Im String stehen ja auch nur 0 oder 1 für die Bits und keine Bytes, somit sollte ULong-Enum seinen Job erledigen... Die Binärwerte, die du kennst, konvertierst du dann halt in Hexadezimaldarstellung. Fasse immer 4 Bits zu einem Nibble zusammen und konvertiere das in die entsprechende Hexadezimaldarstellung und fertig. Alternativ geht's auch über die Convert-Klasse.

    Gruß
    ~blaze~

    Warum wollt ihr daraus ein ULOng machen ?

    Ich würde den String als String behandeln, und die Eigenschaft Active als Boolean -> Klasse "Setting" mit zwei Properties, String "Bits" und Bool "Active"
    Dann erstmal alle Strings samt Boolean einlesen, und in eine List<Setting> speichern. Und dann parallel eine List<int> führen, welche den jewiligen Offset angibt (also anfangs Enumerable.Range(1, 512).ToList()). Und dann würde ich erst mal alle aus der SettingList nehmen, bei denen Acitve = True ist, und dann die Bits an allen Stellen vergleichen, prüfen wo wirklich alle gleich sind. Und an den dann noch übrigen Stellen, nochmal prüfen, ob alle noch nicht probierten aus der List das Gegenteil enthalten.

    EDIT: Geht prima, mit einer Ausnahme: Es ist sehr Fehleranfällig (Liste leer, falsche offsetlänge etc, sollte verbessert werden):
    Spoiler anzeigen

    C#-Quellcode

    1. using System;
    2. using System.Collections.Generic;
    3. using System.Linq;
    4. using System.Text;
    6. namespace ConsoleApplication
    7. {
    8. class Program
    9. {
    10. static void Main(string[] args)
    11. {
    12. List<Setting> settings = new List<Setting>();
    14. settings.Add(new Setting("101001", true));
    15. settings.Add(new Setting("111100", true));
    16. settings.Add(new Setting("110010", false));
    17. settings.Add(new Setting("000100", true));
    19. List<int> offsets = Enumerable.Range(0, 5).ToList();
    23. //Settings with Active == true
    24. List<Setting> active = settings.Where(s => s.Active).ToList();
    26. List<int> offsetscopy = offsets.Where(o => true).ToList();
    28. foreach (int o in offsetscopy)
    29. {
    30. if (!active.All(s => s.Bits[o] == active[0].Bits[o]))
    31. offsets.Remove(o);
    32. }
    34. //Settings with Active == false
    35. List<Setting> inactive = settings.Where(s => !s.Active).ToList();
    36. List<int> offsetscopy2 = offsets.Where(o => true).ToList();
    38. foreach (int o in offsetscopy2)
    39. {
    40. if (!inactive.All(s => s.Bits[o] == inactive[0].Bits[o]))
    41. offsets.Remove(o);
    42. }
    44. //check whether the bit in the inactive settings is different to the bit in the active settings
    45. List<int> offsetscopy3 = offsets.Where(o => true).ToList();
    46. foreach (int o in offsetscopy3)
    47. {
    48. if (active[0] == inactive[0])
    49. offsets.Remove(o);
    50. }
    52. Console.WriteLine(string.Join(" ", offsets));
    53. Console.ReadLine();
    54. }
    56. class Setting
    57. {
    58. public Setting(string b, bool a)
    59. {
    60. Bits = b;
    61. Active = a;
    62. }
    64. public string Bits { get; set; }
    65. public bool Active { get; set; }
    66. }
    67. }
    68. }

    »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „ThePlexian“ ()

    Mit Strings sollte man nicht rechnen. Strings sind prinzipiell nur wirklich dazu geeignet, für von Menschen lesbaren Text zu stehen.
    Konvertiert man es in ein ULong um, so kann man einfach abfragen:

    VB.NET-Quellcode

    1. Dim x As ULong = Convert.ToUInt64(input, 2)
    2. Dim index As Integer = 2
    3. Dim isSet As Boolean = ((input >> index) And 1) = 1

    Das ist platz- und speichersparend, sowie performant.

    Gruß
    ~blaze~

    Natürlich nutzt man Strings nicht zum Rechnen, aber es geht ja um den Inhalt des Strings, es sind ja praktisch 512 booleans du aneinander gehängt wurden, weswegen ich es abwegig fand daraus ne Zahl zu zaubern. Andererseits verstehe ich Bitshifting nicht, selbst nicht nach dem 8ten mal durchlesen der MSDN Seite, aber wenns besser und performanter ist,dann gut.
    »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

    Theoretisch rechnest du damit. Klar, du kannst auch + auf Strings implementieren und es ginge deswegen um Strings, aber das macht man einfach nicht.
    Bitshifting verschiebt einfach die Bits eines Wertes um den angegebenen Wert:
    (Die Angaben sind zur Basis 2 ==> 0bX)
    0b1 << 2 = 0b100
    0b100 >> 2 = 0b1

    Wenn dann was über den "Rand" hinaussteht, z.B. 0b100 >> 3, wird's abgeschnitten. Mathematisch gesehen entspricht 1 << n dann 2^n und 1 << -n = 1 >> n.
    In einer Binärzahl hast du auch quasi lauter Booleans (eben als Bit) aneinandergehängt ==> ist halt sinnvoll, damit zu arbeiten und nicht den Umweg über die Strings zu gehen.

    Ach ja, zum Code oben:
    Das i-te Bit ist dann gesetzt, wenn (1 << i) = 1. Insofern wird der Wert um i nach rechts geshiftet, sodass die i-te Stelle an die 0-te Stelle gerutscht wird und anschließend wird mit And 1 der linke Teil weggeschnitten. Was dann überbleibt ist entweder 0 oder 1.

    Übrigens gibt's noch einen Unterschied zwischen ULong und Long, UInteger und Integer, UShort und Short bzw. Byte und SByte: Wenn die Zahlen darin negativ sind, werden bei der >>-Operation das Überhängsel (das, was unbekannt ist halt) mit 1 aufgefüllt.

    Gruß
    ~blaze~

    Okay, danke, aber wozu braucht man das oO Vor allem in deinem Beispiel ist das etwas verwirrend, vorallem mit dem And 1) = 1 ^^
    »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

    ThePlexian schrieb:

    etwas verwirrend
    Das lässt sich auch ohne Shift realisieren:

    VB.NET-Quellcode

    1. If (LargeValue And OneBit) = OneBit Then
    2. MesageBox.Show("Bit OneBit ist gesetzt")
    3. Else
    4. MesageBox.Show("Bit OneBit ist nicht gesetzt")
    5. End If

    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!

    Da werden halt alle Stellen abgeschnitten, die darüber hinausragen. Z.B.
    1100101, wenn du die 3. Stelle haben willst, wäre eben 1100101 >> 2 = 11001, weshalb du noch den Rest abschnibbeln musst, daher And 1, da eben das bitweise Komplement dazu führt, dass nur die in beiden Werten gesetzten Bits überbleiben (d.h., wenn das i-te Bit eben beim linken und rechten Teil gesetzt ist, ist es auch im Resultat gesetzt, sonst nicht).
    Das braucht man für allerlei Spielereien, wird dir sicher das eine oder andere Mal über den Weg laufen. Wie gesagt, es MUSS nicht so gelöst werden, aber es KANN so gelöst werden und ist häufig sinnvoll, da Bitshift eine der performantesten Operationen deines x86/x86_64-Prozessors ist.

    Die Variante von @RodFromGermany ist halt die gängigere Art, wie man das hinschreibt, sofern OneBit (1 << x) oder z.B. ein Wert aus einer Enumeration ist.

    Gruß
    ~blaze~

    Also ist 11001 And 01001 = 01001, da nur das 2. und 4. Bit = 1 sind ?

    EDIT: Ah, ich habs glaub ich ^^ Das heißt die Konvertierung in ULong ist nur dafür da um mit BitShifting wieder auf die Bits zugreifen zu können, da das mit String halt nicht geht.
    Also ist mystring[x] == (myulong >> x) And 1 ? (ohne auf datentypen zu achten, und wenn der String halt ne Bitfolge beinhaltet)
    »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „ThePlexian“ ()

    ~blaze~ schrieb:

    oder z.B. ein Wert aus einer Enumeration ist.

    RodFromGermany schrieb:

    Ab Framework 4.0 gibt es da noch ganz elegante Enum-Operationen wie HasFlag(...).
    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!