2 583
edições
mSem resumo de edição |
(rename Tamanho to Comprimento, e add examples) |
||
Linha 14: | Linha 14: | ||
Não há necessidade de se associar a cadeia a um significado, a notação é meramente sintática, livre de semântica. | 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 | 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 | 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: | |||
<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> | |||
== Números naturais e cadeias de tamanho fixo == | == Números naturais e cadeias de tamanho fixo == |
edições