bitsträngar

Bitsträngar är en grundläggande enhet inom datorvetenskap och informationsteori. En bitsträng består av en ändlig följd av tecknen 0 och 1. Längden betecknas |s| och kan vara noll; den tomma strängen ε har längden 0. Den uppsättning av alla bitsträngar med längd n betecknas {0,1}^n, och mängden av alla bitsträngar av godtycklig längd betecknas {0,1}^*.

Exempel: s = 0101 är en bitsträng av längd 4, och t = ε har längd 0. Den tomma strängen fungerar som identitet vid konkatenering: s concatenates with ε ger s. Denna notation används ofta i matematiska och teoretiska sammanhang.

Operativt kan bitsträngar användas på flera sätt. De kan indexeras, så att tecknet i position i hämtas; de kan konkateneras för att bilda längre strängar. Vid lika längd strängar kan man tillämpa per-bits logiska operationer, exempelvis AND (OCH), OR (ELLER), XOR (exklusivt eller) och NOT (icke) per bit. Prefix, suffix och substrings är vanliga begrepp vid analys av bitsträngar. Hammingdistans definierar antalet positioner där två bitsträngar skiljer sig och används inom felkorrigering och kodning.

Användningar av bitsträngar är centrala inom datarepresentation, lagring och kommunikation. De används för binär representation av tal och tecken, i kryptografi, felkontrollkoder och olika typer av koder inom kodningsteori. Bitsträngar utgör dessutom en grundläggande modell för beräkningar i digital elektronik och algoritmdesign.