Skośny system dwójkowy


Skośny system dwójkowy w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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 {\displaystyle i} -tej pozycji, licząc od prawej i zaczynając numerację od 0, odpowiada liczbie 2 i . {\displaystyle 2^{i}.}

W systemie skośnym z kolei cyfra na i {\displaystyle i} -tej pozycji odpowiada liczbie 2 i + 1 1. {\displaystyle 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 , {\displaystyle 2,} co odpowiada liczbie 2 ( 2 i + 1 1 ) . {\displaystyle 2(2^{i+1}-1).}

Podsumowując liczba jest zapisana przy pomocy ciągu cyfr d i { 0 , 1 , 2 } {\displaystyle 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 {\displaystyle d_{i}d_{i-1}...d_{3}d_{2}d_{1}d_{0}} ), a liczba którą reprezentują to x = i = 0 k d i ( 2 i + 1 1 ) . {\displaystyle x=\sum _{i=0}^{k}d_{i}(2^{i+1}-1).}

Na przykład liczba 92 , {\displaystyle 92,} może zostać zapisana jako 101200 s k e w , {\displaystyle 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. {\displaystyle 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,...

Spis treści

Niejednoznaczność reprezentacji i konwencja zapisu | 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 s k e w , {\displaystyle 21122_{skew},} ponieważ 2 1 + 2 3 + 1 7 + 1 15 + 2 31 = 2 + 6 + 7 + 15 + 62 = 92. {\displaystyle 2\cdot 1+2\cdot 3+1\cdot 7+1\cdot 15+2\cdot 31=2+6+7+15+62=92.}

Początkowe liczby | edytuj kod

Zapis początkowych 15 liczb przedstawiono w tabeli:

Operacje dodawania i usuwania jedynki | edytuj kod

Pierwszym spostrzeżeniem jest, że 2 ( 2 i + 1 1 ) + 1 = 1 ( 2 i + 2 1 ) {\displaystyle 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 s k e w + 1 = 102000 s k e w = 93. {\displaystyle 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 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 ) {\displaystyle O(\log x)}

Rzadkie liczby binarne | 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 {\displaystyle \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\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 | 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 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:

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

Przykład implementacji | 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 kod

Referencje | edytuj kod

Na podstawie artykułu: "Skośny system dwójkowy" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy