Código Natural/Listagens com representações
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 ...