2 532
edições
(15 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) | |||
Linha 3: | Linha 3: | ||
A noção de "cadeia de bits" ([[wikipedia:bit string|''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). | A noção de "cadeia de bits" ([[wikipedia:bit string|''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 [[wikipedia:Natural number|número natural]] [[wikipedia:Binary number|binário]] por permitir zeros à esquerda. Por exemplo o número natural binário <code> | Ela difere de um [[wikipedia:Natural number|número natural]] [[wikipedia:Binary number|binário]] por permitir zeros à esquerda. Por exemplo o número natural binário <code>0001001</code> é equivalente a <code>1001</code>, mas se dizemos que <code>0001001</code> é uma ''cadeia de bits'', essa equivalência deixa de existir. | ||
A rigor, portanto, a cadeia de bits não | A rigor, portanto, a cadeia de bits não pode ser "promovida" a [[wikipedia:Natural number|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 <code>0101100</code> é considerada diferente de <code>0000111</code>, 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. <br/>PS: no [https://www.postgresql.org/docs/current/functions-bitstring.html PostgreSQL] adota-se a convenção "da esquerda para a direita". A convenção aqui adotada é da notação posicional. | |||
=== Números | 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 [[wikipedia:SQL|SQL]] e outras linguagens padronizadas, a função ''lenght''(''x'') retorna a medida de tamanho da cadeia ''x''. Exemplos: ''lenght''("<code>00</code>")=2; ''lenght''("<code>11</code>")=2; ''lenght''("<code>010101001</code>")=9; ''lenght''("<code></code>")=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 [[wikipedia:Lexicographic order|lexicográfica]], ou seja, expressando uma cadeia por linha e ordenando as linhas como se fossem palavras. '''<code>0</code> vem antes de <code>1</code>''', é 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 ([[wikipedia:SQL|padrão SQL]]) que oferecem a [https://www.postgresql.org/docs/current/datatype-bit.html 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 | |||
|- | |||
|<small>1 bit:</small> | |||
0 | |||
1 | |||
|<small>Até<br/>2 bits:</small> | |||
0 | |||
00 | |||
01 | |||
1 | |||
10 | |||
11 | |||
|<small>Até<br/>3 bits:</small> | |||
0 | |||
00 | |||
000 | |||
001 | |||
01 | |||
010 | |||
011 | |||
1 | |||
10 | |||
100 | |||
101 | |||
11 | |||
110 | |||
111 | |||
|<small>Até<br/>4 bits:</small> | |||
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 | |||
|<small>Até 12 bits:</small> | |||
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. | 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 <math> | O conjunto <math>C_k</math> de todas as cadeias possíveis de comprimento ''k'' pode ser expresso como conjunto de todos os números naturais de zero a <math>2^k-1</math>, acrescentando-se zeros à esquerda quando seu comprimento for menor que ''k''. <br/>Por exemplo com ''k''=2 temos ''C''<sub>2</sub>={<code>00</code>, <code>01</code>, <code>10</code>, <code>11</code>}. Ignorando os zeros a esquerda, correspondem à representação binária dos números naturais zero até <math>2^1-1=3</math>, ou seja, em decimal o conjunto ''C'''<sub>2</sub>={0,1,2,3}⊂ℕ. | ||
Essa correspondência, um isomorfismo entre cadeias de bits ''C''<sub>k</sub> e números naturais ''C'''<sub>k</sub>, 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 (''bitstring''s) em ''level order'' com respectivos comprimentos e valores numéricos: | |||
<pre> | |||
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 | |||
... | |||
</pre> | |||
=== 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 [[wikipedia:First-class citizen|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 [[wikipedia:Scala (programming language)|Scala]], é possível definir tipos consistentes num crescer de complexidade, até que se possa considerar o tipo mais complexo como [[wikipedia:First-class citizen|cidadão de primera classe]]. Na Matemática os [[wikipedia:Set theory|conjuntos]] seriam os análogos dos dados brutos. O [[wikipedia:Group theory|grupo]], bem mais sofisticado, uma espécie de "conjunto [[wikipedia:Object-oriented programming|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 [[wikipedia:ISO/IEC 9075|ISO SQL]] (ISO/IEC 9075), mas em seguida foi cancelada com a versão [[wikipedia:SQL:2003|SQL:2003]]. A última versão do padrão a suportar cadeias de bits foi a [[wikipedia:SQL:1999|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 [[wikipedia:Convention over configuration|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 == | == Referências == | ||
C. E. Shannon (1948), “A Mathematical Theory of Communication”. [https://doi.org/10.1002/j.1538-7305.1948.tb01338.x urn:doi:10.1002/j.1538-7305.1948.tb01338.x]. | Formalizações históricas: | ||
* A. M. Turing (1937), “On Computable Numbers, with an Application to the Entscheidungsproblem”. [https://doi.org/10.1112/plms/s2-42.1.230 urn:doi:10.1112/plms/s2-42.1.230]. | |||
* C. E. Shannon (1948), “A Mathematical Theory of Communication”. [https://doi.org/10.1002/j.1538-7305.1948.tb01338.x 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 | |||
[[Categoria:Conceitos]] | [[Categoria:Conceitos]] |
edições