Skośny system liczb binarnych

Skośny binarny system liczbowy to niestandardowy pozycyjny system liczbowy , w którym n -ta cyfra wnosi wartość ${\ Displaystyle 2 ^ {n + 1} -1}$ razy cyfra (cyfry są indeksowane od 0) zamiast ${\ displaystyle 2 ^ {n}}$ razy, jak to ma miejsce w systemie binarnym . Każda cyfra ma wartość 0, 1 lub 2. Liczba może mieć wiele skośnych reprezentacji binarnych. Na przykład liczbę dziesiętną 15 można zapisać jako 1000, 201 i 122. Każdą liczbę można zapisać jednoznacznie w kanonicznej postaci binarnej skośnej, w której występuje tylko co najwyżej jedno wystąpienie cyfry 2, która musi być najmniej znaczącą cyfrą różną od zera. W tym przypadku 15 jest zapisane kanonicznie jako 1000.

Przykłady

Kanoniczne binarne reprezentacje skośne liczb od 0 do 15 przedstawiono w poniższej tabeli:

Dziesiętny	Dwójkowy	Pochyl binarny	Potrójny
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 arytmetyczne

Zaletą skośnego binarnego jest to, że każda operacja inkrementacji może być wykonana z co najwyżej jedną operacją przenoszenia . Wykorzystuje to fakt, że ${\ Displaystyle 2 (2 ^ {n + 1} -1) + 1 = 2 ^ {n + 2} -1 }$ . Zwiększanie skośnej liczby binarnej odbywa się poprzez ustawienie jedynej dwójki na zero i zwiększenie następnej cyfry od zera do jednego lub od jednego do dwóch. Gdy liczby są reprezentowane przy użyciu formy kodowania długości serii jako połączone listy cyfr niezerowych, inkrementacja i dekrementacja mogą być wykonywane w stałym czasie.

Inne operacje arytmetyczne mogą być wykonywane przez przełączanie między skośną reprezentacją binarną a reprezentacją binarną.

Od skośnej reprezentacji binarnej do reprezentacji binarnej

$za$ pomocą pętli, obliczając kolejne wartości i dodając ją raz lub dwa razy dla każdego ${\ Displaystyle 2 ^ {n + 1}$ $n$ $displaystyle$ tak, że ta to odpowiednio 1 lub 2. Podana jest teraz bardziej wydajna metoda, z reprezentacją tylko bitową i jednym odejmowaniem.

Skośna liczba binarna postaci ${\ Displaystyle b_ {0} \ kropki b_ {n}}$ bez 2 i z $Displaystyle$ jest równa liczbie binarnej $0b_ {0} \ kropki b_ {n}}$ minus ${\ Displaystyle m}$ . Niech $^ {c}}$ $\ displaystyle$ $razy$ cyfrę powtórzoną . Skośna liczba binarna formularza ${\ Displaystyle 0 ^ {c_ {0}} 21 ^ {c_ {1}} 0b_ {0} \ kropki b_ {n}}$ z ${\ Displaystyle m}$ 1s jest równe liczba binarna ${\ Displaystyle 0 ^ {c_ {0} + c_ {1} + 2} 1b_ {0} \ kropki b_ {n}}$ minus ${\ Displaystyle m}$ .

Od reprezentacji binarnej do skośnej reprezentacji binarnej

Podobnie jak w poprzedniej sekcji, liczba binarna postaci $\$ $Displaystyle b_ {0} \ kropki b_ {n}}$ z równa się skośnej liczbie binarnej b ${\ displaystyle$ ${\ Displaystyle b_ {1} \ kropki b_ {n}}$ plus ${\ Displaystyle m}$ . Zauważ $,$ że ponieważ dodawanie nie jest zdefiniowane, dodanie zwiększeniu liczby ${\ displaystyle m}$ razy. Jednak $m}$ $displaystyle$ jest ograniczony logarytmem, przyrost zajmuje stały czas. Stąd przekształcenie liczby binarnej w liczbę binarną skośną przebiega w czasie liniowo względem długości liczby.

Aplikacje

Skośne liczby binarne zostały opracowane przez Eugene'a Myersa w 1983 r. Dla czysto funkcjonalnej struktury danych , która umożliwia operacje na abstrakcyjnym typie danych stosu , a także umożliwia wydajne indeksowanie sekwencji elementów stosu. Zostały one później zastosowane do skośnych stert dwumianowych , wariantu stert dwumianowych , które obsługują operacje wstawiania w najgorszym przypadku w stałym czasie.

Zobacz też

Notatki