Operacije sa bitovima u programskom jeziku C

Uvod

Uobičajeni logički operatori u programskom jeziku C: &&, ||, ^^ i !, operišu nad celobrojnim promenljivama i uzimaju u obzir vrednosti operanada u celosti, pri čemu se vrednost 0 tumači kao "NETAČNO", a bilo koja vrednost različita od 0 (ne samo 1), tumači se kao "TAČNO" - i pri tom nije moguće pristupati pojedinačnim bitovima.

U većini uobičajenih situacija, pristup pojedinačnim bitovima nije neophodan, međutim, postoje i situacije u kojima pristup bitovima - sasvim dobro dođe.

Rekli bismo da se prethodna konstatacija odnosi pre svega na sistemsko programiranje - koje između ostalog podrazumeva pristup hardveru, a pristup hardveru podrazumeva pristup pojedinačnim pinovima hardverskih komponenti (uključivanje, isključivanje, ili naprosto, očitavanje vrednosti pojedinačnih pinova na određenom hardverskom portu i sl) - što su operacije koje se mogu obaviti samo preko operatora koji imaju mogućnost da operišu nad pojedinačnim bitovima.

Takođe, rekli bismo i da su operacije nad pojedinačnim bitovima (u očima većine programera), veoma zanimljive same po sebi, a vredi spomenuti i to da bitovski operatori pružaju zanimljive mogućnosti i u svakodnevnom programiranju.

Pregled bitovskih operatora u C-u

U programskom jeziku C, pristup pojedinačnim bitovima pri obavljanju logičkih operacija, postiže se upotrebom specijalizovanih operatora:

& - bitovska konjunkcija (bitovsko I)
| - bitovska disjunkcija (bitovsko ILI)
^ - bitovska ekskluzivna disjunkcija (bitovski XOR)
~ - invertovanje bitova (bitovsko NE)
<< - pomeranje bitova ulevo
>> - pomeranje bitova udesno

Međutim, potrebno je odmah naglasiti da navedeni bitovski operatori nisu u stanju da obave operaciju na samo jednom paru bitova u dve celobrojne promenljive (bar ne direktno), već operišu nad svim parovima susednih bitova u dve promenljive koje učestvuju u operaciji. *

Situacija u kojoj se ne može direktno pristupati pojedinačnim bitovima, može delovati pomalo problematično (i svakako zaslužuje pažnju), ali, uz pažljivo promišljanje, uvek se može postići željeni rezultat.

Za početak, pogledajmo kako funkcionišu sami operatori.

Napomena: za prikaz tablica istinitosti koristićemo ponešto eklektičan pristup - umesto uobičajenih oznaka poznatih iz matematike, koristićemo oznake za operatore koje se koriste u C-u, da ne bi došlo do zabune (na primer, u matematici se operacija logičke konjunkcije označava sa ^, dok isti operator u C-u predstavlja bitovski operator ekskluzivne disjunkcije - bitovski XOR, a ima i drugih razlika).

Takođe, umesto istinitosnih vrednosti ⊤ ("te") i ⊥ ("ne-te"), koristićemo oznake 0 i 1.

(Doduše, tablice koje ćemo prikazati, zapravo važe i ako zamislimo da su "A" i "B", celobrojne promenljive koje bitovski operatori koriste kao operande, ali, nije nam namera da prizivamo takve asocijacije, već da na što praktičniji način prikažemo tablice istinitosti opšteg tipa, koje se primenjuju na parove bitova.)

Operator & (bitovsko I)

Tablica istinitosti za logičku konjunkciju (logičko I), prikazana je na sledećoj slici:

Logičko I - Tablica Istinitosti — Slika 1. - Istinitosna tablica za operaciju logičke konjunkcije: rezultat je "TAČNO", samo ako su oba uslova zadovoljena

Bitovski operator konjunkcije & (bitovsko I), operiše nad dve celobrojne vrednosti, pristupajući nezavisno parovima bitova na istoj poziciji u obe promenljive, i primenjuje gornju tablicu na parove bitova.

Kada se bitovski operator & upotrebi između dve osmobitne celobrojne promenljive, * dobija se sledeći rezultat:

Logičko I - Primer — Slika 2. - Bitovska konjunkcija primenjuje se na svaki par bitova nezavisno i rezultat će biti 1 samo na onim pozicijama gde oba bita imaju vrednost 1.

Operator | (bitovsko ILI)

Tablica istinitosti za logičku disjunkciju (logičko ILI), prikazana je na sledećoj slici:

Logičko ILI - Tablica Istinitosti — Slika 3. - Istinitosna tablica za operaciju logičke disjunkcije: rezultat je "TAČNO" onda kada je bilo koji od dva uslova zadovoljen

Bitovski operator disjunkcije | (bitovsko ILI), takođe je binarni operator, a primer upotrebe bitovskog operatora disjunkcije, možemo videti na sledećoj slici:

Logičko ILI - Primer — Slika 4. - Bitovska disjunkcija, primenjena na svaki par bitova nezavisno, daje rezultat 1 na svim mestima gde makar jedan od dva bita ima vrednost 1.

Operator ^ (isključivo ILI)

Tablica istinitosti za operaciju ekskluzivne disjunkcije (isključivo ILI, odnosno XOR), prikazana je na sledećoj slici:

Isključivo ILI - Tablica Istinitosti — Slika 5. - Istinitosna tablica za operaciju ekskluzivne disjunkcije: rezultat je "TAČNO" samo ukoliko su operandi različiti

Kada se gornja tablica primeni na dve celobrojne vrednosti, preko bitovskog operatora ekskluzivne disjunkcije ^ (bitovski XOR), dobija se sledeći rezultat:

Isključivo ILI - Primer — Slika 6. - U skladu sa tablicom isključive disjunkcije, operator ^ daje vrednost 1 samo na onim mestima gde par bitova sadrži jednu nulu i jednu jedinicu.

Operator ~ (invertovanje bitova / bitovsko NE)

Tablica istinitosti za operaciju invertovanja (logičko NE), prikazana je na sledećoj slici:

Za razliku od, do sada opisanih operatora (i onih koji tek slede), bitovski operator negacije ~ (bitovsko NE), je unarni operator, što znači da operiše nad jednom promenljivom.

Primer upotrebe bitovskog operatora ~ možemo videti na donjoj slici:

Operator << (pomeranje bitova ulevo)

Operator << je binarni bitovski operator preko koga se, svi bitovi celobrojne promenljive, pomeraju određeni broj mesta ulevo.

U naredbi a << n, svi bitovi promenljive a pomeraju se za n mesta ulevo, pri čemu važe sledeća pravila:

uključeni bitovi sa leve strane, za koje posle pomeranja ulevo nema mesta - jednostavno se zanemaruju
sa desne strane se dodaju nule

Na primer, ukoliko promenljiva a na početku ima vrednost 1, posle operacije a << 2, imaće vrednost 4.

Praktičan primer upotrebe operatora << možemo videti na donjoj slici:

Pomeranje bitova ulevo - Primer — Slika 9. - Pomeranje bitova ulevo za dva mesta (bitovi koji ne mogu biti smešteni sa leve strane nestaju, a desno se dopisuju nule)

Pri upotrebi operatora pomeranja bitova ulevo, mora se uvek voditi računa o levim bitovima promenljive, jer (baš kao u slučaju sa gornje slike), lako se može desiti da neki od bitova praktično budu izbrisani!

Pomenuli smo na početku da bitovski operatori dobro dođu i u svakodnevnim situacijama, pa tako, u praktičnom smislu (ukoliko sa leve strane ima dovoljno mesta za jedinice koje se pomeraju), upotrebom operatora <<, određena vrednost lako se može pomnožiti nekim od stepena broja dva (vrednostima kao što su 2, 4 .... 64, 128 .... 512 i sl).

Operator >> (pomeranje bitova udesno)

Operator >> je binarni bitovski operator preko koga se, svi bitovi celobrojne promenljive, pomeraju određeni broj mesta udesno.

U naredbi a >> n, svi bitovi promenljive a pomeraju se za n mesta udesno, pri čemu važe sledeća pravila:

uključeni bitovi sa desne strane, za koje posle pomeranja udesno nema mesta - jednostavno se zanemaruju
sa leve strane se dodaju nule

Na primer, ukoliko promenljiva a na početku ima vrednost 8, posle operacije a >> 2, imaće vrednost 2.

Praktičan primer upotrebe operatora >> možemo videti na donjoj slici:

Pomeranje bitova udesno - Primer — Slika 10. - Pomeranje bitova udesno za dva mesta (uključeni bitovi sa desne strane za koje posle pomeranja nema mesta - zanemaruju se, a levo se dopisuju nule)

Pri upotrebi operatora pomeranja bitova udesno, takođe se mora uvek voditi računa o jedinicama sa (ovoga puta) desne strane.

Međutim, ukoliko se operator >> koristi kao mehanizam za "brzinsko deljenje" nekim od stepena dvojke, jasno je da je u pitanju celobrojno deljenje bez ostatka, ali je takođe jasno (shodno svemu što smo prethodno naveli), da će rezultat uvek biti korektan.

Operacije sa bitovima

Vraćamo se na jedno od glavnih pitanja sa početka: kako se može izvesti da određeni operator utiče samo na određeni bit u promenljivoj (a ne - na celu promenljivu)?

Maskiranje bita

Operacija koja se popularno naziva "maskiranje bit(ov)a", podrazumeva (tipično, ali ne i uvek; videćemo u nastavku), upotrebu pomoćne promenljive koja ima isključene sve bitove, i jedan uključen bit - na poziciji na kojoj je, u glavnoj promenljivoj, potrebno očitati vrednost bita ili obaviti neku drugu operaciju.

Uključivanje određenog bita (u pomoćnoj promenljivoj), najlakše se izvodi tako što se prvo uključi samo prvi bit (praktično, preko naredbe dodele a = 1), posle čega se prvi bit, preko operatora pomeranja ulevo a = a << (p - 1);, postavlja na poziciju p.

Maskiranje bitova - Primer — Slika 11. - Uključivanjem prvog bita i pomeranjem bitova za tri mesta ulevo, praktično je uključen četvrti bit (odnosno - kreirana je "maska" za 4. bit sa desne strane).

Na ovom mestu iznećemo jednu napomenu, tehničke prirode.

U idejnom smislu, postupak koji smo videli na slici je korektan, ali, u praktičnom smislu (u programskim jezicima), naredba kao što je:

		
a << (p - 1);

Slika 12. - Naredba kojom se (naizgled) pomeraju bitovi u promenljivoj a (dok se rezultat, zapravo, samo privremeno čuva u memoriji).

.... neće zapravo dovesti do pomeranja bitova u promenljivoj a - jer se rezultat ne čuva!

Da bi rezultat bio sačuvan, neophodno je koristiti naredbu dodele:

		
a = a << (p - 1);

Slika 13. - Naredba kojom se (ovoga puta zapravo), pomeraju bitovi u promenljivoj a.

Pogledajmo kako se, uz korišćenje tehnike maskiranja, može operisati nad pojedinačnim bitovima.

Uključivanje pojedinačnog bita

Za uključivanje određenog bita (odnosno, za zadavanje vrednosti 1 određenom bitu), potrebno je prvo "maskirati" poziciju ....

Uključivanje bita - Maskiranje — Slika 14. - Generisanje "maske" pomeranjem uključenog bita na poziciju p.

.... i potom pozvati bitovski operator disjunkcije (bitovsko ILI):

Uključivanje bita - Primer — Slika 15. - Uz masku sa prethodne slike, bitovski operator disjunkcije ostaviće sve bitove - osim "maskiranog" bita - u prvobitnom stanju, a maskirani bit će (obavezno) biti uključen.

Svi bitovi, osim "maskiranog" bita, zadržaće svoje vrednosti, dok će maskirani bit posle izvršavanja operacije obavezno imati vrednost 1.

Isključivanje pojedinačnog bita

Za isključivanje određenog bita, prvo je potrebno napraviti standardnu masku (kakvu smo koristili i u prethodnom primeru):

Isključivanje bita - Maskiranje — Slika 16. - Generisanje "maske" pomeranjem uključenog bita na poziciju p (u međukoraku, maska će biti invertovana).

U sledećem koraku, maska se invertuje (preko operatora ~ menjaju se vrednost svih bitova, tako da nule postanu jedinice, a jedinice nule).

Na kraju, poziva se bitovski operator konjunkcije (bitovsko I):

Isključivanje bita - Primer — Slika 17. - Upotrebom invertovane maske (i operatora bitovske konjunkcije), postižemo da svi uključeni bitovi ostanu uključeni, dok će prvobitno uključeni bit na poziciji p, na kraju biti isključen.

Preko invertovane maske, postigli smo da se ne isključi nijedan od bitova koji su prethodno bili uključeni - osim bita na poziciji p, koji je potrebno isključiti - i koji biva isključen.

Očitavanje vrednosti pojedinačnog bita

Očitavanje vrednosti bita na određenoj poziciji je (reklo bi se), najopštija od operacija koje se mogu izvoditi nad pojedinačnim bitovima, međutim, za razliku od prethodno opisanih operacija (za koje postoje uobičajeni/optimalni postupci, koji se gotovo uvek koriste), za očitavanje bita postoje dva različita pristupa, i upravo zato smo kraću diskusiju o operaciji očitavanja vrednosti bita ostavili "za pred kraj".

Varijanta 1

Sa jedne strane, očitavanje bita na određenoj poziciji, može se izvesti upotrebom standardne maske kakvu smo već koristili:

Ideja se može implementirati na sledeći način:

		
a = 233; // proizvoljna vrednost;
         // zanima nas (samo) 4. bit sa desne strane
p = 4;
m = 1 << (p - 1); // praktično: m = 8
r = a & m; // u ovom slučaju, krajnji rezultat je takođe 8;
           // u opštem smislu, rezultat je: ili 0, ili stepen
		   // broja 2 koji odgovara poziciji koju očitavamo

Slika 19. - Implementacija algoritma sa prethodne slike.

.... pri čemu se kao rezultat dobija: ili 0, ili (praktično), "kopija" promenljive m (maske).

Varijanta 2

U praksi (budući da prethodni algoritam nije baš pogodan za ekonomično zapisivanje u jednoj liniji koda), tipično se sprovodi postupak kojim se traženi bit pomera na prvu poziciju, i potom se očitava vrednost prvog bita (ili, u praktičnom smislu - vrednost traženog bita).

Ako želimo da očitamo (na primer), 4. bit sa desne strane u promenljivoj a, prvo je potrebno dovesti četvrti bit promenljive a na prvu poziciju, preko operatora >> (pri čemu za početak treba uvideti da se vrednost promenljive a - ukoliko primenimo pravilan postupak - neće promeniti; više o svemu u nastavku):

Očitavanje vrednosti bita - Maskiranje — Slika 20. - U drugoj varijanti očitavanja bita na 4. poziciji, prvo je potrebno navedeni bit postaviti na 1. poziciju (pomeranjem svih bitova udesno za 3 mesta).

U drugom koraku - uz korišćenje bitovskog operatora konjunkcije - rezultat se svodi na 0 ili 1 (i pamti se preko dodatne promenljive).

Očitavanje vrednosti bita - Primer — Slika 21. - Upotrebom bitovske konjunkcije, rezultat se svodi na 0 ili 1.

Programski kod je još jednostavniji (nego što bi se dalo naslutiti posmatranjem primera sa prethodne dve slike):

		
// a = 233;
// p = 4;
r = a >> (p - 1) & 1;

Slika 22. - Praktičan primer koda za očitavanje bita na poziciji p (u promenljivoj a).

Cela naredba zapisuje se u jednom redu, nema pomoćnih promenljivih, i promenljiva a zadržava svoju vrednost.

Da pojasnimo dodatno: vrednost promenljive a kopira se na (neimenovanu) pomoćnu memorijsku lokaciju, obavlja se pomeranje bitova, računa se krajnji rezultat (koji se smešta u promenljivu r) i budući da (prosto rečeno), nema naredbe dodele koja bi promenila vrednost promenljive a - promenljiva a zadržava vrednost.

Invertovanje ("obrtanje") bita na poziciji p

Invertovanje pojedinačnog bita je (zapravo), krajnje jednostavna operacija (možda i najjednostavnija od svih), ali, budući da - bez obzira na navedenu jednostavnost - upotreba operatora XOR (koji naizgled nije namenjen "obrtanju" pojedinačnih bitova), na prvi pogled deluje manje intuitivno od upotrebe operatora ~ (koji doslovno jeste namenjen invertovanju bitova - ali nam u ovom slučaju neće mnogo pomoći), operaciju invertovanja pojedinačnih bitova smo ostavili za kraj.

U svakom slučaju, dovoljno je samo maskirati određeni bit ....

Obrtanje bita - Maskiranje — Slika 23. - Generisanje "maske" pomeranjem uključenog bita na poziciju p.

.... i pozvati bitovski XOR:

Obrtanje bita - Primer — Slika 24. - Invertovanje bita na poziciji #4: svi bitovi koji su imali vrednost 1 (osim četvrtog), zadržavaju vrednost (zato što se "xor-uju" sa nulama); na četvrtoj poziciji XOR uključuje bit (ako je bit imao vrednost 0), ili isključuje bit (ako je bit imao vrednost 1).

.... koji (sada je jasno), deluje "kao poručeno" za ovakav zahvat.

Operator XOR (bilo da je u pitanju bitovska ili "nebitovska" varijanta), ima i brojne druge primene (o čemu ćemo pisati u nekom od narednih članaka), a za sam kraj vam ostavljamo da uživate u jednostavnosti i eleganciji algoritma za invertovanje pojedinačnih bitova.