Código Natural/Listagens com representações: mudanças entre as edições
(→Comprimento 11: e maiores) |
m (Peter moveu Código natural/Listagens com representações para Código Natural/Listagens com representações: nme próprio) |
Edição atual tal como às 18h16min de 6 de janeiro de 2024
Nas tabelas abaixo são apresentadas amostragens de códigos naturais ordenados. Conjuntos de tamanhos crescentes, de X1, X2, ..., X8. A coluna count é um contador de linhas para o humano acompanhar em representação decimal a sequência, as colunas b4h e b16h são as representações em base4h e base16h respectivamente.
A coluna hInt é a representação "cache-length", descrita em ??. Como depende do tamanho máximo, a ilustração ficou com Smallint (16 bits) ao invés do usual Bigint (64 bits). Na prática, como o bit de sinal é perdido e o cache usa 4 bits, sobram 16-4-1=11 bits, que resulta no valor máximo 32763 (da bitstring "11111111111").
A coluna hidd é a representação "hidden bit", onde a inclusão à esquerda do dígito 1 na bitstring resulta em um valor decimal maior. Por exemplo as bitstrings 0
, 1
e 00
com o 1 na frente serão 10
, 11
e 100
, que em decimal serão 2, 3 e 4.
Código-fonte SQL usando a biblioteca de https://git.osm.codes/NaturalCodes/tree/main/src-sql
SELECT row_number() over() AS count, bitstring,
natcod.vBit_to_hSml( bitstring ) as "hInt",
natcod.vbit_to_hiddenBig( bitstring ) as hidd,
natcod.vbit_to_baseh(bitstring,4,true) as b4h,
natcod.vbit_to_baseh(bitstring,16,true) as b16h
FROM natcod.generate_vbit_series(8) t(bitstring);
Comprimento 1
X1: códigos naturais com no máximo 1 bit.
count | bitstring | hInt | hidd | b4h | b16h |
---|---|---|---|---|---|
0 |
|
0 | 1 | ||
1 | 0 |
1 | 2 | G | G |
2 | 1 |
16385 | 3 | Q | Q |
Comprimento 2
X2: códigos naturais com no máximo 2 bits.
count | bitstring | hInt | hidd | b4h | b16h |
---|---|---|---|---|---|
0 |
|
0 | 1 | ||
1 | 0 |
1 | 2 | G | G |
2 | 00 |
2 | 4 | 0 | H |
3 | 01 |
8194 | 5 | 1 | M |
4 | 1 |
16385 | 3 | Q | Q |
5 | 10 |
16386 | 6 | 2 | R |
6 | 11 |
24578 | 7 | 3 | V |
Comprimento 8
Abaixo listagem obtida de git.osm.codes/NaturalCodes/src/step91assert-p2_diff.sql com resultado completo em data/assert-p2_diff.txt.
count | bitstring | hidd | b4h | b16h |
---|---|---|---|---|
0 |
|
1 | ||
1 | 0 |
2 | G | G |
2 | 00 |
4 | 0 | H |
3 | 000 |
8 | 0G | J |
4 | 0000 |
16 | 00 | 0 |
5 | 00000 |
32 | 00G | 0G |
6 | 000000 |
64 | 000 | 0H |
7 | 0000000 |
128 | 000G | 0J |
8 | 00000000 |
256 | 0000 | 00 |
9 | 00000001 |
257 | 0001 | 01 |
10 | 0000001 |
129 | 000Q | 0K |
11 | 00000010 |
258 | 0002 | 02 |
12 | 00000011 |
259 | 0003 | 03 |
13 | 000001 |
65 | 001 | 0M |
14 | 0000010 |
130 | 001G | 0N |
15 | 00000100 |
260 | 0010 | 04 |
16 | 00000101 |
261 | 0011 | 05 |
17 | 0000011 |
131 | 001Q | 0P |
18 | 00000110 |
262 | 0012 | 06 |
19 | 00000111 |
263 | 0013 | 07 |
20 | 00001 |
33 | 00Q | 0Q |
21 | 000010 |
66 | 002 | 0R |
22 | 0000100 |
132 | 002G | 0S |
23 | 00001000 |
264 | 0020 | 08 |
24 | 00001001 |
265 | 0021 | 09 |
25 | 0000101 |
133 | 002Q | 0T |
26 | 00001010 |
266 | 0022 | 0a |
27 | 00001011 |
267 | 0023 | 0b |
28 | 000011 |
67 | 003 | 0V |
29 | 0000110 |
134 | 003G | 0Z |
30 | 00001100 |
268 | 0030 | 0c |
31 | 00001101 |
269 | 0031 | 0d |
32 | 0000111 |
135 | 003Q | 0Y |
33 | 00001110 |
270 | 0032 | 0e |
34 | 00001111 |
271 | 0033 | 0f |
35 | 0001 |
17 | 01 | 1 |
36 | 00010 |
34 | 01G | 1G |
37 | 000100 |
68 | 010 | 1H |
38 | 0001000 |
136 | 010G | 1J |
39 | 00010000 |
272 | 0100 | 10 |
40 | 00010001 |
273 | 0101 | 11 |
41 | 0001001 |
137 | 010Q | 1K |
42 | 00010010 |
274 | 0102 | 12 |
... | ... | ... | ... | ... |
244 | 01111000 |
376 | 1320 | 78 |
245 | 01111001 |
377 | 1321 | 79 |
246 | 0111101 |
189 | 132Q | 7T |
247 | 01111010 |
378 | 1322 | 7a |
248 | 01111011 |
379 | 1323 | 7b |
249 | 011111 |
95 | 133 | 7V |
250 | 0111110 |
190 | 133G | 7Z |
251 | 01111100 |
380 | 1330 | 7c |
252 | 01111101 |
381 | 1331 | 7d |
253 | 0111111 |
191 | 133Q | 7Y |
254 | 01111110 |
382 | 1332 | 7e |
255 | 01111111 |
383 | 1333 | 7f |
256 | 1 |
3 | Q | Q |
257 | 10 |
6 | 2 | R |
258 | 100 |
12 | 2G | S |
259 | 1000 |
24 | 20 | 8 |
260 | 10000 |
48 | 20G | 8G |
261 | 100000 |
96 | 200 | 8H |
262 | 1000000 |
192 | 200G | 8J |
263 | 10000000 |
384 | 2000 | 80 |
264 | 10000001 |
385 | 2001 | 81 |
265 | 1000001 |
193 | 200Q | 8K |
266 | 10000010 |
386 | 2002 | 82 |
... | ... | ... | ... | ... |
499 | 11111000 |
504 | 3320 | f8 |
500 | 11111001 |
505 | 3321 | f9 |
501 | 1111101 |
253 | 332Q | fT |
502 | 11111010 |
506 | 3322 | fa |
503 | 11111011 |
507 | 3323 | fb |
504 | 111111 |
127 | 333 | fV |
505 | 1111110 |
254 | 333G | fZ |
506 | 11111100 |
508 | 3330 | fc |
507 | 11111101 |
509 | 3331 | fd |
508 | 1111111 |
255 | 333Q | fY |
509 | 11111110 |
510 | 3332 | fe |
510 | 11111111 |
511 | 3333 | ff |
Comprimento 8 em level order
A coluna hidd proporciona a "Level order", que não é a ordem natural (lexicográfica) para uma hierarquia, mas proporciona intervalos contendo mesmo tamanho. Pode ser conseguido com a coluna hInt usando ORDER BY hInt&15, hInt
.
count | bitstring | hInt | hidd | b4h | b16h -------+-----------+-------+------+-----+------ 1 | 0 | 1 | 2 | G | G 2 | 1 | 16385 | 3 | Q | Q 3 | 00 | 2 | 4 | 0 | H 4 | 01 | 8194 | 5 | 1 | M 5 | 10 | 16386 | 6 | 2 | R 6 | 11 | 24578 | 7 | 3 | V 7 | 000 | 3 | 8 | 0G | J 8 | 001 | 4099 | 9 | 0Q | K 9 | 010 | 8195 | 10 | 1G | N 10 | 011 | 12291 | 11 | 1Q | P 11 | 100 | 16387 | 12 | 2G | S 12 | 101 | 20483 | 13 | 2Q | T 13 | 110 | 24579 | 14 | 3G | Z 14 | 111 | 28675 | 15 | 3Q | Y 15 | 0000 | 4 | 16 | 00 | 0 16 | 0001 | 2052 | 17 | 01 | 1 17 | 0010 | 4100 | 18 | 02 | 2 18 | 0011 | 6148 | 19 | 03 | 3 19 | 0100 | 8196 | 20 | 10 | 4 20 | 0101 | 10244 | 21 | 11 | 5 21 | 0110 | 12292 | 22 | 12 | 6 22 | 0111 | 14340 | 23 | 13 | 7 23 | 1000 | 16388 | 24 | 20 | 8 24 | 1001 | 18436 | 25 | 21 | 9 25 | 1010 | 20484 | 26 | 22 | a 26 | 1011 | 22532 | 27 | 23 | b 27 | 1100 | 24580 | 28 | 30 | c 28 | 1101 | 26628 | 29 | 31 | d 29 | 1110 | 28676 | 30 | 32 | e 30 | 1111 | 30724 | 31 | 33 | f 31 | 00000 | 5 | 32 | 00G | 0G 32 | 00001 | 1029 | 33 | 00Q | 0Q 33 | 00010 | 2053 | 34 | 01G | 1G 34 | 00011 | 3077 | 35 | 01Q | 1Q 35 | 00100 | 4101 | 36 | 02G | 2G ... 250 | 1111011 | 31495 | 251 | 331Q | fP 251 | 1111100 | 31751 | 252 | 332G | fS 252 | 1111101 | 32007 | 253 | 332Q | fT 253 | 1111110 | 32263 | 254 | 333G | fZ 254 | 1111111 | 32519 | 255 | 333Q | fY 255 | 00000000 | 8 | 256 | 0000 | 00 256 | 00000001 | 136 | 257 | 0001 | 01 257 | 00000010 | 264 | 258 | 0002 | 02 258 | 00000011 | 392 | 259 | 0003 | 03 259 | 00000100 | 520 | 260 | 0010 | 04 ... 495 | 11110000 | 30728 | 496 | 3300 | f0 496 | 11110001 | 30856 | 497 | 3301 | f1 497 | 11110010 | 30984 | 498 | 3302 | f2 498 | 11110011 | 31112 | 499 | 3303 | f3 499 | 11110100 | 31240 | 500 | 3310 | f4 500 | 11110101 | 31368 | 501 | 3311 | f5 501 | 11110110 | 31496 | 502 | 3312 | f6 502 | 11110111 | 31624 | 503 | 3313 | f7 503 | 11111000 | 31752 | 504 | 3320 | f8 504 | 11111001 | 31880 | 505 | 3321 | f9 505 | 11111010 | 32008 | 506 | 3322 | fa 506 | 11111011 | 32136 | 507 | 3323 | fb 507 | 11111100 | 32264 | 508 | 3330 | fc 508 | 11111101 | 32392 | 509 | 3331 | fd 509 | 11111110 | 32520 | 510 | 3332 | fe 510 | 11111111 | 32648 | 511 | 3333 | ff
Comprimento 11
Inteiros Smallint possuem 2 bytes (16 bits), como 1 bit é consumido pelo sinal (sempre positivo) e outros 4 bits pelo cache-length (comprimentos 0 a 11), restam 16-1-4=11 bits. Abaixo as representações decimal e binária deste formato, mostrando como o valor numérico (coluna hint_dec) segue exatamente a ordem lexicográfica.
bitstring | hint_dec | hint_bin -------------+----------+-------------------- | 0 | 0 00000000000 0000 0 | 1 | 0 00000000000 0001 00 | 2 | 0 00000000000 0010 000 | 3 | 0 00000000000 0011 0000 | 4 | 0 00000000000 0100 00000 | 5 | 0 00000000000 0101 000000 | 6 | 0 00000000000 0110 0000000 | 7 | 0 00000000000 0111 00000000 | 8 | 0 00000000000 1000 000000000 | 9 | 0 00000000000 1001 0000000000 | 10 | 0 00000000000 1010 00000000000 | 11 | 0 00000000000 1011 00000000001 | 27 | 0 00000000001 1011 0000000001 | 42 | 0 00000000010 1010 00000000010 | 43 | 0 00000000010 1011 00000000011 | 59 | 0 00000000011 1011 000000001 | 73 | 0 00000000100 1001 0000000010 | 74 | 0 00000000100 1010 00000000100 | 75 | 0 00000000100 1011 00000000101 | 91 | 0 00000000101 1011 0000000011 | 106 | 0 00000000110 1010 00000000110 | 107 | 0 00000000110 1011 00000000111 | 123 | 0 00000000111 1011 00000001 | 136 | 0 00000001000 1000 000000010 | 137 | 0 00000001000 1001 ... 1111111011 | 32618 | 0 11111110110 1010 11111110110 | 32619 | 0 11111110110 1011 11111110111 | 32635 | 0 11111110111 1011 11111111 | 32648 | 0 11111111000 1000 111111110 | 32649 | 0 11111111000 1001 1111111100 | 32650 | 0 11111111000 1010 11111111000 | 32651 | 0 11111111000 1011 11111111001 | 32667 | 0 11111111001 1011 1111111101 | 32682 | 0 11111111010 1010 11111111010 | 32683 | 0 11111111010 1011 11111111011 | 32699 | 0 11111111011 1011 111111111 | 32713 | 0 11111111100 1001 1111111110 | 32714 | 0 11111111100 1010 11111111100 | 32715 | 0 11111111100 1011 11111111101 | 32731 | 0 11111111101 1011 1111111111 | 32746 | 0 11111111110 1010 11111111110 | 32747 | 0 11111111110 1011 11111111111 | 32763 | 0 11111111111 1011
Comprimentos maiores
Abaixo o inicio da listagem de comprimento 20.
0 00 000 0000 00000 000000 0000000 00000000 000000000 0000000000 00000000000 000000000000 0000000000000 00000000000000 000000000000000 0000000000000000 00000000000000000 000000000000000000 0000000000000000000 00000000000000000000 00000000000000000001 0000000000000000001 00000000000000000010 00000000000000000011 000000000000000001 0000000000000000010 00000000000000000100 00000000000000000101 0000000000000000011 00000000000000000110 00000000000000000111 00000000000000001 000000000000000010 0000000000000000100 00000000000000001000 00000000000000001001 0000000000000000101 00000000000000001010 00000000000000001011 000000000000000011 ...