Skev binärt talsystem

Det skeva binära talsystemet är ett icke-standardiserat positionssiffersystem där den n :e siffran bidrar med ett värde på $2^{n+1}-1$ gånger siffran (siffrorna indexeras från 0) istället för $2^{n}$ gånger som de gör i binär . Varje siffra har värdet 0, 1 eller 2. Ett tal kan ha många sneda binära representationer. Till exempel kan ett decimaltal 15 skrivas som 1000, 201 och 122. Varje nummer kan skrivas unikt i skev binär kanonisk form där det bara finns högst en instans av siffran 2, som måste vara den minst signifikanta icke-nollsiffran. I det här fallet skrivs 15 kanoniskt som 1000.

Exempel

Kanoniska sneda binära representationer av talen från 0 till 15 visas i följande tabell:

Decimal	Binär	Skev binär	Ternär
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

Aritmetiska operationer

Fördelen med skev binär är att varje inkrementoperation kan utföras med högst en överföringsoperation . Detta utnyttjar det faktum att $2(2^{n+1}-1)+1=2^{n+2}-1$ . Att öka ett skevt binärt tal görs genom att sätta de enda två till en noll och öka nästa siffra från noll till ett eller en till två. När siffror representeras med hjälp av en form av körlängdskodning som länkade listor av siffror som inte är noll, kan inkrementering och dekrementering utföras i konstant tid.

Andra aritmetiska operationer kan utföras genom att växla mellan den sneda binära representationen och den binära representationen.

Från sned binär representation till binär representation

Givet ett skevt binärt tal kan dess värde beräknas av en slinga, som beräknar de successiva värdena på $2^{n+1}-1$ och adderar det en eller två gånger för varje ${\ displaystyle n}$ så att ${\displaystyle n}:$ e siffran är 1 respektive 2. En mer effektiv metod ges nu, med endast bitrepresentation och en subtraktion.

Det sneda binära talet för formen $dots b_{n}}$ $0b_ {0}\dots b_{n}$ utan 2 och med $m$ är 1s lika med det binära talet minus $m$ . Låt $d^{c}$ representera siffran $d$ upprepad $c$ gånger. Det sneda binära talet i formen $0^{c_{0}}21^{c_{1}}0b_{0}\dots b_{n}$ med $m$ 1s är lika med det binära talet $0^{c_{0}+c_{1}+2}1b_{0}\dots b_{n}$ minus $m$ .

Från binär representation till skev binär representation

På samma sätt som i föregående avsnitt är det binära talet $b$ av formen $b_{0}\dots b_{n}$ med $m$ 1s lika med det sneda binära talet $b_{1}\dots b_{n}$ plus $m$ . Observera att eftersom addition inte är definierad, motsvarar addering av $m$ att man ökar antalet $m$ gånger. Men $m$ begränsas av logaritmen för $b$ och inkrementeringen tar konstant tid. Omvandling av ett binärt tal till ett skevt binärt tal löper därför linjärt i längden på talet.

Ansökningar

De skeva binära talen utvecklades av Eugene Myers 1983 för en rent funktionell datastruktur som tillåter operationer av den abstrakta stackdatatypen och även möjliggör effektiv indexering i sekvensen av stackelement. De användes senare för att skeva binomialhögar , en variant av binomialhögar som stöder insättningsoperationer i värsta fall i konstant tid.

Se även

Anteckningar