Cadeia de bits

Turing imaginava uma fita infinita de bits, para trabalhar a vontade nos primeiros computadores.

A noção de "cadeia de bits" (bit string) foi desenvolvida pela Lógica Matemática, principalmente no início dos anos 1900, e consagrada pelos trabalhos de Turing (1937) e Shannon (1948).

Ela difere de um número natural binário por permitir zeros à esquerda. Por exemplo o número natural binário 0001001 é equivalente a 1001, mas se dizemos que 0001001 é uma cadeia de bits, aí essa equivalência deixa de existir.

A rigor, portanto, a cadeia de bits não pode ser vista como número natural. Uma alternativa seria a interpretação como código natural, que não afeta a integridade da cadeia.

Notação

A cadeia de bits é intrinsecamente posicional, apesar de não ter uma semântica numérica associada. Por exemplo a cadeia 0101100 é considerada diferente de 0000111, justamente porque os zeros e uns ocupam posições diferentes em cada uma delas.

A título descritivo, para se referenciar bit a bit, convenciona-se que os bits da cadeia são indexados da direita para a esquerda, e iniciando pelo bit-zero.
PS: no PostgreSQL adota-se a convenção "da esquerda para a direita". A convenção aqui adotada é da notação posicional.

Não há necessidade de se associar a cadeia a um significado, a notação é meramente sintática, livre de semântica.

Comprimento

Toda cadeia de bits pode ter seu comprimento medido: é a quantidade de bits na cadeia. Uma cadeia de zero bits é uma cadeia vazia.

Em SQL e outras linguagens padronizadas, a função lenght(x) retorna a medida de tamanho da cadeia x. Exemplos: lenght("00")=2;  lenght("11")=2;  lenght("010101001")=9;  lenght("")=0.

O comprimento permite classificar cadeias: toda cadeia de comprimento c é elemento da "classe c", ou seja, o conjunto infinito de todas as cadeias de tamanho c.

Ordenação de cadeias de bits

A "ordem natural" da cadeia de bits é a lexicográfica, ou seja, colocando linha a linha e ordenando as linhas como se fossem palavras. "0" vem antes de "1", é uma convenção arbitrária porém madura, estável e universal. Exemplos de cadeias de "até k bits":

k=1	k=2	k=3	k=4	k=12
0 1	0 00 01 1 10 11	0 00 000 001 01 010 011 1 10 100 101 11 110 111	0 00 000 0000 0001 001 0010 0011 01 010 0100 0101 011 0110 0111 1 10 100 1000 1001 101 1010 1011 11 110 1100 1101 111 1110 1111	0 00 000 0000 00000 000000 0000000 00000000 000000000 0000000000 00000000000 000000000000 000000000001 00000000001 000000000010 000000000011 0000000001 00000000010 000000000100 000000000101 00000000011 000000000110 000000000111 000000001 0000000010 00000000100 000000001000 000000001001 00000000101 ...

Outras formas de ordenação

Diversas formas de ordenação são possíveis. Entre as mais utilizadas, depois da preorder (acima), as aplicações mais populares fazem uso da level order, ou "ordenação pelo comprimento primeiro, depois a ordem léxica".

Level order:

k=1	k=2	k=3	k=4	k=12
0 1	0 1 00 01 10 11	0 1 00 01 10 11 000 001 010 011 100 101 110 111	0 1 00 01 10 11 000 001 010 011 100 101 110 111 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111	0 1 00 01 10 11 000 001 010 011 100 101 110 111 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 00000 00001 ...

Curiosamente, dentro de um mesmo comprimento, a ordem lexicográfica coincide com a ordem numérica se as bitstrings forem transformadas em números. Exemplo:

  bitstring   | comprimento | val_numerico 
--------------+-------------+--------------
 0            |           1 |            0
 1            |           1 |            1
 00           |           2 |            0
 01           |           2 |            1
 10           |           2 |            2
 11           |           2 |            3
 000          |           3 |            0
 001          |           3 |            1
 010          |           3 |            2
 011          |           3 |            3
 100          |           3 |            4
 101          |           3 |            5
 110          |           3 |            6
 111          |           3 |            7
 0000         |           4 |            0
 0001         |           4 |            1
 0010         |           4 |            2
 0011         |           4 |            3
 0100         |           4 |            4
 0101         |           4 |            5
 0110         |           4 |            6
 0111         |           4 |            7
 1000         |           4 |            8
 1001         |           4 |            9
 1010         |           4 |           10
 ...
 00000        |           5 |            0
 00001        |           5 |            1
 00010        |           5 |            2
 00011        |           5 |            3
 ...

Números naturais e cadeias de tamanho fixo

Nos computadores, tradicionalmente, os números inteiros positivos são representados com zeros a esquerda para completar o número de bits desejado.

O conjunto $C_{k}$ de todas as cadeias possíveis de tamanho k pode ser expresso como conjunto de todos os números naturais de zero a $2_{k}-1$, acrescentando-se zeros à esquerda quando seu tamanho for menor que k.

Há um claro isomorfismo entre as cadeias de $C_{k}$ e os números naturais de zero a $2_{k}-1$.

Erros e adulterações em cadeias

No computador, por tradição (ou culpa de softwares mal projetados), pode-se erroneamente forçar que uma cadeia de bits de tamanho fixo seja interpretada como um número. Com a promoção dos códigos naturais a cidadões de primera classe, esse erro pode ser evitado.

Referências

Formalizações históricas:

• A. M. Turing (1937), “On Computable Numbers, with an Application to the Entscheidungsproblem”. urn:doi:10.1112/plms/s2-42.1.230.

• C. E. Shannon (1948), “A Mathematical Theory of Communication”. urn:doi:10.1002/j.1538-7305.1948.tb01338.x.

Uso prático:

• https://www.postgresql.org/docs/current/datatype-bit.html
• https://www.postgresql.org/docs/current/functions-bitstring.html