Bitaaðgerðir

Í fyrri köflum höfum við skoðað hvernig tölvur geyma og framsetja gögn, hvort sem það eru tölur, texti eða litir, sem runur af bitum (0 og 1). Við höfum einnig kynnst því hvernig við getum umbreytt þessum bitum í texta eða myndir.

En hvernig vinnur tölvan sjálf með þessa bita? Þegar við leggjum saman tvær tölur, sækjum vefsíðu eða dulkóðum skilaboð, þá er örgjörvinn ávallt að sýsla með bitana á bak við tjöldin. Í þessum kafla ætlum við að kynnast bitaaðgerðum (e. bitwise operations), þ.e. aðgerðum sem vinna beint á einstaka bitum í tvíundatölum.

Hvers vegna bitaaðgerðir?

Það kann að hljóma flókið að þurfa að hugsa um einstaka bita þegar við forritum, en bitaaðgerðir eru mjög öflugt tól til að hafa í verkfærakistunni. Margar ástæður liggja þar að baki, meðal annars:

1. Bitaaðgerðir eru framkvæmdar beint á vélbúnaði örgjörvans og taka yfirleitt aðeins eitt örgjörvaskref (e. clock cycle). Þær eru því gríðarlega hraðvirkar og nýta sáralitla orku.
2. Þegar við erum að vinna með netpakka eða stýrikerfi þurfum við oft að lesa eða breyta ákveðnum stillingum. Í stað þess að sóa heilu bæti í að geyma einfalda Já/Nei stillingu, geymum við oft átta ólíkar stillingar í einu einasta bæti, þar sem hver biti stendur fyrir einn eiginleika. Við notum svo bitaaðgerðir til að lesa eða breyta þessum bitum.
3. Nánast öll dulritunarkerfi heimsins byggja á bitaaðgerðum. Ef þú vilt skilja hvernig gögn eru dulkóðuð þarftu að kunna að sýsla með bita.

Tengingin við vélbúnað og rökhlið

Í grunninn er tölvan þín ekkert annað en risastórt safn af milljónum eða milljörðum örsmárra rafrása sem kallaðar eru smárar (e. transistors). Þessir smárar virka eins og örfínir rofar sem hleypa rafstraumi í gegn (1) eða loka fyrir hann (0).

Með því að tengja þessa rofa saman á ákveðinn hátt búum við til rökhlið (e. logic gates). Rökhlið eru líkamlegir vélbúnaðarhlutar sem framkvæma rökfræðilegar aðgerðir á rafstraumnum.

Þegar við framkvæmum bitaaðgerð í forritunarmáli eins og Python eða C, þá erum við í raun að skipa örgjörvanum að senda rafstraum í gegnum þessi rökhlið! Til dæmis, ef við framkvæmum bitaaðgerðina AND á tveimur 8 bita tölum í forritinu okkar, þá sendir örgjörvinn þessa bita í gegnum átta sjálfstæð AND-rökhlið sem vinna öll í einu og skila niðurstöðunni á augabragði.

Til að lýsa því hvernig hvert rökhlið virkar notum við svokallaða sanntöflu (e. truth table). Sanntafla sýnir einfaldlega allar mögulegar samsetningar á inntaki og sýnir hvert úttakið verður í hverju tilfelli.

Grunnvirkjar

Kíkjum nú á fjóra helstu grunnvirkjana bitaaðgerða.

NOT — Neitun

NOT aðgerðin er svokallaður einstæður virki (e. unary operator), sem þýðir að hún vinnur aðeins á einni tölu í einu. Hún virkar einfaldlega eins og rofi sem snýr öllum bitum við: 1 verður 0, og 0 verður 1.

Í stærðfræði og rökfræði er neitun yfirleitt táknuð með horni: \(\neg A\) (eða stundum \(\sim A\)). Í flestum forritunarmálum (þ.á m. Python og C) er NOT bitaaðgerðin hins vegar táknuð með bylgjutákni: ~.

Sanntafla NOT

Ef við beitum NOT á bætið 01101001 þá fáum við:

  ~ 01101001
  ----------
    10010110

AND — Ogun

AND aðgerðin er tvístæð, þ.e. tekur tvö inntök, og skilar aðeins 1 ef bæði inntökin eru 1. Ef annað hvort eða bæði inntökin eru 0, þá verður úttakið 0.

Í stærðfræði er and-aðgerðin (ogun) táknuð með hatti: \(A \wedge B\). Í flestum forritunarmálum er bitaaðgerðin hins vegar táknuð með og-tákni: &.

Sanntafla AND

Skoðum dæmi þar sem við beitum AND á tvær tölur, bitafylki fyrir bitafylki:

    11011011
  & 10101100
  ----------
    10001000

OR — Eðun

OR aðgerðin tekur tvö inntök og skilar 1 ef að minnsta kosti annað inntakið er 1. Hún skilar aðeins 0 ef bæði inntökin eru 0.

Í stærðfræði er eða-aðgerðin (eðun) táknuð með fleyg: \(A \vee B\). Í flestum forritunarmálum er bitaaðgerðin hins vegar táknuð með lóðréttu striki: | (oft kallað pípa eða pipe).

Sanntafla OR

Skoðum dæmi um OR aðgerð á tveimur bætum:

    11000101
  | 00110100
  ----------
    11110101

XOR — Misgildisaðgerð (e. exclusive OR)

XOR aðgerðin (stundum kölluð víxl-eða eða einkvæmt EÐA) er ein mikilvægasta bitaaðgerðin. Hún tekur tvö inntök og skilar 1 ef inntökin eru mismunandi (annað er 1 og hitt 0). Ef þau eru eins (bæði 0 eða bæði 1) skilar hún 0.

Í stærðfræði er þessi aðgerð (misgildi) táknuð með plús í hring: \(A \oplus B\). Í flestum forritunarmálum er bitaaðgerðin XOR hins vegar táknuð með hatti: ^.

Sanntafla XOR

Skoðum dæmi um XOR aðgerð:

    10101010
  ^ 11110000
  ----------
    01011010

XOR aðgerðin hefur tvo eiginleika sem gera hana mjög gagnlega.

• Sjálfhverfa: Ef tala er misgilduð við sjálfa sig fáum við alltaf núll, þ.e. \(A \oplus A = 0\).
• Andhverfa: Ef misgildingu er beitt tvisvar sinnum með sömu tölunni, fáum við upprunalegu töluna aftur! Það er, ef \(C = A \oplus B\), þá er \(C \oplus B = A\). Þetta er grunnurinn að einfaldri dulkóðun, þar sem \(B\) er dulkóðunarlykillinn.

Bitastjak

Önnur mjög mikilvæg tegund bitaaðgerða er bitastjak (e. bit shift). Við þessa aðgerð stjökum við öllum bitum í tölu til vinstri eða hægri um ákveðinn fjölda sæta.

Vinstri stjak (e. Left Shift)

Við vinstri stjak færast allir bitar til vinstri og nýjum 0 bitum er bætt við á hægri endann. Í flestum forritunarmálum er bitastjak til vinstri táknað með tveimur vinstri goggum: <<.

Skoðum dæmi þar sem við stjökum tölunni 5 (00000101) til vinstri um eitt sæti (5 << 1):

   00000101  (Talan 5)
   <<<<<<<<  (Stjakað um 1 sæti til vinstri)
   00001010  (Útkoman er 10)

Fjöldi bita

Það er mjög algengt í forritunarmálum að framsetning heiltalna sé takmörkuð við ákveðinn fjölda bita, oft 32 bita. Í þeim tilfellum hefur vinstri stjak þau áhrif að þeir bitar sem hliðrast til vinstri umfram bitafjöldann glatast.

Ef aðeins er notast við 8 bita framsetningu, sjáum við hér hvað gerist þegar 69 er stjakað til vinstri um tvö sæti.

   01000101  (Talan 69)
   <<<<<<<<  (Stjakað um 2 sæti til vinstri)
 0100010100  
   vvvvvvvv  (Fremstu tveimur bitum hent til að passa í 8 bita)
   00010100  (Útkoman er 20)

Þessi hegðun samræmist því sem finnst í forritunarmálum eins og C og Java. Forritunarmálið Python, aftur á móti, notast við framsetningu heiltalna sem gerir það að verkum að hægt er að tákna eins stórar heiltölur og vera vill. Í Python lendum við því aldrei í því að bitum sé hent þegar stjakað er til vinstri, og þá jafngildir stjökun til vinstri um \(n\) sæti ávallt margföldun með \(2^n\).

Hægri stjak (e. Right Shift)

Við hægri stjak færast allir bitar til hægri. Bitarnir sem fara út af hægri endanum glatast. Í flestum forritunarmálum er bitastjak til vinstri táknað með tveimur hægri goggum: >>.

Í framsetningu heiltalna getur bitinn lengst til vinstri haft sérstaka merkingu, þ.e. hann getur sagt til um hvort talan sé neikvæð eða jákvæð. Við ætlum ekki að fara nákvæmlega í þá útfærslu framsetningar heiltalna, en hún er ástæða þess að til eru tvær tegundir hægri stjaks.

Rökstjak (e. Logical Shift)

Við rökstjak er alltaf bætt við 0 á vinstri endann, óháð því hver upprunalega talan var. Þessi aðferð er ávallt notuð fyrir jákvæðar heiltölur.

Reiknistjak (e. Arithmetic Shift)

Ef við erum að vinna með neikvæðar tölur sem nota formerkisbita (e. sign bit) á vinstra enda bitarununnar til að tákna að talan sé neikvæð, þá viljum við ekki eyðileggja formerkið. Reiknistjak heldur formerkisbitanum óbreyttum. Ef vinstri bitinn var 1, þá er 1 bætt við; ef hann var 0, þá er 0 bætt við.

Hringstjak (e. Circular Shift eða Rotate)

Sumir örgjörvar bjóða upp á hringstjak, þar sem engir bitar glatast. Bitarnir sem fara út af öðrum endanum „rúlla“ hringinn og koma inn á hinum endanum!

Flóknari útreikningar með bitaaðgerðum

Hvernig getur örgjörvinn lagt saman tvær tölur ef hann vinnur bara með rökhlið? Svarið er að við getum byggt flóknari stærðfræði algjörlega upp úr einföldum bitaaðgerðum!

Skoðum hvernig við leggjum saman tvo staka bita, \(A\) og \(B\):

Samlagning án geymslu (XOR)

• \(0 + 0 = 0\)
• \(0 + 1 = 1\)
• \(1 + 0 = 1\)
• \(1 + 1 = 0\) (með 1 í geymslu, þ.e. \(10\) í tvíundakerfi)

Ef við skoðum þessa samlagningu tökum við eftir því að hún er nákvæmlega eins og sanntafla misgildingar! XOR gefur okkur því summu bitanna.

Geymslutalan (AND)

Hvenær fáum við geymslutölu (e. carry)? Aðeins þegar við leggjum saman \(1 + 1\). Í öllum öðrum tilfellum fáum við ekki geymslutölu. Þetta er nákvæmlega eins og sanntafla ogunar!

Með því að tengja eitt XOR-rökhlið og eitt AND-rökhlið saman búum við til svokallaða hálfsamlagningarrás (e. half adder). Með því að tengja margar slíkar rásir er hægt að leggja saman tölur af hvaða stærð sem er! Þetta sýnir hvernig hugbúnaður, stærðfræði og vélbúnaður mætast í einni heild.

Dæmi og æfingar

    1 1 0 0  (12)
  & 1 0 1 0  (10)
  ---------
    1 0 0 0  (8)

    1 1 1 1  (15)
  ^ 1 1 1 1  (15)
  ---------
    0 0 0 0  (0)