Binært tallsystem

Det binære tallsystem (også totallsystemet) representerer numeriske verdier ved å bruke to symboler, som oftest sifrene 0 og 1.

Mer nøyaktig, er det binære tallsystem et posisjonssystem med grunntall to. På grunn av dens relative enkle implementasjon i elektroniske kretser blir totallsystemet brukt internt i så å si alle moderne datamaskiner.

Historie

Den første kjente beskrivelse av et totallsystem ble gjort av den indiske matematikeren Pingala i sin Chhandah-shastra, og er tidsfestet til det femte eller det andre århundret f.Kr. Pingala beskrev det binære tallsystem i sammenheng med en opplisting av vediske meter med korte eller lange vokaler. Ifølge den indiske tradisjon er Pingala den yngre broren til grammatikeren Panini.

Selv om den britiske filosofoen Francis Bacon tidligere hadde beskrevet et utviklet system for skjult binær enkoding til bruk i kryptering, ble det moderne binære totallsystem først fullt ut dokumentert av Gottfried Leibniz i det 17. århundre i hans artikkel Explication de l'Arithmétique Binaire. Mens Pingalas system bruker symbolene 1 og 2, bruker Leibniz 0 og 1 som det moderne totallsystemet.

Den britiske matematikeren George Boole publiserte i 1854 en forskningsartikkel som beskrev et logisk system som senere skulle bli kjent som boolsk algebra. Det viste seg at hans logiske system var nyttig i utviklingen av det binære system, særlig i implementeringen av den i elektroniske kretser.

Claude Shannon skrev sin masteravhandling A Symbolic Analysis of Relay and Switching Circuits i 1937. Denne beskrev for første gang i historien boolsk algebra og binær aritmetikk implementert med elektroniske reléer og brytere. Avhandlingen grunnla praktisk talt teorien bak design av digitale kretser.

George Stibitz, som da jobbet ved Bell Labs, ferdigstilte i november 1937 en relebasert datamaskin som han kalte for «Modell K» (etter «kjøkken», hvor han hadde satt den sammen), som kunne regne ved å bruke binær addisjon. Bell Labs godkjente derfor et forskningsprogram i slutten av 1938 med Stibitz ved roret. Deres Complex Number Computer, som ble ferdig den 8. januar 1940 kunne regne med komplekse tall.

I en demonstrasjon ved American Mathematical Society-konferansen ved Darthmouth College den 11. september 1940 kunne Stibbitz sende kommandoer over telefonlinjen til maskinen med en fjernskriver. Det var den første beregningsbaserte maskinen som noengang hadde blitt kontrollert over en telefonlinje. Noen av deltagerne på konferansen som overvar demonstrasjonen var John von Neumann, John Mauchly og Norbert Wiener som skrev om dette i sine memoarer.

Fremstilling

Et binært tall kan bli representert ved enhver sekvens av biter (binary digits, binære siffer), som i sin tur kan bli representert ved hjelp av enhver mekanisme som er i stand til å være i to gjensidige utelukkende tilstander. De følgende sekvenser av symboler kunne alle bli tolket som forskjellige binære numeriske verdier:

1 1 0 1 0 0 1 1
| | - | − - | |
x x o x o o x x
J J N J N N J J
på på av på av av på på
sann sann usann sann usann usann sann sann

Den binære verdien som blir representert i hvert tilfelle er avhengig av verdien som man gir hvert symbol. I en datamaskin kan de numeriske verdiene bli representert av to forskjellige spenninger; på en magnetisk disk kan magnetiske polariteter bli bruk. En «positiv», «ja» eller «på» -tilstand er ikke nødvendigvis lik den numeriske verdien av én; det avhenger av hvilken arkitektur som er i bruk.

På samme måte som man som oftest skriver tall ved å bruke arabiske tall blir binære tall som oftest skrevet ved å bruke symbolene 0 og 1. Binære tall blir ofte markert med senket skrift eller med en endelse) for å indikere grunntallet. De følgende skrivemåtene er ekvivalente:

100101 binary (eksplisitt markering av format)

100101b (en ending som indikerer binært format)

bin 100101 (en prefiks som indikerer binært format)

100101₂ (senket skrift som indikerer grunntall-2 notasjon)

Binære tallverdier blir som oftest uttalt ved å uttale hvert enkelt siffer for å kunne skille dem fra desimale tall. For eksempel blir det binære tallet «100» uttalt «en null null» i stedet for «hundre» for å markere eksplisitt at det er et binært tall, og siden det er mer korrekt. Siden det binære tallet «100» er likt fire desimalt ville det vært forvirrende og numerisk ukorrekt å kalle tallet for «hundre». Er man vant med å jobbe med binære tallverdier er det både nærliggende og korrekt å kalle tallet for «fire».

Telling binært

Å telle i det binære tallsystem er likt som å telle i hvilket som helst annet tallsystem. Man starter med et enkelt siffer, og tellingen fortsetter gjennom hvert symbol i økende rekkefølge. Det desimale tallsystemet bruker symbolene 0 til 9, mens det binære bruker bare symbolene 0 og 1.

Når man ikke har flere symbol for det første sifferet, øker man det neste høyere sifferet, og tellingen starter på nytt igjen på 0. I det desimale tallsystemet går tellingen slik:

00, 01, 02, ... 07, 08, 09 (man begynner på nytt igjen på sifferet helt til høyre, og 0 blir økt)

10, 11, 12, ... 17, 18, 19 (man begynner på nytt igjen på sifferet helt til høyre, og 1 blir økt)

20, 21, 22, ...

Når sifferet helt til høyre når 9, starter tellingen igjen på 0, og det andre sifferet blir økt.

Tellingen er lik i totallsystemet, men siden man bare har to symboler er det slik at når 1 blir nådd, starter tellingen på 0 igjen, og siffert til venstre øker:

000, 001 (sifferet til høyre starter på nytt, og den andre 0 øker)

010, 011 (sifrene i midten og helt til høyre starter på nytt, og 0-tallet helt til venstre øker)

100, 101 (sifferet helt til høyre begynner på nytt, 0-tallet i midten øker)

110, 111...

Binær aritmetikk

Aritmetikk i totallsystemet er veldig likt aritmetikk i andre tallsystemer. Addisjon, subtrahering, multiplikasjon og divisjon kan gjøres på binære tall.

Addisjon

Den enkleste aritmetiske operasjon binært er addisjon. Å legge til to ensiffrede binære tall er relativt enkelt:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 10 (1 i mente)

1 + 1 + 1 = 11 (1 i mente)

Å addere to «1»-verdier gir verdien «10» som er ekvivalent med den desimale verdien 2. Dette er likt det som skjer i det desimale tallsystemet når enkelt ensiffrede tall er lagt sammen; hvis resultatet overstiger verdien av grunntallet (10), blir sifferet til venstre økt:

5 + 5 = 10

7 + 9 = 16

Dette er kjent som mente i de fleste tallsystemer.

  1 1 1 1 1     (mente)
    0 1 1 0 1
+   1 0 1 1 1
-------------
= 1 0 0 1 0 0

I dette eksempelet blir to tall lagt sammen: 01101 (13 desimalt) og 10111 (23 desimalt). Den øverste raden viser mentesifrene som blir brukt. Hvis man starter i kolonnen ytterst til høyre ser vi at 1 + 1 = 10. 1-tallet blir satt opp i mente, og 0-sifferet er skrevet nederst i kolonnen til høyre. Den andre kolonnen fra høyre er lagt sammen: 1 + 0 + 1 = 10 igjen; 1-tallet blir overført i mente og 0 er skrevet på bunnen. Den tredje kolonnen: 1 + 1 + 1 = 11. Denne gangen blir 1-tallet overført og et 1-tall er skrevet nederst. Hvis man fortsetter på denne måten får man sluttsvaret 100100.

Subtrahering

Subtrahering virker på stort sett samme måte:

0 - 0 = 0

0 - 1 = 1 (med låning)

1 - 0 = 1

1 - 1 = 0

Et binært tall kan bli subtrahert fra et annet på følgende måte:

    *   * * *   (kolonner med stjerne har blitt lånt fra)
  1 1 0 1 1 1 0
–     1 0 1 1 1
----------------
= 1 0 1 0 1 1 1

Å subtrahere et positivt tall er ekvivalent til å addere et negativt tall med lik absoluttverdi; datamaskiner bruker vanligvis toerkomplement notasjonen for å representere negative verdier. Denne notasjonen eliminerer behovet for en eget "trekke-fra"-operasjon. For flere detaljer, se toerkomplement.

Multiplikasjon

Multiplisering i det binære tallsystemet er tilsvarende metoden i det desimale tallsystemet. To tall A og B kan bli mulitplisert ved delvise produkter: for hvert siffer i B blir produktet av det sifferet i A utregnet og skrevet på en ny linje, et hakk til venstre for hver gang. Summen av alle disse delvise produktene gir sluttresultatet.

Siden det bare finnes to siffer i det binære tallsystemet, finnes det bare to mulige resultat av hver delvise multiplisering:

Hvis sifferet i B er 0, blir det delvise produktet også 0
Hvis sifferet i B er 1, blir det delvise produktet likt A

For eksempel blir de binære tallene 1011 og 1010 multiplisert som følger:

           1 0 1 1   (A)
         × 1 0 1 0   (B)
         ---------
           0 0 0 0   ← Tilsvarer til null i B
         1 0 1 1     ← Tilsvarer til en i B
       0 0 0 0
   + 1 0 1 1
   ---------------
   = 1 1 0 1 1 1 0

Dividering

Dividering i det binære tallsystemet er likt metoden brukt i det desimale tallsystem:

Bitvise logiske operasjoner

Selv om det ikke er direkte relatert til den numeriske tolkningen av binære symboler, kan sekvenser av bits bli manipulert ved å bruke Boolske logisk operator. Når en streng med binære symboler blir manipulert på denne måten kalles det en bitvis operasjon.

De logiske operandene AND, OR og Eksklusiv disjunksjon kan bli utført på samsvarende bits på to binære tall. Den logiske NOT operasjonen kan bli utført på individuelle bits i et enkelt binærtall.

Slike operasjoner kan enkelte ganger bli brukt som aritmetiske snarveier, og kan også ha andre fordeler ved utregning. For eksempel kan man kutte av den siste biten av et binært tall (også kjent som binærskifting), tilsvarer å dele på to desimalt.

Se bitvis operasjon.

Konvertering til og fra andre tallsystemer

Desimal

Denne metoden fungerer for konvertering fra alle grunntall, men det finnes bedre metoder for grunntall som er kvadrater av to, som for de oktale og heksadesimale tallsystemene beskrevet under.

Siffre i posisjoneringstallsystemer på lavere eller mindre signifikante posisjoner representerer stadig lavere potenser av grunntallet. Starteksponenten er en mindre enn antall siffre i tallet. Et femsifret tall starter med en eksponent på fire. I det desimale systemet er grunntallet ti, så sifferet helt til venstre i et femsiffret tall representerer 10⁴ (titusen) posisjonen. F.eks.:

97352₁₀ er lik:

9 ganger 10⁴ (9 × 10000 = 90000) pluss

7 ganger 10³ (7 × 1000 = 7000) pluss

3 ganger 10² (3 × 100 = 300) pluss

5 ganger 10¹ (5 × 10 = 50) pluss

2 ganger 10⁰ (2 × 1 = 2)

Å multiplisere med grunntallet er enkelt. Man flytter siffrene et hakk til venstre, og 0 er lagt til høyresiden av tallet. For eksempel, 9735 ganger 10 er lik 97350. Derfor er en måte å tolke en streng med siffer er at det siste sifferet [?]. 97352 er lik 9735 ganger 10 pluss 2. Et eksempel på binær form er 1101100111₂ er lik 110110011₂ ganger 2 pluss 1. Dette er essensen i konverteringsmetoden. I hvert steg skriver en nummeret som skal konverteres som 2*k + 0 eller 2*k + 1 for et heltall k som

blir det nye tallet som skal konverteres.

118₁₀ er lik

59 x 2 + 0

(29 x 2 + 1) x 2 + 0

((14 x 2 + 1) x 2 + 1) x 2 + 0

(((7 x 2 + 0) x 2 + 1) x 2 + 1) x 2 + 0

((((3 x 2 + 1) x 2 + 0) x 2 + 1) x 2 + 1) x 2 + 0

(((((1 x 2 + 1) x 2 + 1) x 2 + 0) x 2 + 1) x 2 + 1) x 2 + 0

1 x 2⁶ + 1 x 2⁵ + 1 x 2⁴ + 0 x 2³ + 1 x

2² + 1 x 2¹ + 0 x 2⁰

'1110110₂

Så algoritmen for å konvertere en heltallsdesimaltall til sin binære form er å dele tallet på to, og skrive resten på ett-posisjonen. Resultatet er igjen dividert på to, og resten skrevet på den neste posisjonen til venstre. Denne prosessen gjentar man til nummeret når null.

For eksempel er 118₁₀ binært:

Operasjon	Rest
118/2 = 59	0
59/2 = 29	1
29/2 = 14	1
14/2 = 7	0
7/2 = 3	1
3/2 = 1	1
1/2 = 0	1

Hvis man leser sekvensen av rester fra bunnen og oppover får man det binære tallet 1110110₂.

For å konvertere fra binært til desimalt gjør man det hele omvendt. Man starter fra venstre, og dobler resultatet og legger til neste siffer til det ikke finnes flere. I eksempelet konverteres 110010101101₂ til desimalform:

Resultat	Gjenværende siffer
0	110010101101
0*2 + 1 = 1	10010101101
1*2 + 1 = 3	0010101101
3*2 + 0 = 6	010101101
6*2 + 0 = 12	10101101
12*2 + 1 = 25	0101101
25*2 + 0 = 50	101101
502 + 1 = 101*	01101
1012 + 0 = 202*	1101
2022 + 1 = 405*	101
4052 + 1 = 811*	01
8112 + 0 = 1622*	1
16222 + 1 = 3245*

og resultatet er 3245₁₀.

Heksadesimalt

Da heksadesimaltallenes basis 16 = 2⁴, vil en konvertering være særlig enkel - et heksadesimalt siffer representerer en gruppe av fire binære sifre.

Heksadesimalt	Binært
0	0000
1	0001
2	0010
3	0011
4	0100
5	0101
6	0110
7	0111
8	1000
9	1001
A	1010
B	1011
C	1100
D	1101
E	1110
F	1111

Eksempel: 3F8₁₆ = 001111111000₂

Også desimale tall kan legges til i tabellen. Da vil ikke tabellen vise bokstaver etter 1001 (9) i binære tallsystemet, men resten av tallene som 10, 11 og 12 og videre feks:

Desimale tall til venstre nedenfor . binære tall til høyre nedenfor.

    0               0000
    1               0001
    2               0010
    3               0011
    4               0100
    5               0101
    6               0110
    7               0111
    8               1000
    9               1001
   10               1010
   11               1011
   12               1100
   13               1101
   14               1110
   15               1111

Oktalt

Oktaltallenes basis er 2³ – et oktalt siffer representerer en gruppe av tre binære siffre.

Oktalt	Binært
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

Eksempel: 173₈ = 001111011₂

Brøk

I titallsystemet heter desimalene tideler, hundredeler, tusendeler, titusendeler, hundretusendeler osv. Disse tallene er henholdsvis 10⁻¹, 10⁻², 10⁻³, 10⁻⁴, 10⁻⁵.

Sifrene til høyre for kommaet i totallsystemet representerer (i rekkefølge fra venstre mot høyre) 2⁻¹, 2⁻², 2⁻³, 2⁻⁴, 2⁻⁵ osv. Disse tallene er med andre ord 1/2, 1/4, 1/8, 1/16 og 1/32.

Tallet 0,01 i totallsystemet er en firedel. Ved å summere 0,1 og 0,001 får man at tallet 0,101 i totallsystemet er en halv pluss en åttedel, det vil si fem åttedeler.

Se også