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 -tej pozycji, licząc od prawej i zaczynając numerację od 0, odpowiada liczbie
W systemie skośnym z kolei cyfra na -tej pozycji odpowiada liczbie Oprócz użycia cyfry 0 oraz 1, tak jak w zwykłych liczbach binarnych, pozwala się na użycie cyfry co odpowiada liczbie
Podsumowując liczba jest zapisana przy pomocy ciągu cyfr (zapisanych w kolejności malejącej ), a liczba którą reprezentują to
Na przykład liczba może zostać zapisana jako ponieważ
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ż: ponieważ
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
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:
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
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ć ). 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) | |||
cons (konstrukcja nowej listy z dodanym nowym pierwszym elementem) | |||
tail (konstrukcja nowej listy bez pierwszego elementu) | |||
index (i-ty element) | – pesymistycznie |
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