www.wikidata.de-de.nina.az

Bitkette In der Informatik ist eine auch Bitstring oder je nach Dimension Bitvektor bzw Bitarray eine endliche Folge von

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 Bearbeiten

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 Bearbeiten

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

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 Bearbeiten

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:

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

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 Bearbeiten

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 Bearbeiten

Literatur Bearbeiten

  • 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 S dieses besteht aus zwei Zeichen den Bits S 0 1 Wahrend das Bitfeld vollstandig in den Datentyp einer Binarzahl eingebettet ist und das einzelne Bit nur uber 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 ahnlich Obwohl die Sequenz von Binarziffern eines Bitvektors zur Bildung einer Binarzahl beliebiger Grosse verwendet werden kann hat ein Bitvektor zunachst nicht unmittelbar etwas mit einer Binarzahl zu tun diese muss durch eine extra dafur vorgesehene Funktion gebildet werden Eine klassische Anwendung eines Bitvektors ist das Sieb des Eratosthenes zur Bestimmung von Primzahlen Inhaltsverzeichnis 1 Bedeutungen 2 Kettenoperationen 3 Programmiersprachliche Unterstutzung 4 Fullbits 5 Siehe auch 6 LiteraturBedeutungen BearbeitenBeispiele fur Bedeutungen die den Bits oder Bitgruppen unterlegt werden konnen sind wie beim Bitfeld 1 0 wahr falsch bzw true false Boolesche Variable vorhanden nicht vorhanden hell dunkel usw So enthalt das Dateiformat BMP fur Schwarz Weiss Grafiken neben Zusatzinformationen ein 2 dimensionales Bitarray bei dem jedes Bit einem Schwarz Weiss Pixel zugeordnet ist Jede Untermenge einer endlichen Menge 0 1 2 n 1 kann durch einen Bitvektor oder eine Bitkette der Lange n beschrieben werden und die Mengenoperationen Durchschnitt und Vereinigung durch logische Operationen auf Bitvektoren Kettenoperationen BearbeitenZu den Bitketten gehoren 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 Lange der Kette in Bits Lexikographischer VergleichDazu kommen komponentenweise logische Operationen UND ODER NICHT Umwandeln in Binarzahl 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 Unterstutzung BearbeitenProgrammiersprachliche Unterstutzung fur 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 lasst Die Programmiersprachen C und C insbesondere C prasentieren 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 binar 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 Binarzahl gezielt verandert 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 ausfuhrliche Beschreibung im Artikel Bitwertigkeit Adressierung von Bits Fur echte Bitarrays gibt es in C bspw die Klassen std bitset mit zur Ubersetzungszeit festzulegenden Grenzen fur die Indizes dynamic bitset der Boost Bibliothek mit Indexgrenzen deren Festlegung bis zur Laufzeit verzogert werden kann und mit einigen komplexeren BitkettenfunktionenAndere Programmiersprachen The Common Lisp HyperSpec von Common Lisp Der ANSI Common Lisp Standard unterstutzt 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 DDie Implementierungen vieler dieser Pakete sind vom Typ Little Endian was sich auf die Initialisierung die Ein Ausgabe und die Umwandlung auswirken kann Fullbits BearbeitenDa die kleinste adressierbare Einheit das Byte ist das mehrere i d R acht Bits umfasst enthalten nicht vollstandig gefullte Bytes noch weitere Bits diese werden Fullbits genannt engl padding bits oder slack bits Beim Arbeiten mit C empfiehlt es sich die Fullbits explizit auf einen definierten Wert zu setzen z B auf 0 Daruber hinaus sind bei der Verkettung zweier Bitketten B1 und B2 wenn die Lange len1 der ersten Kette B1 nicht durch 8 teilbar ist deren Fullbits durch die ersten Bits von B2 zu uberschreiben die Kette B2 muss also um len1 mod 8 Bits in die hoheren Indizes verschoben werden Siehe auch BearbeitenBitstromLiteratur BearbeitenOS 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 Abgerufen von https de wikipedia org w index php title Bitkette amp oldid 207061241