Wie heißt das Speichern / Packen vieler Boolescher Zustände in eine Zahl?

55

Es ist eine Art einfache Komprimierung, bei der Sie eine numerische Variable verwenden, um viele boolesche / binäre Zustände zu speichern. Dabei wird die Verdopplung verwendet und jede Verdopplungszahl ist 1 + die Summe aller vorherigen.

Ich bin sicher, es muss eine alte, bekannte Technik sein. Ich würde gerne wissen, wie sie heißt, um richtig darauf zu verweisen. Ich habe mehrere Suchanfragen durchgeführt, um es zu beschreiben, aber nichts anderes als einige Blog-Artikel gefunden, bei denen die Artikelautoren dies anscheinend selbst herausgefunden haben und nicht wissen, wie sie es nennen sollen ( Beispiel 1 , Beispiel 2 ).

Zum Beispiel ist hier eine sehr einfache Implementierung, um das Konzept zu veranschaulichen:

packStatesIntoNumber () {
  let num = 0
  if (this.stateA) num += 1
  if (this.stateB) num += 2
  if (this.stateC) num += 4
  if (this.stateD) num += 8
  if (this.stateE) num += 16
  if (this.stateF) num += 32
  return num
}

unpackStatesFromNumber (num) {
  assert(num < 64)
  this.stateF = num >= 32; if (this.stateF) num -= 32
  this.stateE = num >= 16; if (this.stateE) num -= 16
  this.stateD = num >= 8; if (this.stateD) num -= 8
  this.stateC = num >= 4; if (this.stateC) num -= 4
  this.stateB = num >= 2; if (this.stateB) num -= 2
  this.stateA = num >= 1; if (this.stateA) num -= 1
}

Sie könnten auch bitweise Operatoren verwenden, das Parsen von Zahlen zur Basis 2, Aufzählungen ... Es gibt viel effizientere Möglichkeiten, dies zu implementieren. Ich interessiere mich für den Namen des Ansatzes im Allgemeinen.

user56reinstatemonica8
quelle
8
In C # gibt es enumsund sie können ein FlagsAttribut haben. Sie könnten Ihren Code viel einfacher machen.
Bernhard Hiller
12
Ich würde das "simulieren von Bitfeldern" nennen. Es ist fast immer eine schlechte Idee, es sei denn, Raumeffizienz ist überragend wichtig.
Kilian Foth
7
@KilianFoth A boolwird im Allgemeinen intern als 32-Bit-Ganzzahl gespeichert. Daher kann das Packen den Faktor 32 ausmachen. Das ist wirklich eine Menge. Ich meine, wir Programmierer sind immer bereit, die Hälfte unserer Ressourcen wegzuwerfen, aber ich zögere im Allgemeinen, 97% davon wegzuwerfen. Derartige Verschwendungsfaktoren können leicht den Unterschied zwischen der Ausführung wichtiger Anwendungsfälle und Speichermangel ausmachen.
cmaster
3
Historisch gesehen werden die typischen Bitmasken zum Deklarieren, Setzen und Abrufen von Werten verwendet. Das Verwenden von Schichten ist ungewöhnlich und nicht wirklich die beste Illustration des Ansatzes.
JimmyJames
3
@cmaster Der Grund, warum Bools auf diese Weise gespeichert werden, ist, dass die gemeinsame Nutzung eines einzelnen Speicherorts (32 oder 64 Bit auf heutigen Computern) für die Cache-Leistung sehr schlecht sein kann, wenn Sie dem Code der Maschinensprache nicht viel Aufmerksamkeit schenken. Wenn Sie eine wirklich große Anzahl von Bits haben, lohnt es sich wahrscheinlich, aber wenn nicht, ist es wahrscheinlich besser, die Bits nicht vorab zu optimieren und zu packen, wenn Sie bereit sind, sie an ein Netzwerk oder eine Festplatte zu übertragen.
Bill K

Antworten:

107

Es wird am häufigsten als Bitfeld bezeichnet , und ein anderer Begriff, den Sie häufig hören, sind Bitmasken , mit denen einzelne Bitwerte oder das gesamte Bitfeld auf einmal abgerufen oder festgelegt werden.

Viele Programmiersprachen haben dazu Hilfsstrukturen. Wie @BernhardHiller in den Kommentaren festhält, enthält C # Aufzählungen mit Flags . Java hat die EnumSet- Klasse.

Glorfindel
quelle
4
Ich würde "Bitfeld" so interpretieren, dass eine Sprachfunktion verwendet wird, mit der einzelne Bits Feldern einer Struktur zugewiesen werden können, anstatt dies manuell mit bitweisen Operatoren zu tun.
Peter Green
22
@PeterGreen Das wäre anders als die Standardinterpretation.
Eric
1
"Bit-Mapping" oder "Bit-Mapping" kann auch in diesem Fall angewendet werden, obwohl dies für Recordsets und die Array-Verarbeitung üblich ist. Beim Extrahieren gemeinsamer Elemente aus mehreren Mengen kann der Wert zerlegt werden, um Komponenten eines Verbundmodells zu identifizieren. Wir sagen dies sogar von oktalen Dateimodus-Ziffern. Bitmasken (beliebige Masken) sind in der Regel Filter (wie bei E / A-Ports und Datenrichtungsregistern).
McKenzm
1
In C # BitArraykönnen beliebig viele Bits gespeichert und indiziert werden (während Flags auf einen Integer-Typ beschränkt sind und als Masken verwendet werden sollen).
Luaan
Wahr; Ich habe gerade die beiden Strukturen erwähnt, mit denen ich am vertrautesten bin. Es gibt wahrscheinlich Dutzende, besonders in anderen Sprachen.
Glorfindel
20

Seltsame, ziemlich unterschiedliche Begriffe, aber ich sehe keinen, der mir sofort in den Sinn gekommen ist (und das steht im Titel Ihrer Frage!) - Bit-Packing ist das, was ich schon immer gehört habe.

Ich hatte gedacht, dass dies wirklich offensichtlich ist, aber seltsamerweise, wenn ich es google, scheint es ein Begriff zu sein, der weit verbreitet, aber nicht offiziell definiert ist Prozess). Das Suchen nach der Definition scheint zu dieser Seite zu führen:

http://www.kinematicsoup.com/news/2016/9/6/data-compression-bit-packing-101

Was für SO-Zwecke nicht besonders gut ist, aber die beste Definition / Beschreibung ist, die ich finden kann, einschließlich dieser kurzen Beschreibung: "Bit-Packing ist ein einfaches Konzept: Verwenden Sie so wenig wie möglich, um Daten zu speichern."

Bill K
quelle
Können Sie einige Referenzen nennen? Interessanter Begriff.
Greg Burghardt
13
Das Packen von Bits ist technisch korrekt, bezieht sich aber auch auf eine allgemeinere Sache als nur auf Boolesche Zustände - das Speichern von Daten im Allgemeinen in einer möglichst geringen Anzahl von Bits. Zum Beispiel könnte eine andere Verwendung bedeuten, ein charArray zu komprimieren, indem zwei chars in eins gesetzt werden int.
Izkata
@ GregBurghardt Sie wissen, es ist interessant. Ich habe beim Posten nicht darüber nachgedacht, weil der Begriff in den 80ern / 90ern so verbreitet war, als ich Programmieren in C und Assembler lernte - obwohl eine Google-Suche VIELE Erwähnungen findet, gibt es keine definitive Wikipedia-Seite dafür . Die erste Antwort in Google lautet wie folgt: "Bit-Packing ist ein einfaches Konzept: Verwenden Sie so wenig wie möglich, um Daten zu speichern." kinematicsoup.com/news/2016/9/6/…
Bill K
Das ist, als ich auch über Bit-Packing lernte, obwohl Sie viel verrückter werden können, als einfach unbenutzte Nullen in nominell ganzzahligen Werten umzuwandeln. Vor einigen Jahren bin ich auf ein System gestoßen, das einen seiner Parameter als 8-Bit-Float gespeichert hat. IIRC 5 Bits für eine Mantisse ohne Vorzeichen (alle Werte waren positiv, ohne dass das Vorzeichen explizit gespeichert werden muss) und 3 weitere Bits für einen Exponenten zur Basis 10. Zu der Zeit, als ich davon ausgegangen war, dass es sich um ein veraltetes Hardware-Problem handelte, das keinen Weg vorwärts hatte, konnte ich jedoch feststellen, dass beim maschinellen Lernen in letzter Zeit einige Arbeitslasten aus dem RP16 herausfielen.
Dan Neely
1
@DanNeely Diese Art von Dingen wird auch häufig von GPUs unterstützt - der Handel zwischen Präzision, Speicher und Berechnung ist dort ziemlich wichtig. Dies wurde auch beim GPU-basierten Computing sehr gut ausgenutzt.
Luaan
14

Es gibt viele verschiedene Begriffe, die verwendet werden, um dies zu beschreiben.

Am häufigsten werden die Bits "Bitflags" oder "Bitfelder" genannt.
(Es ist jedoch anzumerken, dass sich "Bitfelder" manchmal auf ein bestimmtes Merkmal der Sprachen C und C ++ beziehen, das zwar verwandt ist, aber nicht genau dasselbe.)

Die ganze Zahl selbst wird je nach Verwendung und Umständen auf verschiedene Weise entweder als "Bit-Array", "Bit-Set" oder "Bit-Vektor" bezeichnet.

In beiden Fällen erfolgt das Extrahieren der Bits aus der Bitmenge / dem Vektor / dem Array durch Verschieben und Maskieren.
(dh mit einer Bitmaske .)


Für einige Beispiele für jeden aktiven Begriff:


Es ist nicht wirklich relevant für die Frage, aber ich möchte sagen: Bitte verwenden Sie Addition und Subtraktion nicht, um Bits zu setzen und zu löschen, da diese Methoden fehleranfällig sind.
(Wenn Sie dies num += 1zweimal tun , entspricht das Ergebnis num += 2.)

Verwenden Sie stattdessen lieber die entsprechenden bitweisen Operationen, wenn Ihre gewählte Sprache diese bereitstellt:

packStatesIntoNumber ()
{
  let num = 0
  if (this.stateA) num |= 1
  if (this.stateB) num |= 2
  if (this.stateC) num |= 4
  if (this.stateD) num |= 8
  if (this.stateE) num |= 16
  if (this.stateF) num |= 32
  return num
}

unpackStatesFromNumber (num)
{
  this.stateF = ((num & 32) != 0);
  this.stateE = ((num & 16) != 0);
  this.stateD = ((num & 8) != 0);
  this.stateC = ((num & 4) != 0);
  this.stateB = ((num & 2) != 0);
  this.stateA = ((num & 1) != 0);
}
Pharap
quelle
1
this.stateF = (num & 32) ? true : falseusw. Sie müssen nicht mutieren, numwährend Sie die Werte extrahieren.
Roger Lipscombe
3
@ RogerLipscombe Guter Punkt, ich habe nicht wirklich durchgelesen, was der Code tat, sondern nur auf die Verwendung von +und reagiert -. Ich habe jetzt eins besser gemacht und != 0anstelle eines Ternären verwendet, was meiner Meinung nach prägnanter ist, während ich noch expclit bin.
Pharap