Binært tallsystem
Fra Wikipedia, den frie encyklopedi
Det binære tallsystem (også totallsystemet) representerer numeriske verdier ved å bruke to symboler, som oftest siffrene 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å og si alle moderne datamaskiner.
Innhold |
[rediger] 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. I fø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 utviklet sin mastertese i 1937 som implementerte Boolsk algebra og binær aritmetikk for første gang i historien ved å bruke elektroniske releer og brytere . Tesen A Symbolic Analysis of Relay and Switching Circuits grunnla praktisk talt designen 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 beregnende maskinen som noengang hadde blitt kontrollert over en telefonlinje. Noen av deltagerene på konferansen som overværte demonstrasjoen var John Von Neumann, John Mauchly og Norbert Wiener som skrev om dette i sine memoarer.
[rediger] 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:
11010011 på av av på av på - | - | | - | - - | - | o x o o x o o x N J N N J N J J J sann usann sann sann sann usann han han hun han hun
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 likt 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)
- 1001012 (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".
[rediger] 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...
[rediger] 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.
[rediger] 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)
Å 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 mentesifferene 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.
[rediger] 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.
[rediger] 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
[rediger] Dividering
Dividering i det binære tallsystemet er likt metoden brukt i det desimale tallsystem:
[rediger] 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.
[rediger] Konvertering til og fra andre tallsystemer
[rediger] 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 104 (titusen) posisjonen. F.eks.:
- 9735210 er lik:
- 9 ganger 104 (9 × 10000 = 90000) pluss
- 7 ganger 103 (7 × 1000 = 7000) pluss
- 3 ganger 102 (3 × 100 = 300) pluss
- 5 ganger 101 (5 × 10 = 50) pluss
- 2 ganger 100 (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 11011001112 er lik 1101100112 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.
- 11810 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 26 + 1 x 25 + 1 x 24 + 0 x 23 + 1 x
22 + 1 x 21 + 0 x 20
-
- '11101102
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 prossesen gjentar man til nummeret når null.
For eksempel er 11810 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 11101102.
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 1100101011012 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 |
| 50*2 + 1 = 101 | 01101 |
| 101*2 + 0 = 202 | 1101 |
| 202*2 + 1 = 405 | 101 |
| 405*2 + 1 = 811 | 01 |
| 811*2 + 0 = 1622 | 1 |
| 1622*2 + 1 = 3245 |
og resultatet er 324510.
[rediger] Heksadesimalt
Da heksadesimaltallenes basis 16 er 24 er en konvertering særlig enkel - et heksadesimalt siffer representerer en gruppe av fire binære siffre.
| 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: 3F816 = 0011111110002
[rediger] Oktalt
Oktaltallenes basis er 23 - 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: 1738 = 0011110112
[rediger] Representering av reelle tall
[rediger] Vitser
Det finnes 10 forskjellige personer her i verden, de som forstår binærkode og de som ikke gjør det.
