Teilmasken

Teilmasken bezeichnen in der Informatik Bitmasken, deren Eins-Bits eine Teilmenge der Eins-Bits einer gegebenen Maske M bilden. Formal heißt eine Bitmaske S eine Teilmaske von M, wenn S & M = S gilt. Das bedeutet, dass S entsteht, indem man bei M einige der 1-Bits auf 0 setzt. Die Anzahl der Teilmasken von M entspricht 2^(Anzahl der 1-Bits in M). Die Menge der Teilmasken bildet eine Teilmengenstruktur (eine Teilmengenordnung) unter der Inklusion.

Enumierung und Eigenschaften: Eine gängige Eigenschaft ist, dass jede Teilmaske durch das Auslassen einiger 1-Bits von M entsteht. Zur Iteration aller Teilmasken verwendet man üblicherweise einen Ablauf, der alle nicht-null Teilmasken erzeugt: sub = M; while (sub != 0) { ... sub = (sub - 1) & M; }. Dabei wird am Ende auch die Nullmaske berücksichtigt, falls gewünscht. Ein Beispiel: M = 13 (1101₂) hat drei 1-Bits. Seine Teilmasken sind {0, 1, 4, 5, 8, 9, 12, 13}.

Anwendungen: Teilmasken spielen eine zentrale Rolle in Algorithmen, die mit Mengen arbeiten oder Masken verwenden. Typische Anwendungen sind dynamische Programmierung über Teilmasken, Subset-Konvolution, Optimierungs- und Suchverfahren mit Bitrestriktionen sowie das Enumerieren aller möglichen Teilmengen eines gegebenen Sets.

Bezug und Kontext: Der Begriff ist eng mit dem Konzept der Masken in der Programmierung verbunden, bei dem Bits verwendet werden, um Eigenschaften oder Optionen zu repräsentieren. Teilmasken dienen dazu, zulässige Submengen konsistent mit einer Obermaske zu behandeln. See also: Maske, Bitmaske, Subset, SOS-DP.