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> |
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 Kôd:
00000110 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 Generalno, ti bi uvek trebao da dobiješ negativan broj ako je unet pozitivan i obrnuto, jer je prvi bit uvek oznaka +- ( 0 = +, 1 = -) |
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? :D |
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? |
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. |
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 :D]? 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 :)
|
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 |
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; } |
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... |
broj ne moras da stepenujes vec pomeras bitove isto
maska = ~(~0 << n)<< p |
Vreme je GMT +2. Trenutno vreme je 07:48. |
Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.