Skośny system dwójkowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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} ... 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*(2^3 - 1) + 1*(2^4-1) + 1*(2^6-1) = 0*1 + 0*3 + 2*7 + 1*15 + 0*31 + 1*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[edytuj | edytuj kod]

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*1 + 2*3 + 1*7 + 1*15 + 2*31 = 2 + 6 + 7 + 15 + 62 = 92.

Początkowe liczby[edytuj | edytuj kod]

Zapis początkowych 15 liczb przedstawiono w tabeli:

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

Operacje dodawania i usuwania jedynki[edytuj | edytuj kod]

Pierwszym spostrzeżeniem jest, że 2*(2^{i+1} - 1) + 1 = 1*(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. 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Z powodu swoich właściwości, skośne liczby dwójkowe wykorzystuje się w językach funkcyjnych, do implementacji takich struktur danych jak list 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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]

Referencje[edytuj | edytuj kod]