nav_dugme codeBlog codeBlog
  • početna Početna stranica
  • Sačuvani članci Sačuvani članci
  • Učionica
  • Saveti
  • Zanimljivosti
  • Kontakt

Operacije sa bitovima u programskom jeziku C

Viber
zoom_plus zoom_minus bookmark

Uvod

Uobičajeni logički operatori u programskom jeziku C: &&, ||, ^^ i !, standardno uzimaju u obzir vrednosti operanada u celosti, pri čemu se 0 interpretira kao "NE" (ili "NETAČNO"), dok se bilo koja vrednost različita od 0 (ne samo 1), tumači kao "DA" (ili "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 "dobro dođe".

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

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

Veoma zanimljive mogućnosti (sa nekima ćemo se upoznati u ovom članku; sa drugima - u budućim člancima).

Kratak pregled bitovskih operatora u C-u

U programskom jeziku C, pristup pojedinačnim bitovima u logičkim operacijama postiže se upotrebom specijalizovanih operatora:

  • & - konjukcija (bitovsko "I")
  • | - disjunkcija (bitovsko "ILI")
  • ^ - XOR (bitovsko isključivo "ILI")
  • ~ - invertovanje (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.

Shodno navedenim uslovima: za konjukciju, disjunkciju i XOR važi da se bit na poziciji p u rezultatu, dobija kao rezultat operacije nad bitovima na poziciji p u operandima a i b (a u slučaju operacije invertovanja, kao rezultat invertovanja bita na poziciji p u promenljivoj a).

Situacija u kojoj ne možemo direktno pristupati pojedinačnim bitovima može delovati pomalo problematično (i svakako zaslužuje pažnju), ali, uz pažljivo promišljanje, možemo uvek 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 konjukcije označava sa ^, dok isti operator u C-u predstavlja bitovski operator ekskluzivne disjunkcije - bitovski XOR (a ima i drugih razlika). Takođe, oznake 0 i 1 ćemo koristiti umesto istinitosnih vrednosti ⊤ ("te") i ⊥ ("ne-te").

(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 konjukciju (logičko I) prikazana je na sledećoj slici:

Logičko I - Tablica Istinitosti
Slika 1. - Logičko I daje vrednost "TAČNO", samo kada su oba uslova zadovoljena

Ukratko: u opštem smislu, rezultat je 1 samo ako su oba uslova tačna (ili praktično - ako oba bita imaju vrednost 1).

Bitovski operator & 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 konjukcija primenjuje se na svaki par bitova nezavisno i rezultat će biti 1 samo na onim pozicijama gde oba bita imaju vrednost 1.

Iako su celobrojne promenljive (dugi niz godina unazad) tipično 32-bitne, u primerima ćemo se (zarad preglednosti) zadržati na 8-bitnim neoznačenim promenljivama.

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. - Logičko ILI daje vrednost "TAČNO" onda kada je bilo koji od dva uslova zadovoljen

Ukratko: u opštem smislu, rezultat je 1 ukoliko je bilo koji od dva uslova tačan (praktično - ukoliko bilo koji od dva bita ima vrednost 1).

Operator | je takođe 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) prikazana je na sledećoj slici:

Isključivo ILI - Tablica Istinitosti
Slika 5. - Ekskluzivna disjunkcija daje vrednost "TAČNO" samo ukoliko su operandi različiti

Ukratko: rezultat je 1 onda kada su dva uslova različita (praktično - ukoliko par bitova sadrži jednu nulu i jednu jedinicu), dok je, ukoliko oba uslova imaju istu vrednost, rezultat 0.

Kada gornju tablicu primenimo na dve celobrojne vrednosti preko bitovskog operatora ^, dobijamo 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:

Isključivo ILI - Tablica Istinitosti
Slika 7. - Logičko "NE" daje vrednost "TAČNO" ukoliko se na ulazu pojavi vrednost "NETAČNO" i obrnuto.

Ukratko: ukoliko je uslov (bit) prethodno imao vrednost 1, dobija vrednost 0; ukoliko je imao vrednost 0, dobija vrednost 1.

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

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

Isključivo ILI - Primer
Slika 8. - U skladu sa tablicom negacije, operator ~ "obrće bitove" (0 postaje 1; 1 postaje 0).

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, operator << pomera sve bitove promenljive a za n mesta ulevo, pri čemu važe sledeća pravila:

  • početni bitovi (sa vrednošću 1) 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.

.... ali će zato neoznačena osmobitna promenljiva sa vrednošću 128, posle operacije a << 1 imati vrednost 0!

Opštiji 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, moramo uvek voditi računa o levim bitovima promenljive, jer se lako može desiti (kao u slučaju sa gornje slike) da neke od bitova praktično izbrišemo!

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 pomeramo), upotrebom operatora << određenu vrednost lako možemo 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:

  • svi bitovi (jedinice) 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.

Opšti 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 moramo uvek voditi računa o jedinicama sa (ovoga puta) desne strane.

Međutim, ukoliko operator >> koristimo 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 prethodno navedenom) da ćemo uvek dobiti korektan rezultat.

Maskiranje bitova

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

Operacija koja se popularno naziva "maskiranje bitova", podrazumeva (tipično, ali ne i uvek; videćemo u nastavku), upotrebu pomoćne promenljive koja ima isključene sve bitove, osim na jednoj poziciji - na onoj 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), koji se potom, preko operatora pomeranja ulevo a = a << (p - 1);, postavi 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, strogo 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!

Verujemo da je čitaocima poznato od ranije da ni naredba kao što je a + 1 ne dovodi do uvećanja vrednosti promenljive a (a napomenimo i to da smo na slici #11, naredbu dodele izostavili isključivo zarad preglednosti).

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

		
a = a << (p - 1);
		
	
Slika 13. - Naredba kojom se (ovoga puta za prave) 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 (zadavanje vrednosti 1 datom bitu), potrebno je 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. - Logička disjunkcija ostaviće sve bitove - osim maskiranog - u prvobitnom stanju, a maskirani bit će (obavezno) biti uključen.

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

I ovoga puta (zarad preglednosti) na prvoj slici smo izostavili naredbu dodele, koju bismo u kodu (naravno) koristili, a isto važi i za primere u narednim odeljcima.

Isključivanje pojedinačnog bita

Za isključivanje određenog bita, prvo je potrebno napraviti standardnu masku ....

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

.... zatim je potrebno invertovati masku (preko operatora ~ promeniti vrednost svih bitova, tako da nule postanu jedinice, a jedinice nule) i potom pozvati operator konjukcije (bitovsko I)

Isključivanje bita - Primer
Slika 17. - Upotrebom invertovane maske, svi uključeni bitovi će ostati uključeni, dok će prvobitno uključeni bit na poziciji p na kraju biti isključen.

Preko invertovane maske, pobrinuli smo se 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 bitova postoje dva različita pristupa, pa smo zato kraću diskusiju o ovoj operaciji ostavili "za pred kraj".

Varijanta 1

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

Očitavanje vrednosti bita - varijanta 1
Slika 18. - Očitavanje vrednosti bita na poziciji p - preko uobičajene maske.

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 0, ili stepen broja 2 
           // koji odgovara poziciji koju očitavamo
		
	
Slika 19. - Implementacija algoritma sa prethodne slike.

.... pri čemu se kao rezultat dobija: 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 njegova vrednost.

Ako želimo da očitamo (na primer) 4. bit sa desne strane u promenljivoj a, prvo je potrebno, preko operatora >> dovesti četvrti bit a na prvu poziciju:

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).

.... i potom, koristeći bitovski operator konjukcije, svesti rezultat na 0 ili 1 - koji se pamti preko dodatne promenljive.

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

Programski kod je još jednostavniji (nego što bi se dalo naslutiti 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.

U primerima na gornjim slikama, zarad preglednosti smo koristili pomoćnu promenljivu x (u praksi tipično nema potrebe za uvođenjem pomoćnih promenljivih).

Da pojasnimo dodatno: vrednost promenljive a smešta 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" 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 da maskiramo određeni bit ....

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

.... i pozovemo bitovski operator 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 ga isključuje (ako je imao vrednost 1).

.... koji (sada vidimo), 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.

Autor članka Nikola Vukićević Za web portal www.codeblog.rs
Napomena: Tekstovi, slike, web aplikacije i svi ostali sadržaji na sajtu www.codeblog.rs (osim u slučajevima gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.codeblog.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo drugo korišćenje u komercijalne svrhe, bez eksplicitnog pismenog odobrenja autora.
© 2020-2023. Sva prava zadržana.
Viber
početna Početna > Članci > Operacije sa bitovima u programskom jeziku C

Info & povezani članci Info o članku - dugme

Info

trejler_sat Datum objave: 08.01.2020.

trejler_sat Poslednja izmena: ----

trejler_dokument Jezici: C

trejler_teg_crveni Težina: 8/10

Povezani članci

Zašto baš binarni brojevi? Pozicioni brojevni sistemi Binarno stablo pretrage Aritmetika velikih brojeva BFS i DFS - Pronalaženje putanje kroz lavirint IT termini Dinamičko programiranje Argumenti komandne linije Strukture podataka Regularni izrazi - napredna pretraga teksta Ostali članci
Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live.
John Woods
codeBlog codeBlog
Projekat posvećen popularizaciji kulture i veštine programiranja.
Napomena: Tekstovi i slike na sajtu www.codeblog.rs (osim u slučajevima, gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.codeblog.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo drugo korišćenje u komercijalne svrhe, bez eksplicitnog odobrenja autora.
© 2020-2023. Sva prava zadržana.
Facebook - logo
Instagram - logo
LinkedIn - logo
Twitter - logo
E-mail
Naslovna
   •
Uslovi korišćenja
   •
Obaveštenja
   •
FAQ
   •
Kontakt