Bitkette

In der Informatik ist eine Bitkette (auch Bitstring oder je nach Dimension Bitvektor bzw. Bitarray) eine (endliche) Folge von Zeichen aus dem kleinsten interessanten Alphabet Σ; dieses besteht aus zwei Zeichen, den Bits: Σ := {0,1}.

Während das Bitfeld vollständig in den Datentyp einer Binärzahl eingebettet ist und das einzelne Bit nur über sein programmiersprachliches Symbol anzusprechen ist, kommt beim Bitarray ein ganzzahliger Bit-Index (oder auch mehrere) hinzu. Bitkette und (1-dimensionaler) Bitvektor sind beim Zugriff auf ein einzelnes Bit konzeptionell ähnlich.

Obwohl die Sequenz von Binärziffern eines Bitvektors zur Bildung einer Binärzahl (beliebiger Größe) verwendet werden kann, hat ein Bitvektor zunächst nicht unmittelbar etwas mit einer Binärzahl zu tun – diese muss durch eine extra dafür vorgesehene Funktion gebildet werden.

Eine klassische Anwendung eines Bitvektors ist das Sieb des Eratosthenes zur Bestimmung von Primzahlen.

Bedeutungen

Beispiele für Bedeutungen, die den Bits oder Bitgruppen unterlegt werden können, sind wie beim Bitfeld:

• 1/0
• wahr/falsch bzw. true/false (Boolesche Variable)
• vorhanden/nicht vorhanden
• hell/dunkel usw.

So enthält das Dateiformat BMP für Schwarz-Weiß-Grafiken (neben Zusatzinformationen) ein 2-dimensionales Bitarray, bei dem jedes Bit einem Schwarz-Weiß-Pixel zugeordnet ist.

Jede Untermenge einer endlichen Menge {0, 1, 2, …, n−1} kann durch einen Bitvektor (oder eine Bitkette) der Länge n beschrieben werden und die Mengenoperationen Durchschnitt und Vereinigung durch logische Operationen auf Bitvektoren.

Kettenoperationen

Zu den Bitketten gehören typische Kettenoperationen, wie sie auch bei Zeichenketten vorkommen, z. B.

• Bilden (extrahieren) einer Teilkette
• Setzen einer Teilkette in die Kette
• Finden einer Teilkette in der Kette
• Verketten zweier Ketten
• Länge der Kette (in Bits)
• Lexikographischer Vergleich

Dazu kommen

• (komponentenweise) logische Operationen (UND, ODER, NICHT)
• Umwandeln in Binärzahl.

Die Extraktion einer Teilkette kann auch durch eine Verschiebung nach links und eine nach rechts bewerkstelligt werden. Die Verkettung zweier Ketten kann auch durch eine Verschiebung der ersten Kette nach links und eine logische ODER-Operation mit der zweiten Kette auf dem hereingezogenen Teil bewerkstelligt werden.

Programmiersprachliche Unterstützung

Programmiersprachliche Unterstützung für echte Bitarrays gibt es in PL/I. Bis auf das Umwandeln in eine beliebig lange Ganzzahl sind alle genannten Funktionen vorhanden.

In der Programmiersprache C++ gibt es den Datentyp bool, der aber nicht nur 1 Bit, sondern mindestens ein Byte verbraucht, und sich nicht zu den Ketten oder Feldern dieses Artikels aggregieren lässt.

Die Programmiersprachen C und C++, insbesondere C, präsentieren ein transparentes Speichermodell und erlauben im Bereich Arithmetik/Logik ein sehr maschinennahes Programmieren und volle Kontrolle bei Typumwandlungen.

Ein einzelnes Bit ist nicht direkt adressierbar, kann also nur mit binär-arithmetischen Mitteln dingfest gemacht werden – am einfachsten mit Hilfe von Shift-Befehlen. Mit diesen Befehlen wird die positionelle Wertigkeit eines Bits innerhalb der im Dualsystem dargestellten Binärzahl gezielt verändert, so dass jedem der 8 Bits ein eindeutiges Bit-Offset innerhalb der Byte-Adresse zugeordnet werden kann derart, dass die Shift-Befehle mit diesem Offset linear umgehen (ausführliche Beschreibung im Artikel Bitwertigkeit#Adressierung von Bits).

Für echte Bitarrays gibt es in C++ bspw. die Klassen:

• std::bitset mit zur Übersetzungszeit festzulegenden Grenzen für die Indizes
• dynamic_bitset der Boost-Bibliothek mit Indexgrenzen, deren Festlegung bis zur Laufzeit verzögert werden kann, und mit einigen komplexeren Bitkettenfunktionen

Andere Programmiersprachen:

• The Common Lisp HyperSpec von Common Lisp: Der ANSI Common Lisp Standard unterstützt Bit-Vektoren (engl. bit-vector) (s. Functions on Arrays of Bits).

Bitketten haben mit variabel langen Ganzzahlen viel gemeinsam, sofern diese auf dem Dualsystem aufbauen. Beispiele:

• Die Klasse java.math.BigInteger der Programmiersprache Java
• Die Klasse std.bigint der Programmiersprache D

Die Implementierungen vieler dieser Pakete sind vom Typ Little-Endian, was sich auf die Initialisierung, die Ein-/Ausgabe und die Umwandlung auswirken kann.

Füllbits

Da die kleinste adressierbare Einheit das Byte ist, das mehrere, i. d. R. acht, Bits umfasst, enthalten nicht vollständig gefüllte Bytes noch weitere Bits; diese werden Füllbits genannt (engl. padding bits oder slack bits).

Beim Arbeiten mit C empfiehlt es sich, die Füllbits explizit auf einen definierten Wert zu setzen, z. B. auf 0.

Darüber hinaus sind bei der Verkettung zweier Bitketten B1 und B2, wenn die Länge len1 der ersten Kette B1 nicht durch 8 teilbar ist, deren Füllbits durch die ersten Bits von B2 zu überschreiben; die Kette B2 muss also um len1 mod 8 Bits in die höheren Indizes verschoben werden.

Siehe auch

• Bitstrom

Literatur

• OS PL/I Checkout and Optimizing Compilers: Language Reference Manual. IBM Form GC33-0009 (1970)
• Paul Abrahams: The PL/I Programming Language. Courant Mathematics and Computing Laboratory, New York University, 1979 (iron-spring.com [PDF]). 
• IBM PL/I Compilers for z/OS, AIX, MVS and VSE
• Stephen Prata: C primer plus. 5th ed. Sams, Indianapolis, Ind 2007, ISBN 0-672-32696-5.