Gibt es eine praktische Grenze für die Größe von Bitmasken?

Question

Es gibt einen gemeinsamen Weg, um mehrere Werte in einer Variablen zu speichern, durch eine Bitmaske verwenden. Zum Beispiel, wenn ein Benutzer Lese-, Schreib- und Ausführungsrechte auf ein Element, das read = 4 (2^2), write = 2 (2^1), execute = 1 (2^0) mit den Worten auf eine einzige Zahl umgewandelt werden können und sie dann zusammen in den 7 zu erhalten.

Ich verwende diese Technik in mehreren Web-Anwendungen, in denen ich in der Regel die Variable in ein Feld speichern würde und gebe ihm eine Art von MEDIUMINT oder was auch immer, abhängig von der Anzahl der verschiedenen Werte.

Was mich interessieren, ist, ob es eine praktische Grenze für die Anzahl der Werte, die Sie wie folgt speichern kann? wenn die Zahl der über 64 war zum Beispiel, könnten Sie nicht verwenden (64 Bit) ganzen Zahlen nicht mehr. Ist dies der Fall war, was würden Sie nutzen? Wie wäre es, Ihre Programmlogik beeinflussen (dh: Sie könnten noch bitweise Vergleiche verwenden)?

Ich weiß, dass, wenn Sie wirklich immer große Mengen von Werten beginnen, eine andere Methode die optimale Lösung sein würde, aber ich bin interessiert an den Grenzen von dieser Methode.

Answer 1

Aus der Spitze von meinem Kopf, würde ich eine set_bit und get_bit Funktion schreiben, die eine Reihe von Bytes und ein wenig in der Anordnung versetzt nehmen könnten, und verwenden Sie einig Bit-twiddling das entsprechende Bit in dem Array zu setzen / get . So etwas wie dies (in C, aber hoffentlich Sie erhalten die Idee):

// sets the n-th bit in |bytes|. num_bytes is the number of bytes in the array
// result is 0 on success, non-zero on failure (offset out-of-bounds)
int set_bit(char* bytes, unsigned long num_bytes, unsigned long offset)
{
  // make sure offset is valid
  if(offset < 0 || offset > (num_bytes<<3)-1) { return -1; }

  //set the right bit
  bytes[offset >> 3] |= (1 << (offset & 0x7));

  return 0; //success 
}

//gets the n-th bit in |bytes|. num_bytes is the number of bytes in the array
// returns (-1) on error, 0 if bit is "off", positive number if "on"
int get_bit(char* bytes, unsigned long num_bytes, unsigned long offset)
{
  // make sure offset is valid
  if(offset < 0 || offset > (num_bytes<<3)-1) { return -1; }

  //get the right bit
  return (bytes[offset >> 3] & (1 << (offset & 0x7));
}

Answer 2

Ich habe Bitmasken in Dateisystem-Code verwendet, wo die Bit-Maske viele Male größer als ein Maschinenwort ist. denken Sie daran, wie ein „Array von booleschen“;

(Journaling Masken im Flash-Speicher, wenn Sie wissen wollen)

viele Compiler wissen, wie dies zu tun Sie . Adda Bit von OO-Typen zu haben, die senibly arbeiten und dann Ihr Code beginnt mit der Suche, wie es Absicht ist, nicht irgendein Bit-Banging.

Meine 2 Cent.

Answer 3

Mit einem 64-Bit-Integer, können Sie Werte speichern bis zu 2 ^ 64-1, 64 sind nur 2 ^ 6. Also ja, es gibt eine Grenze, aber wenn Sie mehr als 64-its im Wert von Fahnen benötigen, würde ich sehr daran interessiert zu wissen, was sie alle tun:)

Wie viele Staaten so müssen Sie möglicherweise darüber nachdenken? Wenn Sie 64 mögliche Zustände haben, in der Anzahl der Kombinationen sie existieren können, ist die Größe von einem 64-Bit-Integer.

Wenn Sie über 128 Flaggen sorgen, dann ein Paar von Bit-Vektoren würde genügen (2 ^ 64 * 2).

Addition : in Programming Pearls, gibt es eine ausführliche Diskussion einen Bit-Array mit einer Länge von 10 ^ 7 der Verwendung in ganzen Zahlen implementiert (für 800-Nummern verwendet werden) - es ist sehr schnell und sehr angemessen für die Aufgabe in diesem Kapitel beschrieben.

Answer 4

Einige Sprachen (ich glaube, Perl tut, nicht sicher) erlauben bitweise Arithmetik auf Zeichenfolgen. Geben Sie eine viel größere effektive Reichweite. ((Strlen * 8bit Zeichen) Kombinationen)

Allerdings würde ich nicht einen einzigen Wert für Überlagerung von mehr als ein / Typ / von Daten verwenden. Der Grund r / w / x Triplett von 3-Bit ints wäre wahrscheinlich die obere „praktische“ Grenze sein, nicht für die Raumeffizienzgründe, aber für die praktische Entwicklung Gründe.

(Php nutzt dieses System seine Fehlermeldungen zu steuern, und ich habe bereits festgestellt, dass es ein wenig over-the-top, wenn Sie Werte definieren müssen, wo PHP-Konstanten nicht ansässig sind und Sie haben die ganze Zahl von Hand zu erzeugen, und um ehrlich zu sein, wenn chmod nicht die ‚ugo + rwx‘ Stil-Syntax hat unterstützen würde ich nie verwenden will, weil ich nie die magischen Zahlen erinnern kann)

Der Instant Sie öffnen eine Konstanten-Tabelle zu Debug-Code zu knacken haben Sie wissen, sind zu weit gegangen.

Answer 5

Alt Faden, aber es ist erwähnenswert, dass es Fälle geben, erfordern aufgeblähte Bitmasken, zum Beispiel molekulare Fingerabdrücke, die oft als 1024-Bit-Arrays erzeugt werden, die wir in 32 Bigint Feldern gepackt haben (SQL Server nicht UInt32 unterstützt). Bitweise Operationen funktionieren - bis Tisch beginnt zu wachsen und Sie erkennen die Schwergängigkeit von separaten Funktionsaufrufe. Der binäre Datentyp funktionieren würde, wäre es nicht für T-SQL Verbot von Bit-Operatoren mit zwei Binäroperanden.

Answer 6

Zum Beispiel verwendet .NET Array von ganzen Zahlen als internen Speicher für ihre BitArray Klasse. Praktisch gibt es keinen anderen Weg, um.

Dass gesagt wird, in SQL finden Sie mehr als eine Spalte benötigen (oder die Blobs verwenden) alle Zustände zu speichern.

Answer 7

Sie markiert diese Frage SQL, so dass ich glaube, Sie mit der Dokumentation konsultieren müssen für die Datenbank, die Größe einer ganzen Zahl zu finden. Dann subtrahiert ein Bit für das Vorzeichen, nur um sicher zu sein.

Edit: Ihr Kommentar sagt, dass Sie MySQL verwenden. Die Dokumentation für MySQL 5.0 numerische Datentypen , dass die Staaten maximale Größe eines numerisch ist 64 oder 65 Ziffern. Das ist 212 Bits für 64 Stellen.

Beachten Sie, dass die Sprache Ihrer Wahl zu können, hat mit diesen Ziffern arbeiten, so können Sie trotzdem auf eine 64-Bit-Integer begrenzt werden.