C - operacije nad bitovima i maske

[Nemanja Avramović]

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:

#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);
}

[bluesman]

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)

00000010
00000100
-----------
00000110 - preko OR
     ^^    - u ova 2 slučaja se pojavljuje bar jedna 1

Kada to što je upisano u polje maskiras sa AND operatorom koji znaci "I JEDNO I DRUGO", za svaku masku pojedinačno dobijas:

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

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š:

00001000
    > right shift za jedno polje
00000100 
     ^ sada je ovde

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

[Nemanja Avramović]

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?

[Gruja]

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?

[degojs]

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.

[Nemanja Avramović]

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

[filjo]

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

[degojs]

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;
}

[Nemanja Avramović]

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

[filjo]

broj ne moras da stepenujes vec pomeras bitove isto

maska = ~(~0 << n)<< p