Šikmý binární číselný systém - Skew binary number system - Wikipedia

The zkosit binární číselný systém je nestandardní poziční číselný systém ve kterém nTato číslice přispívá hodnotou ${ displaystyle 2 ^ {n + 1} -1}$ krát číslice (číslice jsou indexovány od 0) místo ${ displaystyle 2 ^ {n}}$ časy jako v binární. Každá číslice má hodnotu 0, 1 nebo 2. Všimněte si, že číslo může mít mnoho zkosených binárních reprezentací. Například desítkové číslo 15 lze zapsat jako 1000, 201 a 122. Každé číslo lze zapsat jedinečně v zkosené binární kanonické formě, kde existuje pouze nejvíce jedna instance číslice 2, kterou musí být nejméně významné nenulová číslice. V tomto případě je 15 psáno kanonicky jako 1000.

Příklady

Kanonická zkosená binární reprezentace čísel od 0 do 15 jsou uvedena v následující tabulce:^[1]

Aritmetické operace

Výhodou zkoseného binárního souboru je, že každou operaci přírůstku lze provést maximálně jednou nést úkon. Toto využívá skutečnosti, že ${ displaystyle 2 (2 ^ {n + 1} -1) + 1 = 2 ^ {n + 2} -1}$. Zvýšení binárního čísla zešikmení se provádí nastavením pouze dvou na nulu a zvýšením další číslice od nuly k jedné nebo od jedné ke dvěma. Když jsou čísla reprezentována pomocí formy kódování délky běhu jako spojené seznamy nenulových číslic lze inkrementaci a dekrementaci provádět v konstantním čase.

Další aritmetické operace lze provádět přepínáním mezi zkosenou binární reprezentací a binární reprezentací.^[2]

Od šikmé binární reprezentace po binární reprezentaci

Vzhledem k šikmému binárnímu číslu lze jeho hodnotu vypočítat smyčkou, která vypočítá po sobě jdoucí hodnoty ${ displaystyle 2 ^ {n + 1} -1}$ a přidat to jednou nebo dvakrát pro každého ${ displaystyle n}$ takové, že ${ displaystyle n}$th číslice je 1 nebo 2 příslušně. Nyní je uvedena efektivnější metoda s pouze bitovou reprezentací a jedním odečtením.

Zkosené binární číslo formuláře ${ displaystyle b_ {0} tečky b_ {n}}$ bez 2 a s ${ displaystyle m}$ 1s se rovná binárnímu číslu ${ displaystyle 0b_ {0} tečky b_ {n}}$ mínus ${ displaystyle m}$. Nechat ${ displaystyle d ^ {c}}$ představuje číslici ${ displaystyle d}$ opakoval ${ displaystyle c}$ krát. Zkosené binární číslo formuláře ${ displaystyle 0 ^ {c_ {0}} 21 ^ {c_ {1}} 0b_ {0} tečky b_ {n}}$ s ${ displaystyle m}$ 1s se rovná binárnímu číslu ${ displaystyle 0 ^ {c_ {0} + c_ {1} +2} 1b_ {0} tečky b_ {n}}$ mínus ${ displaystyle m}$.

Od binární reprezentace po zkosenou binární reprezentaci

Podobně jako v předchozí části binární číslo ${ displaystyle b}$ formuláře ${ displaystyle b_ {0} tečky b_ {n}}$ s ${ displaystyle m}$ 1 s se rovná zkosenému binárnímu číslu ${ displaystyle b_ {1} tečky b_ {n}}$ Plus ${ displaystyle m}$. Všimněte si, že protože přidání není definováno, přidání ${ displaystyle m}$ odpovídá zvyšování počtu ${ displaystyle m}$ krát. Nicméně, ${ displaystyle m}$ je omezen logaritmem ${ displaystyle b}$ a přírůstek trvá konstantní čas. Proto transformace binárního čísla na zkosené binární číslo běží v čase lineárně v délce čísla.

Aplikace

Zkosená binární čísla byla vyvinuta Eugene Myers v roce 1983 čistě funkční datová struktura , který umožňuje provoz zásobník abstraktní datový typ a také umožňuje efektivní indexování do sekvence prvků zásobníku.^[3] Později byly použity naklonit binomické hromady, varianta binomické hromady které podporují operace vkládání nejhorších případů v konstantním čase.^[4]

Viz také

• Logika se třemi hodnotami
• Redundantní binární reprezentace
• n-ary šedý kód

Poznámky