Operacije sa bitovima u programskom jeziku C
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 izradi rešenja za većinu 'rutinskih' zadataka, nije neophodno pristupati pojedinačnim bitovima, međutim, postoje i mnoge situacije u kojima takva mogućnost sasvim dobro dođe.
Prethodna konstatacija odnosi se pre svega na sistemsko programiranje - aktivnost koja između ostalog podrazumeva pristup hardveru, odnosno, 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 operisanja nad pojedinačnim bitovima.
Može se takođe reći da su operacije nad pojedinačnim bitovima veoma zanimljive same po sebi (u očima većine programera), 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 susednim parovima bitova u dve promenljive koje učestvuju u operaciji.
Shodno navedenim uslovima, za konjunkciju, disjunkciju i XOR važi pravilo da se vrednost bita na poziciji p u rezultatu dobija obavljanjem operacije nad bitovima na poziciji p u operandima a i b (to jest, u slučaju operacije invertovanja, kao rezultat invertovanja bita na poziciji p u promenljivoj a).
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, željeni rezultat se uvek može postići.
Za početak, razmotrićemo kako funkcionišu sami operatori.
Operator & (bitovska konjunkcija)
Operacija logičke konjunkcije (koja je poznata i kao "logičko i", zbog idejne povezanosti sa veznikom "i" iz govornih jezika), obavlja se u skladu sa sledećom istinitosnom tablicom:
| p | q | p ∧ q |
| ⊥ | ⊥ | ⊥ |
| ⊥ | ⊤ | ⊥ |
| ⊤ | ⊥ | ⊥ |
| ⊤ | ⊤ | ⊤ |
Tablica istinitosti za bitovski operator konjunkcije, prikazana je na sledećoj slici:
| a | b | a & b |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Bitovski operator konjunkcije & (bitovsko I), operiše nad dve celobrojne vrednosti, pristupajući nezavisno parovima bitova na istoj poziciji u obe promenljive, pri čemu se na svaku pojedinačnu poziciju primenjuje tablica sa slike #2.
Kada se bitovski operator & upotrebi između dve osmobitne celobrojne promenljive, * dobija se sledeći rezultat:
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | |
| & | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| = | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
Operator | (bitovska disjunkcija)
Logička disjunkcija (poznata i kao "logičko ILI", zbog idejne povezanosti sa veznikom ili), obavlja se u skladu sa sledećom istinitosnom tablicom:
| p | q | p ∨ q |
| ⊥ | ⊥ | ⊥ |
| ⊥ | ⊤ | ⊤ |
| ⊤ | ⊥ | ⊤ |
| ⊤ | ⊤ | ⊤ |
Tablica istinitosti za bitovski operator disjunkcije, prikazana je na sledećoj slici:
| a | b | a | b |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Bitovski operator disjunkcije | (bitovsko ILI), takođe je binarni operator, a primer upotrebe bitovskog operatora disjunkcije možemo videti na sledećoj slici:
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | |
| | | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| = | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
Operator ^ (bitovska isključiva disjunkcija)
Logička operacija ekskluzivne disjunkcije (isključivo ILI, odnosno XOR (ovoga puta nećemo tražiti očigledne 'paralele' sa govornim jezikom :))), obavlja se u skladu sa sledećom istinitosnom tablicom:
| p | q | p ⊻ q |
| ⊥ | ⊥ | ⊥ |
| ⊥ | ⊤ | ⊤ |
| ⊤ | ⊥ | ⊤ |
| ⊤ | ⊤ | ⊥ |
Tablica istinitosti za bitovski operator XOR, prikazana je na sledećoj slici:
| a | b | a ^ b |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Kada se tablica sa slike #8 primeni na dve celobrojne vrednosti, preko bitovskog operatora ekskluzivne disjunkcije ^ (bitovskog XOR-a), dobija se sledeći rezultat:
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | |
| ^ | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| = | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
Operator ~ (bitovska negacija / invertovanje bitova)
Operacija logičke negacije (invertovanje/logičko NE), obavlja se u skladu sa sledećom istinitosnom tablicom:
| p | ¬p |
| ⊥ | ⊤ |
| ⊤ | ⊥ |
Tablica istinitosti za bitovski operator logičke negacije, prikazana je na sledećoj slici:
| a | ~a |
| 0 | 1 |
| 1 | 0 |
Za razliku od operatora koji su prethodno opisani (i nekoliko operatora koji tek slede), bitovski operator negacije ~ je unarni operator, što znači da operiše nad jednom promenljivom.
Primer upotrebe bitovskog operatora ~ možemo videti na donjoj slici:
| ~ | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| = | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
Operator << (pomeranje bitova ulevo)
Operator << je binarni bitovski operator preko koga se bitovi celobrojne promenljive pomeraju određeni broj mesta ulevo, međutim, pravi rezultat operacija pomeranja zavisi od toga da li se operiše nad označenim ili neoznačenim promenljivama.
Uobičajeno je da se operatori pomeranja koriste (isključivo) za manipulaciju bitovima u neoznačenim promenljivama, ali (zarad što bolje informisanosti), osvrnućemo se i na pravila koja tipično važe za pomeranje bitova u označenim promenljivama. *
U naredbi a << n, 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 (ali, ukoliko je u pitanju označena promenljiva, * prvi bit sa leve strane ne učestvuje u 'pomeranju', tj. zadržava prvobitnu vrednost - koja u neoznačenim promenljivama predstavlja znak)
- sa desne strane dopisuju se nule
Na primer, ukoliko neoznačena promenljiva a na početku ima vrednost 1, posle operacije a << 2 imaće vrednost 4.
Praktičan primer upotrebe operatora << koji operiše nad neoznačenom promenljivom, možemo videti na donjoj slici:
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | |
| << | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| = | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
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, i stoga, u praktičnom smislu (ukoliko sa leve strane ima dovoljno mesta za jedinice koje se pomeraju), upotrebom operatora <<, određena vrednost se lako može pomnožiti nekim od stepena broja dva (tj. vrednostima kao što su 2, 4, 8, 16 .... 128, 256, 512 i sl).
Operator >> (pomeranje bitova udesno)
Operator >> je binarni bitovski operator preko koga se bitovi celobrojne promenljive pomeraju određeni broj mesta udesno (pri čemu, i ovoga puta, pravi rezultat zavisi od toga da li je u pitanju označena ili neoznačena promenljiva).
U naredbi a >> n, 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 (ali, ukoliko je u pitanju neoznačena promenljiva, prvi bit tipično ne učestvuje u pomeranju)
- sa leve strane, dopisuju se nule (ali, ako je u pitanju neoznačena promenljiva, prvi bit neće biti izmenjen)
Na primer, ukoliko neoznačena promenljiva a na početku ima vrednost 8, posle operacije a >> 2 imaće vrednost 2.
Praktičan primer upotrebe operatora >> koji operiše nad neoznačenom promenljivom, možemo videti na donjoj slici:
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | |
| >> | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| = | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
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, takođe je jasno (shodno svemu što smo prethodno naveli), da se uvek dobija korektan rezultat.
Operatori pomeranja i označene promenljive
Kao što smo već nagovestili, pomeranje bitova u označenim promenljivama je svojevrsna "siva zona", budući da ne postoje jasna pravila koja važe "uvek" (u svim jezicima tj. svim kompajlerima), ali, najuobičajenija (i najintuitivnija) implementacija, podrazumeva sledeće: ukoliko operatori pomeranja << i >> operišu nad označenim promenljivama, važe prethodno navedena pravila o pomeranju bitova i dopisivanju nula sa leve ili desne strane, ali - prvi bit zadržava prethodnu vrednost (i ne utiče na okolne bitove), što možemo sagledati preko dva naredna primera.
Primer upotrebe operatora <<
U prvom primeru (pomeranje bitova za dva mesta ulevo) ....
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | |
| << | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| = | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
.... možemo primetiti da prvi bit neće poprimiti vrednost 0 (što bi se desilo u slučaju operisanja nad neoznačenom promenljivom).
U drugom primeru (pomeranje bitova za tri mesta ulevo) ....
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | |
| << | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| = | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
.... možemo primetiti da prvi bit neće poprimiti vrednost 1 (što bi se desilo u slučaju operisanja nad neoznačenom promenljivom).
Primer upotrebe operatora >>
U sledećem primeru (pomeranje bitova za dva mesta udesno), prvi bit nije 'u opasnosti od desnih bitova' (kao u gornjim primerima), ali ....
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | |
| >> | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| = | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
.... takođe možemo primetiti da prvi bit (koji u ovom slučaju ima vrednost 1), neće uticati na desne bitove (jer ne učestvuje u pomeranju).
Razlike između logičkih i bitovskih operatora (dodatni osvrt)
Za sam kraj poglavlja o operatorima, još jednom ćemo se osvrnuti na to zašto se logički i bitovski operatori ne mogu (u većini situacija) koristiti 'jedni umesto drugih'.
U prvom primeru ....
int a = 5, b = 10;
int r = a && b; // 1
.... rezultat je 1 (sasvim očekivano: a = ⊤, b = ⊤ => a ∧ b = ⊤), ali, u drugom primeru - koji je naizgled veoma sličan ....
int a = 5, b = 10;
int r = a & b; // 0
.... rezultat je 0 (što možda i nije bilo očekivano :))!
Iako možda "ne deluje" * da je rezultat u drugom slučaju ispravan, nedoumice se mogu otkloniti uz kratak osvrt na bitove od kojih su sačinjeni brojevi 5 (0101(2)) i 10 (1010(2)):
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | |
| & | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| = | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Složene operacije sa bitovima
Pošto smo se upoznali sa osnovnim operatorima, upoznaćemo se i sa tipičnim složeni(ji)m operacijama koje se obavljaju nad pojedinačnim bitovima celobrojnih promenljivih.
Pre svega, 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 (tj. kako da ne utiče na celu promenljivu)?
Maskiranje bita
Operacija koja se popularno naziva "maskiranje bita", podrazumeva (tipično, ali ne uvek; videćemo uskoro), upotrebu posebno pripremljene 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 (koja se koristi kao "maska"), najlakše se izvodi tako što se na početku uključi samo najniži bit (praktično, preko naredbe dodele m = 1), posle čega se najniži bit postavlja na poziciju p preko operatora pomeranja ulevo: m = m << (p - 1);.
| m (maska) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| p | 4 | |||||||
| m << (p - 1) | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
Na ovom mestu iznećemo i 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 ....
m << (p - 1);
.... neće zapravo dovesti do pomeranja bitova u promenljivoj m - jer se rezultat ne čuva.
Da bi rezultat bio sačuvan, neophodno je koristiti naredbu dodele:
m = m << (p - 1);
U nastavku, pogledajmo kako tehnike maskiranja pomažu pri izvođenju 'konkretnijih' operacija sa 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 ....
| m | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| p | 4 | |||||||
| m << (p - 1) | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
.... nakon čega se poziva bitovski operator disjunkcije (bitovsko ILI):
| a | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| m (maska) | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| a = a | m | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
Svi bitovi, osim "maskiranog" bita, zadržaće prethodne vrednosti, a maskirani bit će 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):
| m | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| p | 4 | |||||||
| m << (p - 1) | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
U sledećem koraku, maska se invertuje * (preko operatora ~).
Na kraju, poziva se bitovski operator konjunkcije (bitovsko I):
| a | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| ~m | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
| a = a & ~m | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Preko invertovane maske (i uz korišćenje opštih svojstava operatora &), postigli smo da se isključi samo bit na poziciji p (koji je potrebno isključiti, i koji biva isključen).
Očitavanje vrednosti pojedinačnog bita
Moglo bi se reći da je očitavanje vrednosti bita (na određenoj poziciji), najopštija od svih operacija koje se 'ikako' mogu izvoditi nad pojedinačnim bitovima, međutim, za razliku od prethodno opisanih operacija za koje praktično postoji jedan uobičajeni/optimalni postupak (koji se koristi gotovo uvek), za očitavanje bita postoje dva različita uobičajena pristupa, i upravo zato smo kraću diskusiju o operaciji očitavanja vrednosti bita ostavili "za pred kraj".
Varijanta 1
Sa jedne strane, sasvim je moguće (u praktičnom smislu), * očitati vrednost bita na određenoj poziciji uz upotrebu standardne maske kakvu smo već koristili:
| a | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
| m (maska) | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| a = a & m | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
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 koja se očitava
.... pri čemu se kao rezultat dobija: ili 0, ili (praktično), "kopija" promenljive m (koja predstavlja masku).
Varijanta 2
U većini svakodnevnih situacija (budući da prethodni algoritam nije 'baš' pogodan za ekonomično zapisivanje u jednoj liniji koda), tipično se sprovodi postupak preko koga se traženi bit prvo pomera na najnižu poziciju, i potom se očitava vrednost krajnjeg desnog bita (ili, zapravo - vrednost traženog bita).
Ako je potrebno očitati npr. 4. bit sa desne strane u promenljivoj a, traženi bit se prvo dovodi na krajnju desnu poziciju, * preko operatora >>:
| a | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
| p | 4 | |||||||
| a >> (p - 1) | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
U drugom koraku - uz korišćenje bitovskog operatora konjunkcije - rezultat se svodi na 0 ili 1 i pamti se preko dodatne promenljive (pri čemu se vrednost promenljive a neće promeniti (što ćemo dodatno objasniti na kraju odeljka)).
| x | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| r = x & 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 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;
Cela naredba se zapisuje u jednom redu, u kodu nema pomoćnih promenljivih, * a sama promenljiva a zadržava (prethodnu) vrednost. **
Invertovanje ("obrtanje") bita na poziciji p
Sa jedne strane, invertovanje pojedinačnog bita je zapravo krajnje jednostavna operacija (možda i najjednostavnija od svih), međutim, sa druge strane (bez obzira na prethodno 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 u ovom slučaju neće biti od pomoći), i stoga smo operaciju invertovanja pojedinačnih bitova ostavili za kraj.
Bilo kako bilo, dovoljno je samo maskirati određeni bit ....
| m | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| p | 4 | |||||||
| m << (p - 1) | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
.... i pozvati bitovski operator XOR ....
| a | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| m (maska) | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| a = a ^ m | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
.... koji (sada je jasno), deluje "kao poručeno" za ovakav zahvat:
- ukoliko je bit prethodno bio isključen - biće uključen (0 ^ 1 = 1)
- ukoliko je bit bio uključen - biće isključen (1 ^ 1 = 0)
Operator XOR (bilo da je u pitanju bitovska ili "nebitovska" varijanta), ima i brojne druge primene (o čemu ćemo pisati u budućim člancima), a za sam kraj vam ostavljamo da uživate u jednostavnosti i eleganciji algoritma za invertovanje pojedinačnih bitova.