|
Sva početnička pitanja Sva početnička pitanja bi trebala da se postavljaju u ovom forumu, a ako se pretvori u kvalitetnu diskusiju interesantnu svima - prebacićemo je u odgovarajući forum. Molimo "znalce" da ne omalovažavaju početnike, ako žele da pomognu svi ćemo biti zahvalni, ako ne žele, neka preskoče ovaj forum. |
|
Alati teme | Način prikaza |
29. 10. 2007. | #1 |
emperor Selassie
Grand Master
|
C - operacije nad bitovima i maske
Jel ima neko neki (kratak) tekst o maskama kad se radi sa operacijama nad bit(ov)ima i uopšte o operacijama nad bitima? Radimo C na faksu pa sam sve razumeo osim ovog. Takođe, imam jedan zadatak, pa bi možda nekome bilo lakše da mi pojasni malo to na primeru. Zadatak glasi ovako:
"Napisati program na C-u dz5Inver.c koji u zadatom celom broju od zadate pozicije p posmatra n-bitno polje (n zadato) i invertuje bitove u polju, a zatim prikazuje tako izmenjen ceo broj. Zadate vrednosti p i n moraju biti razumne pozitivne vrednosti. Pretpostavlja se da se bit pozicije 0 nalazi na desnom kraju. Potrebno je da program obrađuje više skupova ulaznih podataka." Ova poslednja rečenica govori to da se radi o petlji while (1) koja se izvršava dok recimo ne unesemo nulu, i to je nebitno. Sad, ja razumem šta ovde treba da se uradi (ili se barem nadam da razumem): Npr. imam broj 8, binarno 00001000 i p stavimo recimo na 4 a n na 3, tako da nam je maska pretposlednje 3 cifre (tako?) tj. 00001110. Ona invertujemo binarne cifre samo u toj maski kod našeg broja, i dobijamo 00000110 što je decimalni broj 6. Ako je ovo što sam rekao tačno, onda sam ja to super shvatio, ali ne znam kako napraviti i koristiti masku, odnosno kako odraditi zadatak Takođe, napominjem da ne želim samo rešenje zadatka, jer ću imati gomilu ovakvih zadataka a ne želim da vas smaram svaki čas da mi radite zadatke Evo nečega: Kôd:
#include <stdio.h> main() { int x,p,n,y; /* x je ulaz, y izlaz, p pozicija a n duzina bitnog polja */ printf("Unesite ceo broj: "); scanf("%d", &x); printf("\nUneti poziciju i sirinu polja u reci: "); scanf("%d %d", &p, &n); y = x>>p-n+1; /* ovo sam uzeo iz nekog prethodnog zadatka, tako da ovde verovatno treba nesto drugo da stoji :( */ y = ~y; /* ovo sam ja nesto brljao, tako da ovde SIGURNO treba nesto drugo da stoji :) */ printf("Rezultat: %d\n", y); } |
29. 10. 2007. | #2 |
Goran Pilipović
Sir Write-a-Lot
|
Evo jednostavnog primera, kome god sam ovako objasnjavao - shvatio je
imas recimo jedan bajt u kome cuvas neko flagove. Bajt je velicine 8 bitova i da cuvas space (to se nekada puno radilo kada se programiralo, sada niko i ne vodi racuna o tome, zato valjda i moderan softver tako zdere memoriju) ... ti mozes da 8 flagova zapises u 1 bajt umesto za svaki posebno... evo recimo, prakticno u sql: imate u users tabeli polje: ... send_newsletter tinyint unsigned not null default 0, send_offers tinyint unsigned not null default 0, send_email tinyint unsigned not null default 0, .. Znaci ako je neko od tih polja 1 onda korisnik "zeli" ako je 0 onda "ne zeli". I standardna procedura je : if ($user->send_newsletter > 0) { // posalji mu newlsetter } else if ($user->send_offers > 0) { // posalji mu offer... i tako dalje... Medjutim, mozes da koristis samo jedno polje za sva 3 flaga tako sto definises recimo send_options tinyint unsigned not null default 0; i refinises recimo MASKE: define ('SEND_NEWSLETTER', 1); // binarno 00000001, odnosno 2^0 define ('SEND_OFFER', 2); // binarno 00000010, odnosno 2^1 define ('SEND_EMAIL', 4); // binarno 00000100, odnosno 2^2 define ('SEND_NESTO', 8); // binarno 00001000, odnosno 2^3 define ('SEND_DRUGO', 16); // binarno 00010000, odnosno 2^4 i kada pokupis polje `send_options` iz baze, proveravas: if ($user->options & SEND_NEWSLETTER) { // posalji mu newlsetter if ($user->options & SEND_OFFER) { // posalji mu offer... if ($user->options & SEND_EMAIL) { // posalji mu mail... Na primer, ako je user izabrao da mu se salje offer i email, onda je upisano u polje: 00000110 jer je offer 00000010 a email 00000100, I onda je računica preko OR (bar jedna 1 u oba polja, znači 01, 10, 11) Kôd:
00000010 00000100 ----------- 00000110 - preko OR ^^ - u ova 2 slučaja se pojavljuje bar jedna 1 Kôd:
00000110 00000010 // SEND_OFFER = 2, binarno 00000010 ----------- 00000010 - sto znaci da je vece od nule i znaci da hoce da ^ samo tu je 1 u oba slucaja U tvom slucaju se trazi inverzija bitova u polju, znaci sto je bilo 0 da postane 1 i obrnuto. Dakle ako imas broj 4, cija je binarna vrednost: $value = 1000 $invertovani_broj = ~$value Dobijaš: $invertovani_broj = 0111 Jedino što treba da paziš je sada broj bitova, a ako koristipš int to zavisi od maxint na sistemu, pa treba da ograničiš na neki razuman broj, recimo ako probaš samo ovako bez obzira na broj bitova, dobićeš: $value = 1000 $inverted_value = 11111111111111111111111111110111; Što je tačno jer je $value u stvari: 00000000000000000001000 a ne samo 1000 kako bi ti poželeo jer je int u stvari 4-bajtni broj (4x8 bitova) na 32-bitnim sistemima. Ako ideš sa left / right shift, nećeš dobiti ono što se traži "ivertovane vrednosti bitova" jer kada uradiš >> (right shift) za broj 00001000 dobijaš: Kôd:
00001000 > right shift za jedno polje 00000100 ^ sada je ovde Generalno, ti bi uvek trebao da dobiješ negativan broj ako je unet pozitivan i obrnuto, jer je prvi bit uvek oznaka +- ( 0 = +, 1 = -)
__________________
Goran Pilipović a.k.a. Ugly Fingers Bradley f.k.a. bluesman I don't always know what I'm talking about but I know I'm right! Poslednja izmena od bluesman : 29. 10. 2007. u 21:24. |
2 članova zahvaljuje bluesman za poruku: |
29. 10. 2007. | #3 |
emperor Selassie
Grand Master
|
Razumem ja tebe blues, bar donekle, ali ti si objasnio ovde menjanje bitova nad celim brojem, što je ok, ali ja treba da kreiram masku i da zamenim bitove samo na određenom polju. E to mene buni: Kako u C-u da napravim masku, da je "primenim" na određeni broj i onda da izvršim operaciju (u ovom slučaju komplementiranje) nad tim brojem ali samo u okviru maske
Ili ja opet propuštam nešto? |
29. 10. 2007. | #4 |
Dejan Grujic
Professional
Datum učlanjenja: 29.09.2005
Poruke: 380
Hvala: 9
64 "Hvala" u 40 poruka
|
Za pocetak bitovi se obicno pisu kao i svi drugi brojevi - tako da je bit sa najmanjom tezinom skroz desno. Tako da i brojanje kreces sa desne strane na levu.
Ovo je manje bitno. Vise je bitno kako da napravis masku i sta da radis sa njom. Kako napraviti masku? Za tvoj primer, maska bi bila 01110000 (tj. samo sam obrnuo da se broji sa desne strane). Masku pravis tako sto napravis n jedinica na pocetku, a onda ih pomeris za p mesta. Kako napraviti broj koji ima n jedinica? Gledaj na primerima: binarno => decimalno 1 => 1 11 => 3 111 => 7 1111 => 15 Formula je: x = pow(2, p) - 1, gde je pow funkcija za stepenovanje. Zaboravio sam tacno kako se stepenuje u c-u, u principu mozes i u petlji da mnozis. Sad ti treba da tako dobijeni broj pomeris za n bita. Za to imas operator u C-u, <<, tj. y = x << n U ovom trenutku imas masku. Kako nju iskoristiti da obrnes bitove? Treba ti operacija zvana "ekskluzivno ili" (poznato i kao XOR), koja obrce bitove tamo gde je maska 1, a ne dira nista tamo gde je 0. Ako me secanje ne vara, to je operator ^ Znaci rezultat je z = broj ^ y Moze ovo i na jos koji nacin, ali mene sad zanima ovo - da li si cuo za ekskluzivno ili? Da li znas osnovne logicke operacije sa bitovima? Zanima me da li ste to radili na faksu ili se pojavilo tek sada sa C-om. I na kom si to faksu? |
29. 10. 2007. | #5 |
I'm a PC too.
Wrote a book
Datum učlanjenja: 05.06.2005
Lokacija: Kanada
Poruke: 1.354
Hvala: 82
130 "Hvala" u 89 poruka
|
Da bi invertovao bit, koristiš XOR (još se naziva i EOR; exclusive OR). Mislim da se u C koristi ^ da bi se izvršila ova operacija.
Mislim da će jedno: rezultat = broj ^ maska; biti dovoljno, valjda će neko da me ispravi ako ne valja //update: eto Gruja me preduhitrio dok sam ja proveravao na Wikipediji koji je simbol u C za XOR. Valja, znači.
__________________
Commercial-Free !!! Poslednja izmena od degojs : 29. 10. 2007. u 23:05. |
29. 10. 2007. | #6 |
emperor Selassie
Grand Master
|
U pitanju je Viša PTT, učimo Osnove programiranja, C, i pravo ko grom iz vedra neba operacije na bitovima. Logičke operacije znam (valjda... radili smo to ranije ), ali me te maske užasno bune. Mislim, znam ja kako to radi, ali nisam znao kako da ih pravim i koristim. Nadam se da ću skapirati iz ove pretposlednje poruke. I da, jel ste sigurni da treba XOR, odnosno ^ za prebacivanje nula i jedinica (i obrnuto) [verujem da jeste ]? Mi smo imali neki zadatak i čini mi se da smo za menjanje bitova koristili ~... ma, sad sam se skroz zbunio :/ idem da spavam, sutra ću moći da razmišljam
Poslednja izmena od Nemanja Avramović : 29. 10. 2007. u 23:17. |
29. 10. 2007. | #7 |
novi član
Na probnom radu
Datum učlanjenja: 31.07.2007
Poruke: 23
Hvala: 0
7 "Hvala" u 5 poruka
|
naravno da mora xor posto treba da diras tj invertujes samo bitove pod maskom a tamo gde su bitovi u masci 0 ne diras nista...
mozda ce ti biti lakse: not A je isto sto i A xor #FFFFFFFF kada ti treba da invertujes npr. bitove 8-23 uradis: A xor #00000FF0 |
29. 10. 2007. | #8 |
I'm a PC too.
Wrote a book
Datum učlanjenja: 05.06.2005
Lokacija: Kanada
Poruke: 1.354
Hvala: 82
130 "Hvala" u 89 poruka
|
Pa šta te buni sa maskama? Imaš početnu poziciju (p) i broj bitova (n) koje trebaš da postaviš na 1, s tim da je prvi bit (najmanja vrednost) pozicija 0.
Možeš da sabereš potencije broja 2 na tim pozicijama.. Ovako nekako: int kreirajMasku( int p, int n ) { maska = 0; for( int i = p; i<p+n; i++) maska += pow(2,i); return maska; }
__________________
Commercial-Free !!! |
29. 10. 2007. | #9 |
emperor Selassie
Grand Master
|
Uf, uf, uf, ajde polako. Izgleda da nisam pratio predavanje kako treba. Kapiram ja šta je XOR i kako radi. Za šta je onda ~ operator u C-u? Evo vidim u svesci piše samo ~a = komplement od "a"
Dalje, razumeo sam da se maska pravi tako što stavim n jedinica na početku pa pomerim masku u stranu (recimo napravim 00000111 pa pomeram za 2 mesta ulevo i dobijem 00011100) i onda izlaz = ulaz OPERACIJA maska - tako? Jel može onda neko da mi da klasičan primer. Ako unesem broj 8, i napravim masku 00001110, šta dobijam na izlazu za operaciju XOR? Pozdrav i hvala unapred. Pišemo se sutra edit: Degojs, hvala ti, sad tek videh tvoju poruku. Detaljnije ću je analizirati sutra, sad sam stvarno jako pospan a rano idem u školu... |
29. 10. 2007. | #10 |
novi član
Na probnom radu
Datum učlanjenja: 31.07.2007
Poruke: 23
Hvala: 0
7 "Hvala" u 5 poruka
|
broj ne moras da stepenujes vec pomeras bitove isto
maska = ~(~0 << n)<< p |
|
|
Slične teme | ||||
Tema | Početna poruka teme | Forum | Odgovori | Poslednja poruka |
Bitwise operacije + Osnovne strukture podataka | MrSteel | Flash | 5 | 12. 05. 2007. 20:24 |