Bitstrings

A bitstring is a finite sequence of bits, where each bit is 0 or 1. Bitstrings are the basic unit of information in binary form and are widely used in computing and digital communications. A bitstring of length n is sometimes written as {0,1}^n and is also called a binary string of length n; the empty string has length 0.

Bitstrings can be finite (most common) or infinite, in which case they form a stream. The number of distinct bitstrings of length n is 2^n. A specific bitstring can be interpreted as the binary representation of integers; for fixed length n there is a bijection between bitstrings of length n and integers from 0 to 2^n - 1.

Operations on bitstrings include concatenation (joining two bitstrings end to end) and bitwise operations such as AND, OR, XOR, and NOT. Substrings, prefixes, and suffixes are standard notions. Leading zeros affect length and representation and are significant when the length is part of the encoding.

Applications include data encoding and storage, network protocols, error detection and correction (parity bits, checksums), cryptography, and algorithmic representations of sets or sequences in programming and research. In digital hardware, bitstrings correspond to bit vectors used by registers and buses.

Bitstrings also figure in theoretical contexts, such as the study of formal languages and automata, where they serve as the binary alphabet. They relate to the binary numeral system and to broader ideas in computer science, including strings, bit vectors, and boolean functions.