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:

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)

Kada to što je upisano u polje maskiras sa AND operatorom koji znaci "I JEDNO I DRUGO", za svaku masku pojedinačno dobijas:
E sada, postoje razne operacije, pored AND, znas da postoji NOT, OR, XOR, XNOR

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š:
a to nije ono što ti treba.

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

Ma.. :) To beše čisto razumevanja radi (pošto je Gruja već dao primer sa pomeranjem), a i moje znanje C je.. sećanje :)

... od pre jedno 15 godina :)

već sam odavno zaboravio na ove fensi "shift" izraze.

haha... jbte, i mene ste zbunili...

Da ti ne pishem detaljno, evo link pa pogledaj:
http://www.vipan.com/htdocs/bitwisehelp.html

Tu je sve lepo objasnjeno...

Poenta price je da ti koriscenjem bitwise operatora dobijash neku drugu vrednost u registru...

Dakle treba da znash logicke operacije AND, NOT, OR i XOR.

e sada recimo imash broj 64 to je osam keceva: 11111111
i imash masku koja je 63 to je sedam keceva i nula: 11111110
i ukoliko uradish XOR opet cesh da dobijesh 64 iliti 11111111

e sada ti rece da ti treba komplement... koji potpuni ili nepotpuni?!? nepotpuno komplementiranje je u stvari negacija dakle koristicesh ~ a za potpuni komplement samo cesh na to sve da dodash 1...

Kao prvo, 64 nije 11111111.
Kao drugo, 11111111 XOR 11111110 nije 11111111
Već 1.

:)

u jbte... da da da... hahaha... kakav sam kreten... sorry osam keceva je 255 haha... 1000000 je 64... zajebo sam se...

Sorry ponovo...

al ste ga iskomplikovali.... :D

sve se svodi na ono sto je gruja vec napisao: ako neku vrednost A XOR-ujes sa nekom maskom (nizom bita), binarno gledano na pozicijama gde je u maski 1, u rezultatu ce ta pozicija da ima invertovanu vrednost iz A, a tamo gde je u maski 0 nista se nece promeniti...

znaci tako mozes da togglujes vrednosti nekih bitova u flagovima, ako su upaljeni ugasis ih i obrnuto (odnosno invertujes im vrednost, matematicki gledano). Znaci XOR je za toggle, ako zelis da upalis neki bit pomocu maske onda koristis OR, ako zelis da ga ugasis onda koristis AND sa invertovanom maskom... i tako ti rade ti racunari, prosto :)

btw, ako ti i dalje nije sasvi leglo kako ovo radi, otvori windows kalkulator, prebaci ga u scientific mod i igraj se malo sa binarnim brojevima... kroz praksu se najbolje kapira..

E sad mi je delimično jasno: Ja ne mogu samo nad onim delom maske koji je obeležen jedinicama da vršim operaciju već nad ulaznim podatkom i celom maskom, zato mora ^ a ne ~ ... tako? :)

E sad još pravljenje maski... ja sam razumeo da se uzmu sve nule, pa se doda n broj jedinica pa se sve to pomera za pomeraj p i kako se pomera tako se dodaju nule s desne strane, right? I to radi ovaj kod:
maska = ~(~0 << n) << p;
Šta npr. raditi kad između jedinica treba da imam x nula u maski? :P npr. 000110100
Kako to radi? :D Jel može neko ovu liniju gore (bold) da mi objasni do detalja (mi smo koristili ovaj oblik... tačnije, u jednom zadatku smo koristili y = x >> p-n+1; pa onda maska = ~(~0<<n); za neko poravnjanje s desne strane)?

@LiquidBrain: Sad ću da pogledam taj link

Prvo sto treba da uradis je da dobro skapiras sta je AND, OR, XOR, NOT...

AND: 1 i 1 = 1, sve ostalo daje 0
OR: 0 i 0 = 0, sve ostalo daje 1
...
Pa onda tako da odlucis koji ces operator da koristis. Pored toga treba da znas precedence, odnosno kojim redom se izvrasavaju operacije

Dakle, ako sam lepo shvatio, da bi dobio recimo masku 000110100 treba da odradim:
~(~(~(~0 << 2) << 1) << 1) << 2)

...znači imali bismo:

000000000000 početna vrednost
111111111111 ~ izvršeno nad prethodnom maskom
111111111100 << 2 izvršeno nad prethodnom maskom
000000000011 ~ izvršeno nad prethodnom maskom
000000000110 << 1 izvršeno nad prethodnom maskom
111111111001 ~ izvršeno nad prethodnom maskom
111111110010 << 1 izvršeno nad prethodnom maskom
000000001101 ~ izvršeno nad prethodnom maskom
000000110100 << 2 izvršeno nad prethodnom maskom

Tako? :D

A da probaš pa vidiš..? ;)

Hah, jeste! :)

Evo šta sam uradio "na papiru" (na kompu uz windowsov calculator)
000000001000 = 8
000000110100 = maska
000000111100 = 60 (posle XORovanja)

A moj program:
...kad mu unesem 8 stvarno vraća 60. Super :)

Hvala svima!

Ево и мало теже артиљерије на задату тему:
http://graphics.stanford.edu/~seander/bithacks.html

ф