Redigerer Binært tallsystem

{{Kildeløs|Helt uten kilder.|dato=10. okt. 2015}}
Det '''binære [[tallsystem]]''' (også ''totallsystemet'') representerer numeriske verdier ved å bruke to symboler, som oftest sifrene [[0 (tall)|0]] og [[1 (tall)|1]].

Mer nøyaktig, er det binære tallsystem et [[posisjonssystem]] med [[grunntall]] [[2 (tall)|to]]. På grunn av dens relative enkle implementasjon i [[elektronisk krets|elektroniske kretser]] blir totallsystemet brukt internt i så å si alle moderne [[datamaskin]]er.

== Historie ==
Den første kjente beskrivelse av et totallsystem ble gjort av den [[indisk]]e [[matematiker]]en [[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 [[Vedisk_matematikk|vediske]] meter med korte eller lange vokaler. Ifølge den [[India|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 [[Storbritannia|britiske]] matematikeren [[George Boole]] publiserte i [[1854]] en forskningsartikkel som beskrev et [[logikk|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 «'''k'''jø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 [[bit]]er (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

[[Fil:Binary clock.svg|300px|thumbnail|right|En [[binær klokke]] kan bruke [[LED]] for å uttrykke binære verdier. I denne klokken viser hver kolonne av LED-lys et binært tall.]]
[[Fil:Binary clock samui moon.jpg|miniatyr|Binært armbåndsur som viser tiden 3:25. De fire øverste diodene er for timer, de seks nederste er for minutter. Man summerer de diodene som lyser.  1 + 2 = 3 og 1 + 8 + 16 = 25   (3:25)]]
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 [[elektrisk spenning|spenninger]]; på en [[magnetisk]] [[disk]] kan magnetiske [[polaritet]]er 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<sub>2</sub> (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)
:'''1'''0, 11, 12, ... 17, 18, 19 (man begynner på nytt igjen på sifferet helt til høyre, og 1 blir økt)
:'''2'''0, 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)
:0'''1'''0, 011 (sifrene i midten og helt til høyre starter på nytt, og 0-tallet helt til venstre øker)
:'''1'''00, 101 (sifferet helt til høyre begynner på nytt, 0-tallet i midten øker)
:1'''1'''0, 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:


<!--
         __________
 1 0 1  | 1 1 0 1 1

Here, the divisor is 101, or 5 decimal, while the dividend is 11011, or 27 decimal. The procedure is the same as that of 

decimal [[long division]]; here, the divisor 101 goes into the first three digits 110 of the dividend one time, so a "1" is 

written on the top line. This result is multiplied by the divisor, and subtracted from the first three digits of the 

dividend; the next digit (a "1") is included to obtain a new three-digit sequence:

              1
         __________
 1 0 1  | 1 1 0 1 1
        – 1 0 1
          -----
            0 1 1

The procedure is then repeated with the new sequence, continuing until the digits in the dividend have been exhausted:

              1 0 1
         __________
 1 0 1  | 1 1 0 1 1
        – 1 0 1
          -----
            0 1 1
          – 0 0 0
            -----
              1 1 1
            – 1 0 1
              -----
                1 0

Thus, the quotient of 11011 divided by 101 is 101<sub>2</sub>, as shown on the top line, while the remainder, shown on the 

bottom line, is 10<sub>2</sub>. In decimal, 27 divided by 5 is 5, with a remainder of 2.

-->

==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 [[Boolsk algebra|Boolske]] [[logiske operatorer|logisk operator]]. Når en streng med binære symboler blir manipulert på denne måten kalles det en [[bitvis operasjon]].

De logiske operandene [[Logisk konjuksjon|AND]], [[Logisk disjunksjon|OR]] og [[Eksklusiv disjunksjon]] kan bli utført på samsvarende bits på to binære tall. Den logiske [[negasjon|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<sup>4</sup> (titusen) posisjonen. F.eks.:

:'''97352<sub>10</sub>''' er lik:
::'''9''' ganger 10<sup>4</sup> (9 × 10000 = '''90000''') pluss
::'''7''' ganger 10<sup>3</sup> (7 × 1000 = '''7000''') pluss
::'''3''' ganger 10<sup>2</sup> (3 × 100 = '''300''') pluss
::'''5''' ganger 10<sup>1</sup> (5 × 10 = '''50''') pluss
::'''2''' ganger 10<sup>0</sup> (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<sub>2</sub>''' er lik '''110110011<sub>2</sub>''' 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<sub>10</sub>''' 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<sup>6</sup> + '''1''' x 2<sup>5</sup> + '''1''' x 2<sup>4</sup> + '''0''' x 2<sup>3</sup> + '''1''' x 

2<sup>2</sup> + '''1''' x 2<sup>1</sup> + '''0''' x 2<sup>0</sup>
::'''1110110<sub>2</sub>''

Så [[algoritme]]n 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<sub>10</sub> binært:
{| class="wikitable"
!Operasjon!!Rest
|-
|118/2 = 59||align="center"|0
|-
|59/2 = 29||align="center"|1
|-
|29/2 = 14||align="center"|1
|-
|14/2 = 7||align="center"|0
|-
|7/2 = 3||align="center"|1
|-
|3/2 = 1||align="center"|1
|-
|1/2 = 0||align="center"|1
|}
Hvis man leser sekvensen av rester fra bunnen og oppover får man det binære tallet 1110110<sub>2</sub>.

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<sub>2</sub> til desimalform:
{| class="wikitable"
!Resultat!!Gjenværende siffer
|-
|'''0'''||align="center"|110010101101
|-
|0*2 + 1 = '''1'''||align="center"|10010101101
|-
|1*2 + 1 = '''3'''||align="center"|0010101101
|-
|3*2 + 0 = '''6'''||align="center"|010101101
|-
|6*2 + 0 = '''12'''||align="center"|10101101
|-
|12*2 + 1 = '''25'''||align="center"|0101101
|-
|25*2 + 0 = '''50'''||align="center"|101101
|-
|50*2 + 1 = '''101'''||align="center"|01101
|-
|101*2 + 0 = '''202'''||align="center"|1101
|-
|202*2 + 1 = '''405'''||align="center"|101
|-
|405*2 + 1 = '''811'''||align="center"|01
|-
|811*2 + 0 = '''1622'''||align="center"|1
|-
|1622*2 + 1 = '''3245'''||align="center"| 
|}
og resultatet er 3245<sub>10</sub>.

===Heksadesimalt===
Da heksadesimaltallenes basis 16 = 2<sup>4</sup>, vil en konvertering være særlig enkel - et heksadesimalt siffer representerer en gruppe av fire binære sifre.

{| class="wikitable"
!Heksadesimalt!!Binært      
|-
|0||align="center"|0000     
|-
|1||align="center"|0001     
|-
|2||align="center"|0010     
|-
|3||align="center"|0011     
|-
|4||align="center"|0100     
|-
|5||align="center"|0101     
|-
|6||align="center"|0110     
|-
|7||align="center"|0111     
|-
|8||align="center"|1000     
|- 
|9||align="center"|1001     
|-
|A||align="center"|1010    
|-
|B||align="center"|1011    
|-
|C||align="center"|1100    
|-
|D||align="center"|1101    
|-
|E||align="center"|1110    
|-
|F||align="center"|1111    
|}
Eksempel: 3F8<sub>16</sub> = 001111111000<sub>2</sub>

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<sup>3</sup>  – et oktalt siffer representerer en gruppe av tre binære siffre.

{| class="wikitable"
!Oktalt!!Binært
|-
|0||align="center"|000
|-
|1||align="center"|001
|-
|2||align="center"|010
|-
|3||align="center"|011
|-
|4||align="center"|100
|-
|5||align="center"|101
|-
|6||align="center"|110
|-
|7||align="center"|111
|}

Eksempel: 173<sub>8</sub> = 001111011<sub>2</sub>

== Brøk ==
I [[titallsystemet]] heter desimalene tideler, hundredeler, tusendeler, titusendeler, hundretusendeler osv. Disse tallene er henholdsvis 10<sup>&minus;1</sup>, 10<sup>&minus;2</sup>, 10<sup>&minus;3</sup>, 10<sup>&minus;4</sup>, 10<sup>&minus;5</sup>.

Sifrene til høyre for kommaet i totallsystemet representerer (i rekkefølge fra venstre mot høyre) 2<sup>&minus;1</sup>, 2<sup>&minus;2</sup>, 2<sup>&minus;3</sup>, 2<sup>&minus;4</sup>, 2<sup>&minus;5</sup> 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å==
* [[Binær logikk]]
* [[Toerpotens]]
{{Autoritetsdata}}

[[Kategori:Tallsystemer]]
[[Kategori:2 (tall)]]