Skośny system dwójkowy

Skośny system dwójkowy, binarne liczby skośne (ang. skew binary numbers) – system liczbowy, w którym liczby są reprezentowane w podobny, lecz nie identyczny, sposób do liczb dwójkowych.

W systemie binarnym kolejne cyfry (0 lub 1, licząc od prawej strony, czyli od najmniej znaczących) odpowiadają kolejnym potęgom liczby 2 (jest to system pozycyjny z bazą 2). Tak więc cyfra 1 na $i$ -tej pozycji, licząc od prawej i zaczynając numerację od 0, odpowiada liczbie $2^{i}.$

W systemie skośnym z kolei cyfra na $i$ -tej pozycji odpowiada liczbie $2^{i+1}-1.$ Oprócz użycia cyfry 0 oraz 1, tak jak w zwykłych liczbach binarnych, pozwala się na użycie cyfry $2,$ co odpowiada liczbie $2(2^{i+1}-1).$

Podsumowując liczba jest zapisana przy pomocy ciągu cyfr $d_{i}\in \{0,1,2\}$ (zapisanych w kolejności malejącej $d_{i}d_{i-1}\dots d_{3}d_{2}d_{1}d_{0}$ ), a liczba którą reprezentują to $x=\sum _{i=0}^{k}d_{i}(2^{i+1}-1).$

Na przykład liczba $92,$ może zostać zapisana jako $101200_{skew},$ ponieważ

$2\cdot (2^{3}-1)+1\cdot (2^{4}-1)+1\cdot (2^{6}-1)=0\cdot 1+0\cdot 3+2\cdot 7+1\cdot 15+0\cdot 31+1\cdot 63=14+15+63=92.$

Kolejne cyfry (od prawej) odpowiadają liczbom: 1, 3, 7, 15, 31, 63, 127, 255, 1023, 2047,...

Niejednoznaczność reprezentacji i konwencja zapisu

W celu usunięcia niejednoznaczności (daną liczbę można zapisać na kilka sposobów), wprowadza się regułę: cyfra 2 może wystąpić tylko raz i musi być to cyfra, za którą jest tylko ciąg cyfr 0. Liczba 92 powyżej jest zapisana zgodnie z tą konwencją. Bez tej reguły można by napisać również: $21122_{skew},$ ponieważ $2\cdot 1+2\cdot 3+1\cdot 7+1\cdot 15+2\cdot 31=2+6+7+15+62=92.$

Początkowe liczby

Zapis początkowych 15 liczb przedstawiono w tabeli:

System dziesiętny	System dwójkowy	System skośny	System trójkowy
0	0	0	0
1	1	1	1
2	10	2	2
3	11	10	10
4	100	11	11
5	101	12	12
6	110	20	20
7	111	100	21
8	1000	101	22
9	1001	102	100
10	1010	110	101
11	1011	111	102
12	1100	112	110
13	1101	120	111
14	1110	200	112
15	1111	1000	120

Operacje dodawania i usuwania jedynki

Pierwszym spostrzeżeniem jest, że $2\cdot (2^{i+1}-1)+1=1\cdot (2^{i+2}-1)$

Tj. dodanie 1 do 2, powoduje pojawienie się 1 na następnym miejscu (przeniesienie) – o ile na następnej pozycji było wcześniej 0.

Tworzy to prostą regułę dodawania 1:

jeśli liczba w reprezentacji skośnej zawiera cyfrę 2 (zgodnie z konwencją jest tylko co najwyżej jedna taka cyfra), zmień ją na 0, a cyfrę następną (bardziej w lewo) zmień z 0 na 1, albo z 1 na 2. (przypadku z cyfrą 2 nie ma, ponieważ jest tylko co najwyżej jedna taka cyfra)
jeśli liczba w reprezentacji skośnej nie zawiera cyfry 2, zmień na pierwszej pozycji (najbardziej na prawo) cyfrę 0 na 1, albo 1 na 2.

W obu przypadkach, powstała liczba będzie zgodna z konwencją.

Przykład: $92+1=101200_{skew}+1=102000_{skew}=93.$

Warto zauważyć, że dodanie jedynki nie powoduje kaskadowego przenoszenia na dalsze pozycje, jak ma miejsce w normalnych systemach pozycyjnych w tym systemie dwójkowym.

Odejmowanie 1 wykonuje się w podobny (odwrotny) sposób.

Motywacja

Liczby skośne w reprezentacji rzadkiej umożliwiają dodawanie jedynki w czasie stałym. W systemie binarnym dodanie 1 do 1 powoduje wynik 0 na danej pozycji i przeniesienie 1 na następną pozycję, które z kolei znowu może wywołać nowe przeniesienia – w najgorszym przypadku trzeba przejść wszystkie cyfry, których jest $O(\log x)$

Rzadkie liczby binarne

Dodawanie (oraz odejmowanie) jedynki w liczbach skośnych zajmuje O(1) czasu, jednak należy znać pozycję cyfry 2 jeśli występuje. Można oprócz liczby pamiętać gdzie ostatnio została zapisana cyfra 2. Jednak w przypadku języków funkcyjnych, nawet ze znajomością pozycji k nie da się dojść do tego elementu w czasie stałym jeśli liczba jest reprezentowana jako lista jedno kierunkowa (trzeba przejść k elementów, których pesymistycznie może być $\log _{2}(x)+1$ ). W celu łatwego dostępu, liczbę zapisuje się w postaci listy w której początek listy odpowiada cyfrom mniej znaczącym (normalnie prawa strona zapisu).

 [0, 0, 2, 1, 0, 1] + 1 = [0, 0, 0, 2, 0, 1]   = 2∙15 + 1∙63 = 93

W tym celu używa się reprezentacji rzadkiej (można ją też zastosować do innych systemów liczbowych). W liście nie przechowuje się elementów równych 0, a oprócz cyfr, przechowuje się wagi (lub pozycje). Cyfrę dwa przechowuje się jako podwójna cyfra 1.

 92 = [7, 7, 15, 63]

 92 + 1 = [7, 7, 15, 63] + 1 = [7+7+1, 15, 63] = [15, 15, 63] = 93

Zamiast wag można alternatywnie przechowywać wykładniki: 92 = [2, 2, 3, 5]. 93 = [3, 3, 5]. W celu oszczędności miejsca (obie reprezentacje są sobie równoważne).

Umożliwia to wykonywanie operacji inkrementacji (dodania 1) oraz dekrementacji (odjęcie 1), w czasie stałym, niezależnie od wielkości liczby.

Zastosowania

Z powodu swoich właściwości, skośne liczby dwójkowe wykorzystuje się w językach funkcyjnych, do implementacji takich struktur danych jak listy o dostępnie swobodnym. Operacje na takich listach mają złożoność przedstawioną w poniższej tabelce w porównaniu do innych funkcyjnych struktur:

Operacja	Lista	Zrównoważone BST	Liczby skośne
head (odczyt pierwszego elementu listy)	$O(1)$	$O(\log n)$	$O(1)$
cons (konstrukcja nowej listy z dodanym nowym pierwszym elementem)	$O(1)$	$O(\log n)$	$O(1)$
tail (konstrukcja nowej listy bez pierwszego elementu)	$O(1)$	$O(\log n)$	$O(1)$
index (i-ty element)	$O(n)$ – pesymistycznie	$O(\log n)$	$O(\log n)$

Liczby skośne mogą być również użyte do implementacji kolejek z dostępem swobodnym w językach funkcyjnych.

Przykład implementacji

Przykład operacji dodawania oraz konwersji na liczbę lub notację pozycyjną (implementacja w języku programowania Erlang). Używa formatu rzadkiej notacji wykładnikowej, np. 92 = [2,2,3,5].

zero() -> [].

% Operacja inc wykonuje się w czasie stałym!
inc([X,X|T]) -> [X+1|T];
inc([X|T])   -> [0,X|T];
inc([])      -> [0].

% [2,2,3,5] -> "101200".
to_display([]) -> [$0];
to_display(L)  -> to_display(L, [], false, 0).

to_display([X,X|T], Acc, _, X)  -> to_display(T, [$2 | Acc], false, X+1);
to_display([X|T], Acc, _, X)    -> to_display(T, [$1 | Acc], false, X+1);
to_display([_|_T]=L, Acc, _, X) -> to_display(L, [$0 | Acc], true, X+1);
to_display([], Acc, true, _X)   -> [$1 | Acc];
to_display([], Acc, false, _X)  -> Acc.

% [2,2,3,5] -> [7,7,15,63].
to_exps(L) -> [ (1 bsl (X+1)) - 1 || X <- L ].

% [7,7,15,63] -> "63+15+7+7".
to_sum([]) -> "0";
to_sum(L) -> string:join([ integer_to_list(P) || P <- to_exps(L) ], "+").

% [2,2,3,5] -> 92.
to_number(L)  -> lists:foldl(fun(X, Acc) -> Acc +  ((1 bsl (X+1)) - 1) end, 0, L).
%to_number2(L) -> lists:sum(to_exps(L)). % alternatywnie

% pokazuje pierwsze N liczb
first(N) -> lists:foldl(fun(I, X) ->
      io:format("~p:   \t~p     \t= ~s        \t= ~p     \t= ~s_skew~n", [I-1, X, to_sum(X), to_number(X), to_display(X)]),
      inc(X)
   end, zero(), lists:seq(1, N)).

Wynik działania:

 first(101).
 0:    []              = 0             = 0             =      0_skew
 1:    [0]             = 1             = 1             =      1_skew
 2:    [0,0]           = 1+1           = 2             =      2_skew
 3:    [1]             = 3             = 3             =     10_skew
 4:    [0,1]           = 3+1           = 4             =     11_skew
 5:    [0,0,1]         = 3+1+1         = 5             =     12_skew
 6:    [1,1]           = 3+3           = 6             =     20_skew
 7:    [2]             = 7             = 7             =    100_skew
 8:    [0,2]           = 7+1           = 8             =    101_skew
 9:    [0,0,2]         = 7+1+1         = 9             =    102_skew
 10:   [1,2]           = 7+3           = 10            =    110_skew
 11:   [0,1,2]         = 7+3+1         = 11            =    111_skew
 12:   [0,0,1,2]       = 7+3+1+1       = 12            =    112_skew
 13:   [1,1,2]         = 7+3+3         = 13            =    120_skew
 14:   [2,2]           = 7+7           = 14            =    200_skew
 15:   [3]             = 15            = 15            =   1000_skew
...
 90:   [0,0,1,2,3,5]   = 63+15+7+3+1+1 = 90            = 101112_skew
 91:   [1,1,2,3,5]     = 63+15+7+3+3   = 91            = 101120_skew
 92:   [2,2,3,5]       = 63+15+7+7     = 92            = 101200_skew
 93:   [3,3,5]         = 63+15+15      = 93            = 102000_skew
 94:   [4,5]           = 63+31         = 94            = 110000_skew
 95:   [0,4,5]         = 63+31+1       = 95            = 110001_skew
 96:   [0,0,4,5]       = 63+31+1+1     = 96            = 110002_skew
 97:   [1,4,5]         = 63+31+3       = 97            = 110010_skew
 98:   [0,1,4,5]       = 63+31+3+1     = 98            = 110011_skew
 99:   [0,0,1,4,5]     = 63+31+3+1+1   = 99            = 110012_skew
 100:  [1,1,4,5]       = 63+31+3+3     = 100           = 110020_skew

Zobacz też

Referencje

Wykład z programowania funkcyjnego z implementacją list opartych na liczbach skośnych w języku Standard ML