[en] English version

Blog

Vize dokonalého uložení čísla

Článek vložen 23. 10. 2002 14:10:00

Existuje jednoduchý způsob, jak uložit číslo nezávisle na velikosti slova

       Jako hlavní princip mého nového digitálního formátu XBFF slouží jistý systém ukládání čísel, známý většině programátorů z kódování znaků UTF8. Princip je tudíž jednoduchý a již dlouho známý.

       Základem celého systému je BIT. Bit je základní jednotka informace, která je zcela logická a nevyvratitelná. Běžně se 8 bitů seskupí do bajtu, což je v současné době nejpoužívanější základní jednotka počítačové informace. Jeden bajt přenáší hodnotu z intervalu <0..255>. Kdo však určil, že bitů bude zrovna 8? Proč ne 4? Nebo 16, či ještě více? Ačkoli se zdá být 8  bitů akorát, není možné vyloučit, že by se toto mohlo někdy změnit. Abstrahujeme-li od organizace bitů do bajtů, lze ukládat čísla jistým jednoduchým způsobem.

       Uvažujme jako základní interval přirozená čísla včetně 0. Uvažujme nyní nekonečný bitový proud, který nese číslo. Způsob je prostý – číslo je určeno počtem bitů jednoho druhu. Zvolme například bit 1 jako nositel informace a 0 jako terminální bit. Pak čísla vypadají takto…

0          0
1          10
2          110
3          1110
4          11110

       Lze vidět, že tento způsob, jakkoli je prostý, zbytečně plýtvá místem (možná vám to připomene něco z oblasti komprese). Domnívám se, že tento způsob je ale naprosto logický, zatím bez formálního důkazu. Možná je na čase, abych si zapsal předmět, kde se přednáší teorie informace. Možná tu totiž plácám něco, co je již dávno světu známé. Pro své účely jsem tento způsob ukládání označil jako BNatural datové šířky 0. Ačkoli zde na první pohled není vidět žádná souvislost (alespoň já jsem ji neviděl), jedná se skutečně o platné označení. Připomenu princip ukládání čísla BNatural v jeho základní šířce 7 v pohledu, který více osvětlí podobnost.

0xxxxxxx
10xxxxxx xxxxxxxx
110xxxxx xxxxxxxx xxxxxxxx

       Základní tvar je 0xxxxxxx, kde x představují datové bity určené pro uložení vlastní hodnoty. Další tvar je 10xxxxxx xxxxxxxx, přičemž k hodnotě určené bity x se přičítá 80h. Podstatné je v tomto případě rekurzivní rozšiřování, tedy 11111111 nnnnnnnn ((N+9)*7)x a přičítá se Sum{I in 1..<N+9>} (2^(7*I)). N představuje další číslo typu BNatural stejné šířky vyjádřené pomocí bitů “n”, které se mohou také rozšiřovat. Tento výpočet lze zobecnit na libovolnou datovou šířku a to takto:

DŠ – datová šířka
PB – počet bitů 1 shora v prvním slově délky (DŠ+1) bitů
RH – rozšiřující hodnota

- počet datových bitů: (DŠ*(PB+1+N))
- přičítaná hodnota: Sum{I in <1.. PB+1+N >} (2^(DŠ*I))

Pro PB =< DŠ není RH přítomna a její hodnota je 0. Když nyní zvolíme DŠ = 0, lze vidět, že pokud je první bit 1, rozšiřuje se číslo o další bit díky RH a hodnota se zvyšuje o 1.

       Existuje mnohem jednodušší způsob, který je také „ve své nulové variantě“ schodný. Mě se ale nelíbí:

0xxxxxxx
1xxxxxxx 0xxxxxxx
1xxxxxxx 1xxxxxxx 0xxxxxxx
1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx

Nelíbí se mi proto, že se musí provádět datové posuny. Srovnejte pro datovou šířku 1:

Způsob jedna:

0          00
1          01
2          1000
3          1001
4          1010
5          1011
6          110000
7          110001
8          110010
9          110011
10        110100
11        110101
12        110110
13        110111

Způsob dvě:

0          00
1          01
2          1000
3          1001
4          1100
5          1101
6          101000
7          101001
8          101100
9          101101
10        111000
11        111001
12        111100
13        111101

No vidíte to? Ne? Tak dobře – moc to vidět nejde, ale těch posunů je tam fakt víc. Honba za dokonalostí pokračuje…

<< Předchozí článek  Následující článek >>