Cadeia de bits
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, essa equivalência deixa de existir.
A rigor, portanto, a cadeia de bits não pode ser "promovida" a 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, expressando uma cadeia por linha e ordenando as linhas como se fossem palavras. 0 vem antes de 1, é uma convenção arbitrária porém estável e universal.
Não existe uma "convenção oficial" dos matemáticos, mas para efeitos de padronização local (neste artigo e em diversas apĺicações e implementações relevantes), podemos supor uma ordem preferível. Isso principalmente porque cadeias de bits são tipos de dados de mais baixo nível, não são munidos de muitos métodos ou operações. Em particular os bancos de dados relacionais (padrão SQL) que oferecem a cadeia de bit como tipo de dados, cumprem a convenção da ordem lexicográfica.
Exemplos de cadeias de "até k bits":
| k=1 | k=2 | k=3 | k=4 | k=12 |
|---|---|---|---|---|
1 bit:
0 1 |
Até 2 bits: 0 00 01 1 10 11 |
Até 3 bits: 0 00 000 001 01 010 011 1 10 100 101 11 110 111 |
Até 4 bits: 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 |
Até 12 bits:
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 000000001010 000000001011 0000000011 ... |
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 ... |
Dentro de um mesmo comprimento, a ordem lexicográfica coincide com a ordem numérica se as bitstrings forem transformadas em números. Ver exemplo na seção abaixo.
Números naturais e cadeias de comprimento 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 de todas as cadeias possíveis de comprimento k pode ser expresso como conjunto de todos os números naturais de zero a , acrescentando-se zeros à esquerda quando seu comprimento for menor que k.
Por exemplo com k=2 temos C2={00, 01, 10, 11}. Ignorando os zeros a esquerda, correspondem à representação binária dos números naturais zero até , ou seja, em decimal o conjunto C'2={0,1,2,3}⊂ℕ.
Essa correspondência, um isomorfismo entre cadeias de bits Ck e números naturais C'k, permite que computadores representam "números de k bits". Quando falamos de "inteiros de k bits", tipicamente 32 e 64 bits, há que se descontar o primeiro bit relativo ao sinal.
Exemplo, listando cadeias de bits (bitstrings) em level order com respectivos comprimentos e valores numéricos:
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 ...
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.
Problemas por ser tipo de baixo nível
A cadeia de bits é um tipo de dado de baixo nível, um típico "dado bruto". O oposto de um "cidadão de primeira classe", munido de diversos métodos, operações e conversões consistentes com outros tipos.
Na Computação, principalmente em linguagens modernas e fortemente tipadas como Scala, é possível definir tipos consistentes num crescer de complexidade, até que se possa considerar o tipo mais complexo como cidadão de primera classe. Na Matemática os conjuntos seriam os análogos dos dados brutos. O grupo, bem mais sofisticado, uma espécie de "conjunto orientado a objeto", seria análogo a tipo de dado de primeira classe.
Uma importante convenção para cadeias de bits surgiu em 1997 com o padrão ISO SQL (ISO/IEC 9075), mas em seguida foi cancelada com a versão SQL:2003. A última versão do padrão a suportar cadeias de bits foi a SQL:1999.
A flexibilidade e abrangência de uso da cadeia de bit pode ser vantajosa em algumas situações, mas na maioria dos casos, tanto matemáticos como programadores precisam de um bom cardápio de métodos e operações reusáveis, para não perder tempo reinventando e para evitar que alguma decisão afete a interoperabilidade num "ecossistema" maior de tipos já bem padronizados. Nas situações onde vale o princípio da convenção sobre a configuração, o melhor é "promover" a cadeia de bits a um cidadão de primeira classe. A AddressForAll sugere para os matemáticos a noção de código natural, como substituto da cadeia de bits em tal contexto. Um pouco mais delicada, a padronização do tipo NatCode em linguagens, requer submissão e revisão mais profunda das diversas comunidades mantenedoras das linguagens.
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: