Ir para o conteúdo

Cadeia de bits: mudanças entre as edições

Cadeia de bits (ver código-fonte)

Edição das 00h04min de 3 de agosto de 2023

3 349 bytes adicionados ,  3 de agosto de 2023
rename Tamanho to Comprimento, e add examples
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.


== Tamanho ==
== Comprimento ==


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


A função ''lenght''(''x'') retorna a medida de tamanho da cadeia ''x''. Exemplos: ''lenght''(<code>00</code>)=2;&nbsp; ''lenght''(<code>11</code>)=2;&nbsp; ''lenght''(<code>010101001</code>)=9.   
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;&nbsp; ''lenght''("<code>11</code>")=2;&nbsp; ''lenght''("<code>010101001</code>")=9;&nbsp; ''lenght''("<code></code>")=0.   


O tamanho permite classificar cadeias: toda cadeia de tamanho ''k'' é elemento da "classe k", ou seja, o conjunto infinito de todas as cadeias de tamanho ''k''.
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 ==
Peter
2 583

edições

Disponível em “https://wiki.addressforall.org/doc/Especial:MobileDiff/2427”