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 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

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\cdot15 + 1\cdot63 = 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 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)
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

Zobacz też

Referencje

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

Witaj

Uczę się języka hebrajskiego. Tutaj go sobie utrwalam.

Źródło

Zawartość tej strony pochodzi stąd.

Odsyłacze

narzędzia marketingowe meble biurowe warszawa zobacz jak wyglada top lista oraz inne treserzy.eu

Podziel się