Zadaci sa bitovima, ili kako već da ih nazovem..

[forrest_gump]

Ma koliko mi glupo bilo da otvaram ovu temu, ali nisam bash uspela da pronadjem neke korisne sadrzaje na netu, a u vezi sa zadacima koji me chekaju na ispitu iz programiranja1, a koje jednostavno ne znam kako da nauchim da reshavam.
Uchenje napamet ne vidim kao reshenje, jer nikad ne uchim tako i jer ne mogu da zapamtim, a i glupo mi je narochito da C uchim napamet..
Shvatate i sami poentu - zelim da nauchim da radim zadatke sa bitovima, ali ne znam kako, jer ja tu nishta ne razumem..
Da biste shvatili o chemu tachno govorim evo i par zadataka:

1.Napisati program na jeziku C koji:
a) chita sa tastature ceo broj n, velichine chetiri bajta, zadat u heksadecimalnom obliku.
b) odredjuje i prikazuje na ekranu poziciju (od bita najmanje tezine) prvog i poslednjeg pojavljivanja binarne kombinacije 101 u zadatom broju n

2.Napisati program na jeziku C koji:
a) chita sa tastatre ceo broj n, velichine chetiri bajta, zadat u decimalnom ili heksadecimalnom obliku,
b) odredjuje i prikazuje na ekranu broj parova susednih bitova zadatog broja koji imaju razlichite vrednosti (u binarnom obliku: 01 ili 10).

i td.

Iako sam iz drugog predmeta uchila operacije sa bitovima tj. binarnim brojevima i tome slichno i iako relativno razumem sve to, ne mogu da shvatim kako se ovi zadaci rade (nije da nemam reshenja istih, ali... )...

Imate li neku pametnu ideju?

Unapred zahvaljujem.

pozzzz

Edit:
---------------> uglavnom nije problem da skapiram kako se rade ovi zadaci pod a), ali one operacija sa bitovima nemam blage veze... O.O

[rile]

int je obično 4-bajta dužine. Kada pretvoriš ulaz u broj, imaćeš, recimo, promenljivu po imenu "broj" dužine 4 bajta sa vrednošću koju si izračunala iz ulaza.

int broj;

to je, dakle, 32 bita podataka.

Jednostavan način (ali ne obavezno i najoptimalniji) je da koristiš operator pomeranja bitova "shift":

int pozicija = 0;
const int maska = 5; /* u binarnom obliku 101 */
while (broj > 0)
{
  if ((broj & maska) == maska) /* Binarna logicka operacija "I". Na primer 1001 & 101 ce dati "1" */
  {
    printf("Pozicija: %d\n", pozicija);
  }
  broj = broj >> 1; /* Pomeri bitove jedno mesto udesno "binary shift right". Na primer 0100 ce posle ovoga biti 0010 */
  pozicija++; /* Povecaj poziciju */
}

Nadam se da ovo pojašnjava stvari?

[forrest_gump]

mislim da je jedini razlog zashto ovo dobro objashnjenje ne pomaze to shto je moj mozak ochigledno ogranichen da udje u sushtinu sabiranja, oduzimanja, maskiranja i shiftovanja bitova.. mislim, sve ostalo iz programiranja 1 mogu da razumem (jer je u principu sve to opipljivo), ali ovo nema shanse...

ipak, hvala na odvojenom vremenu.

[Eddy]

Cisto ovako jedno pitanje. Da li znas Bulovu algebru?

[forrest_gump]

O.O
Nope..

je l bi trebalo? O.o

[Eddy]

Pa za pisanje ovakvih zadataka, po mom skromnom znanju, ako ne znas proste logicke operacije neces moci ni da napises valjan program.
Nauci tablice logickog sabiranja i mnozenja. pa posle nadji (sigurno ste negde radili) u nekoj tvojoj svesci gde ste vezbali operacije sa bitovima.
Kad shvatis taj teorijski deo, tek onda pristupi programiranju.

[forrest_gump]

jutros sam definitivno bila pospana kad sam odgovarala na tvoje pitanje.. <_<

dakle, naravno da znam osnovne logichke operacija sa nulama i jedinicama, ali mi to ne pomaze u reshavanju zadataka u C-u...

Boze, koji sam debil da kazem da ne znam neshto shto znam..

[Monk Psycho]

zadaci sa vise elektor ako uspem da nadjem moje carobne puskice stavicu ih ovde (nazalost to je bilo jedino resenje u mom slucaju)

[forrest_gump]

nikad nisam uchila sa pushkica - bilo bi to neobichno iskustvo..

[rile]

Nije tako teško kao što možda deluje.

Logička operacija "i" ili logičko množenje dva jednobitna broja: 1 i 1 daje 1 a sve ostale kombinacije daju 0
Logička operacija "ili" ili logičko sabiranje daje 1 ako je barem jedan operand 1


U C-u operatori koji se izvršavaju nad svakim bitom datih operanda rade datu logičku operaciju bit-po-bit za svaki bit tih operanda.

Tako recimo bit-logička operacija "i" odnosno operator "&" nad binarnim brojevima

10110
i
00101
daju:
00100

Slično, bit-logička operacija "ili":
10110
ili
00101
daju:
10111


Izraz "maska" je uobičajen u programiranju kada se bit-logičko "i" koristi za "isključivanje" određenih bitova. Naime svaka 0 u "masci" će dati nulu bez obzira da li je u drugom broju na tom mestu jedinica. A ovo mi upravo govori da sam napravio grešku u primeru koji sam dao. Maska ne treba da bude "101" nego "111". Da li vidiš zbog čega?

Dakle moj prethodni primer je neispravan, a ovo bi trebalo da bude bolje:

int pozicija = 0;
const int maska = 7; /* u binarnom obliku 111 */
const int trazenakombinacija = 5; /* u binarnom obliku 101 */
while (broj > 0)
{
  if ((broj & maska) == trazenakombinacija) /* Binarna logicka operacija "I". Na primer 1101 & 111 ce dati "101" */
  {
    printf("Pozicija: %d\n", pozicija);
  }
  broj = broj >> 1; /* Pomeri bitove jedno mesto udesno "binary shift right". Na primer 0100 ce posle ovoga biti 0010 */
  pozicija++; /* Povecaj poziciju */
}

Naravoučenije: ne piši primere na brzinu.

[forrest_gump]

rile kaže:

Nije tako teško kao što možda deluje.

Logička operacija "i" ili logičko množenje dva jednobitna broja: 1 i 1 daje 1 a sve ostale kombinacije daju 0
Logička operacija "ili" ili logičko sabiranje daje 1 ako je barem jedan operand 1


U C-u operatori koji se izvršavaju nad svakim bitom datih operanda rade datu logičku operaciju bit-po-bit za svaki bit tih operanda.

Tako recimo bit-logička operacija "i" odnosno operator "&" nad binarnim brojevima

10110
i
00101
daju:
00100

Slično, bit-logička operacija "ili":
10110
ili
00101
daju:
10111

vec sam rekla da ovo znam.. <_<

rile kaže:

Izraz "maska" je uobičajen u programiranju kada se bit-logičko "i" koristi za "isključivanje" određenih bitova. Naime svaka 0 u "masci" će dati nulu bez obzira da li je u drugom broju na tom mestu jedinica. A ovo mi upravo govori da sam napravio grešku u primeru koji sam dao. Maska ne treba da bude "101" nego "111". Da li vidiš zbog čega?

Dakle moj prethodni primer je neispravan, a ovo bi trebalo da bude bolje:

int pozicija = 0;
const int maska = 7; /* u binarnom obliku 111 */
const int trazenakombinacija = 5; /* u binarnom obliku 101 */
while (broj > 0)
{
  if ((broj & maska) == trazenakombinacija) /* Binarna logicka operacija "I". Na primer 1101 & 111 ce dati "101" */
  {
    printf("Pozicija: %d\n", pozicija);
  }
  broj = broj >> 1; /* Pomeri bitove jedno mesto udesno "binary shift right". Na primer 0100 ce posle ovoga biti 0010 */
  pozicija++; /* Povecaj poziciju */
}

Naravoučenije: ne piši primere na brzinu.

ali ovo ce mi, chini mi se, mnogo pomoci.. Hvala.

[forrest_gump]

u zelji da ne smaram ljude vishe ovom temom poslala sam riletu pp i dobila sam kritiku shto to nisam javno pitala. citiram - Mislim da si mogla da postaviš ovo pitanje javno, možda bi još neko imao koristi od toga.

i zato evo mog pitanja:

LM, u pomenutom zadatku koji si ti, chini mi se, pocheo da reshavash u odgovoru na moju temu, u delu koda gde je potrebno da se odredi i prikaze na ekranu pozicija (od bita najmanje tezine) prvog i poslednjeg pojavljivanja binarne kombinacije 101 u zadatom broju n. ima jedan deo koji ne razumem.

ceo kod za taj deo zadatka glasi:
for(i=0;i<4*VEL_BAJTA-VEL_MASKE;i++)
{
if((n & MASKA) == MASKA)
{
if(!poz_prva)
poz_prva = i;
poz_posl=i;
}
n>>=1;
}
itd...

pre toga je definisano:
#define VEL_BAJTA 8
#define VEL_MASKE 3
#define MASKA 5

i deklarisano:
int i, poz_prva=0;poz_posl=0;

ono shto u celoj ovoj prichi ne razumem je ovo:

{
if(!poz_prva)
poz_prva = i;
poz_posl=i;
}

chemu ovo sluzi i kako ovo funkcionishe? nadam se da te nisam previshe smorila i da ti nece biti preveliki problem da mi to objasnish.

Unapred jedno veliko HVALA!

pozz

i evo njegovog odgovora

pre detekcije prvog pojavljivanja, vrednost u promenljivoj poz_prva je jednaka nuli. Evaluacija izraza u zagradi u "if" iskazu se vrši tako što se izračunava logički ekvivalent, odnosno može da bude ili tačno ili netačno. Kako sam napomenuo u forumu, evaluacija višebitnih celobrojnih promenljivih (kao što je int) se svodi na: "ako je nula, onda je netačno, sve ostalo znači tačno".

U prevodu, taj "if" iskaz kaže:

Ako je vrednost u poz_prva 0 (unarni logički operator ! vrši inverziju ili "ne" logičku operaciju, pa bi bukvalni prevod ovog C iskaza bio: "ako je vrednost u poz_prva NE različita od nule...") onda dodeli trenutnu vrednost promenljive "i" promenljivoj "poz_prva".

Zatim nastavlja sa dodeljivanjem vrednosti prom. "i" promenljivoj "poz_poslednja".

Dodela vrednosti "poz_prva" će da se desi samo prilikom detekcije prvog pojavljivanja date kombinacije, dok će se za prvo i svako sledeće pojavljivanje vrednost dodeliti "poz_poslednja"

Ipak, mislim da je kod koji si dala neispravan jer brojač "i" počinje od 0 a ne od 1. Razmisli šta bi bio rezultat ukoliko bi tražena kombinacija bila već na tom prvom mestu? Probaj na primer sa brojem 5.

Druga greška je poređenje sa "MASKA" (upravo ista greška koju sam ja napravio u početnom primeru). Pogledaj moj ispravljeni primer.

eto.. sad sam ovo podelila sa svima.

pozz i hvala Rile.

[forrest_gump]

Nisam htela da otvaram novu temu iako ovaj zadatak nema veze sa naslovom.
Dakle, moze li neko, molim vas, da mi objasni gde je ovde greshka?

#include <stdio.h>
main()
{
    int n;
    char odg;

    while(1)
    {
        printf("\nUnesite redni broj meseca.\n");
        scanf("%d",&n);

        if(n<1 || n>12)
        {
            printf("\nUneli ste pogreshan broj.\n\n");
            break;
        }
        else
            switch(n)
            {
                case 1:
                case 3:
                case 5:
                case 7:
                case 8:
                case 10:
                case 12:
                    printf("\nMesec ima 31 dan.\n");
                    break;
                case 2:
                    {
                        printf("\nDa li je godina prestupna (D/d za DA i N/n za NE)?\n");
                        scanf("%c",&odg);

                        if(odg=='d' || odg=='D')
                            printf("\nMesec ima 29 dana.\n");
                        else if(odg=='n' || odg=='d')
                            printf("\nMesec ima 28 dana.\n");
                    }
                        break;
                case 4:
                case 6:
                case 9:
                case 11:
                        printf("\nMesec ima 30 dana.\n");
                        break;
                default:
                        break;
            }
            printf("\n\n");

    }
}

Elem, sve radi super osim case 2:, a kada taj kod izdvojim u novi program sve radi ok. Poenta je u tome da kada se zada broj 2 (tj mesec februar) na ekranu izadje pitanje da li je godina prestupna i da se u zavisnosti od odgovora ispishe broj dana u mesecu. Ja ne znam kako bih to mogla drugachije da reshim sem na ovaj nachin, a ovako nece da radi.. <_<

Gde greshim?

Hvala unapred!

PS-Najzanimljivije od svega mi je kada mi kompajler ne prijavljuje greshku (kao sad), a program ipak ne radi.

[holodoc]

Izbaci vitičaste zagrade bloka u case bloku za dvojku.

[forrest_gump]

^
probala. nije pomoglo.

[Apprentice]

else if(odg=='n' || odg=='d') - mozda si ovde pogresila.

[rile]

forrest_gump kaže:

PS-Najzanimljivije od svega mi je kada mi kompajler ne prijavljuje greshku (kao sad), a program ipak ne radi.

Da li koristiš neki debager? Ukoliko postaviš prekidnu tačku ("breakpoint") na liniju posle "scanf", možeš da pogledaš šta je zapravo pročitano. Očitana vrednost nije slovo koje očekuješ nego karakter beline od prethodnog unosa.

Pokušaj sa sledećom izmenom:

...
 
case 2:
{
  printf("\nDa li je godina prestupna (D/d za DA i N/n za NE)?\n");
  scanf("%1s", &odg);
...

p.s. kompajler ne može da pomogne oko pogrešne logike u kodu, što se kompajlera tiče tvoj kod je savršeno ispravan i radi tačno ono što si isprogramirala.

[forrest_gump]

@Apprentice
da, to jeste dobro uochena greshka u kodu, ali to nije ometalo rad programa.

@rile
da, ovo jeste reshilo problem, ali te molim za objashnjenje jer kod:

#include <stdio.h>
main()
{
    char odg;

    printf("\nDa li je godina prestupna (D/d za DA i N/n za NE)?\n");
    scanf("%c",&odg);

    if(odg=='d' || odg=='D')
        printf("\nMesec ima 29 dana.\n");
    else if(odg=='n' || odg=='N')
        printf("\nMesec ima 28 dana.\n");
    
    printf("\n\n");

 }

radi i te kako ispravno, pa mi nije jasno zashto u ovom sluchaju %c odgovara, a u switch/case zadatku ne odgovara nego mora %ls?

hvala vam svima, tebi Rile, posebno!

[rile]

Problem je u unosu u kome zadaješ broj meseca, kada uneseš "2" pa zatim "enter" poziv na scanf će očitati samo broj, dok će karakteri kraja linije (pod windows konzolom je to par karakterea '\r' '\n') ostati u ulaznom baferu.

Format "%c" će preuzeti bilo koji karakter, uključujući i karaktere beline (kao što su pomenuti karakteri kraja linije). Tako odgovor "d" ili "n" dolazi tek kao treći karakter (na windowsu).

Detaljnije objašnjenje scanf funkcije možeš da pročitaš ovde: http://www.opengroup.org/onlinepubs/009695399/
ili sa http://msdn.microsoft.com


Za kraj napomena:
Još jednom sam bacio pogled na tvoj program, ukoliko koristiš predloženi "%1s" format, tvoj program, iako će najverovatnije da radi, ima jedan sakriveni ali potencijalno katastrofalan bag; ako pročitaš pažljivo šta kaže standard za format %s, videćeš ovo:

s Matches a sequence of bytes that are not white-space characters. The application shall ensure that the corresponding argument is a pointer to the initial byte of an array of char, signed char, or unsigned char large enough to accept the sequence and a terminating null character code, which shall be added automatically.

Dakle, parametar koji prosleđuješ funkciji scanf u tvom slučaju nije dobar, trebalo bi da bude

char odg[2];

Posle scanf , u odg[0] će biti odgovor (slovo d/n) a u odg[1] će biti znak za kraj stringa u c-u, '\0'.


Nadam se da ovo pojašnjava stvari.

[allokin]

Ako ti treba jedan karakter mozes da koristis neke od nestandarnih funkcija kao sto je _getch().

#include <conio.h> //za _getch
#include <stdio.h> //za printf

int main(int argc, char **argv)
{
    char ch;

    ch=_getch();
    printf("Pritisnula si %c");
    _getch(); //za pauzu

    return 0;
}