Pomoc oko zadatka iz C-a

Započeo marina, 14.04.2008, 22:26

prethodna tema - sledeća tema

marina

14.04.2008, 22:26 Poslednja Izmena: 14.04.2008, 22:39 od marina
Pozdrav svima!

Treba mi mala pomoc oko sledeceg zadatka jer ne kapiram u cemu je fora. Moze li neko da mi kaze o cemu se radi kod ovih brojeva u obliku ox80 i kakve veze ima operacija logickog bitnog poredjenja sa konverzijom? Znam kako se radi konverzija, ali sta se u ovom zadatku konkretno desava? Ako neko moze da mi iskomentarise zadatak. Hvala :)!

Zadatak. Predstavljanje brojeva u binarnom brojnom sistemu.    

#include<stdio.h>
int main(int argc, char *argv[])
{
int broj,i;
printf("Unesi decimalni broj: ");
scanf("%d",&broj);
for (i=1;i<=8;i++)
{
if ((broj & 0x80) != 0) {
broj <<= 1;
printf("1");
}
else {
broj <<= 1;
printf("0");
}
if (i%4 == 0)
printf(" ");
}
printf("\n");
return 0;
}



Marko Аcović

U zadatku ti se vrsi konverzija celobrojne promenljive u binarni ekvivalent. Imas celobrojnu promenljivu koju logicki mnozis sa "maskom" 0x80 (1000 0000). Kao rezultat dobijas ili 0 ili 1. Kreces od pozicije najvece tezine i vrsis pomeranje (shiftovanje) u levo. Pomeranje vrsis onoliko puta koliko ti je dugacka maska (8 puta u ovom slucaju). Fakticki pomeras 1 kroz sve pozcije, vrsis mnozenje i proveravas rezultat. Na svake 4 pozicije pravis razmak. Ako ti nije bas najjasnije, savetujem da kod provuces kroz neki debugger (preporucujem MS Visual Studio) i pratis kako se menjaju promenljive korak-po-korak. Nadam se da je pomoglo  8)

holodoc

14.04.2008, 23:54 #2 Poslednja Izmena: 15.04.2008, 00:00 od holodoc
Zadatak u suštini nije nešto preterano težak iako dobro dočarava kako se koriste logičke operacije nad bitovima da se izvrši odgovarajuća operacija.

Idemo red po red :)

Prvi red

#include<stdio.h>

služi za dodavanje neophodnih standardnih zaglavlja C-a iz kojih se koriste odgovarajuće funkcije. U konkretnom primeru potrebne su nam funkcije scanf i printf koje se nalaze u navedenom zaglavlju.

Sledeći red je tzv. entry-point aplikacije tj. tačka koju kompajler prvo traži kada počinje sa kompajliranjem. U navedenom primeru su pridodati i argumenti main funkcije argc i argv u koje se prenose vrednosti koje bi se dodatno unosile u komandnoj liniji pri pokretanju programa. Primera radi ako se nakon kompajliranja ovog programa dobije program pod nazivom dectobin.exe i ukuca dectobin.exe 5 argc će dobiti brojnu vrednost 1 a argv pokazivač na pokazivač koji sadrži string 5.

int main(int argc, char *argv[])

Sledeći redovi definišu promenjljivu za brojač i unošenje celobrojnog broja koji se smešta u promenjljivu broj.

int broj,i;
printf("Unesi decimalni broj: ");
scanf("%d",&broj);


Sada ide zanimljiv deo. Ulazimo u petlju koja će se izvršiti tačno osam puta. Zašto osam puta? Pa zato što je pisac zadatka hteo da vrši konverziju samo decimalnih brojeva do 128 [1000 00002] odnosno ovo ograničenje konkretno vrši proveru samo  do broja 128. Ako bi smo hteli da vršimo konverziju do nekog drugog opsega potrebno je da uslov i<8 promenimo u i<broj_pozicija gde je broj_pozicije u stvari maksimalan broj mesta u binarnom broju koji se posmatra. Ako recimo stavimo 16 onda možemo da radimo konverziju do broja 65536 [1000 0000 0000 00002].

Dakle cela petlja se ponavlja u konkretnom slučaju 8 puta.
A petlja počinje tako što se proverava da li je uneti broj u binarnom obliku jednak broju 0x80 (ovo je heksadecimalna prerezentacija broja 128 u jezicima nalik C-u). Dakle programerski oblik heksadecimalnog broja se dobija dodavanjem 0x prefiksa isped broja. Znači 0x80 je u stvari 12810 ili 1000 00002.

Za potrebe objašnjenja pretpostavićemo da je unet broj 5 (01012).

Kada uđemo u petlju prvi put proverava se da li je logička operacija bitnog I poređenja unetog broja i broja 128 binarno različita od nule. Kako se radi bitno poređenje? Na početku imamo sledeće stanje:

0000 0101 <- broj
1000 0000 <- 1282
----------

000000000 <- broj & 0x80


Razlog zašto je ovo rađeno leži u činjenici da smo hteli da vidimo da li je MSB (Most Significant Bit iliti bit najveće težine) binarne reprezentacije unetog broja jednak jedinici. Ako jeste onda se na izlazu ispisuje jedinica a ako nije onda se ispisuje nula.

Bez obzira koji uslov bio ispunjen u if petlji izvršava se sledeći red:

broj <<= 1;

U pitanju je operacija "left-shift"-ovanja ili pomeranja svih bitova u okviru binarnog broja levo za navedeni broj pozicija a nedostajući brojevi sa desne strane se popunjavaju nulama. Posle shift-ovanja broj izgleda ovako:

0000 1010

Sledećih par redova služe isključivo da se prilikom ispisa rezultata (u toku bilo kog prolaza kroz for petlju) proverava da li je trenutna vrednost promenjljive koja broji prolaze i jednaka četvorki pa da usput izvrši i jedno dopisivanje praznog mesta da bi se odvojile tetrade.

if (i%4 == 0)
       printf(" ");


U sledećem ciklusu vrši se upoređivanje novodobijenog "levo pomerenog" broja sa brojem 128 ponovo i to na nivou bitova i ispisuje rezultat upoređivanja.

0000 1010 <- broj
1000 0000 <- 1282
----------

000000000 <- broj & 0x80


Dakle bitovi unetog broja se "pomeraju levo" i u stvari proverava se da li je rezultat upoređivanja poslednjeg bita broja 1282 sa pomerenim brojem u toku trenutnog for ciklusa veći od jedan. Nema veze što je taj broj (logički rezultat) uvek 128, pošto se tada dobija rezultat 1000 0000 jer je bitno da je rezultat operacije samo veći od nule.

Šta se dešava kada naiđe prvi "kec" u šestom ciklusu?

Imamo sledeće stanje:

1010 0000 <- broj
1000 0000 <- 1282
----------

100000000 <- broj & 0x80

Kao što se vidi iz priloženog kada se naleti na jedinicu rezultat upoređivanja unetog broja i 0x80 će biti različit od nule (istina biće 128 uvek kada se štampa jedinica na izlazu)  i biće odštampana jedinica kao rezultat zbog toga što je rezultat logičkog I bitnog upoređivanja u datom ciklusu dalo kao rezultat broj različit od nule. I tako sve dok se ne prođe kompletna petlja od 8 ciklusa.U suštini u toku izvršavanja programa dobijamo sledeći ispis na ekranu tokom izvršavanja pojedinačnih ciklusa u for petlji. Tačnije, svaki red predstavlja šta se vidi na ekranu nakon izvršenja svakog ciklusa pojedinačno.

0
00
000
0000
0000 0
0000 01
0000 010
0000 0101

I to bi bilo to  ;)
<?php
abstract class Ignorance extends Stupidity implements Unavoidable 
    private function 
__construct(){
        
parent::__destruct();
    }; 

// EOF -> life.php

marina

15.04.2008, 01:21 #3 Poslednja Izmena: 22.04.2008, 09:20 od holodoc
Hvala marko_gm i holodoc  :)!
Pomogli ste zaista, posebno hvala holodoc na detaljnom objasnjenju svakog redka  :)!

Pozz :)

holodoc

15.04.2008, 08:03 #4 Poslednja Izmena: 22.04.2008, 09:21 od holodoc
Citat: marina  15.04.2008, 01:21
Hvala marko_gm i holodec  :)!
Pomogli ste zaista, posebno hvala holodoc na detaljnom objasnjenju svakog redka  :)!

Pozz :)
Nema problema koleginice. Drago nam je da smo pomogli :)
<?php
abstract class Ignorance extends Stupidity implements Unavoidable 
    private function 
__construct(){
        
parent::__destruct();
    }; 

// EOF -> life.php

Zepi

Spremajući vezbe iz programskih jezika dođoh i do tematike rada sa bitovima i ovog već diskutovanog zadatka.

Iako smo temu zatvorili tj. svi su bili zadovoljni objašnjenjem ipak evo da se malo vratimo ovde jer ima grešaka.

Kao prvo treba napomenuti da zadatak uspešno ispisuje binarne vrednosti brojeva do 255 tj. 1111 1111, ustvari sama postavka zadatka bi trebala da glasi do 256 umesto 128.

Zašto?

Granica brojeva koji se mogu konvertovati ovim programom određena je samo maskom tj. njenom veličinom. Povećanje broja i neče doprineti ničemu.

primer:
broj 255 binarno je 1111 1111 i ovo radi bez problema sa maskom 1000 0000 koja je i korišćena u zadatku.

Problem nastaje u tome što se ne porede bitovi najveće težine kada su brojevi različitog opsega.
primer:
broj 256 binarno je 1 0000 0000 pri poređenju sa maskom 1000 0000 koja je korišnjena u zadatku daje rezultat 0000 0000.

Važno je primetiti da da pri prvom poređenju tj. (&) nije bila operacija između bitova najveće težine obeleženih crveno već između narandžaste 0 i crvene 1:

   1 0000 0000 (256)
&    1000 0000 (128)

Povećanjem broja iteracija promenljive i se ništa ne dobija (ustvari dobija se veći broj nula na kraju što je veoma pogrešno).

Znači još jednom samo da se napomene da se povećanje opsega postiže povećanjem maske.

Konkretno za ovaj primer maska bi bila broj 256 (decimalno) tj. 1 0000 0000 (binarno) sa čime se opseg brojeva koji se mogu uspešno konvertovati povećava na sve brojeve do 511.
Još da bi mogli i da vidimo sve bitove potrebno je maksimum iteracije promenljive i povećati na 9.

Pozdrav.

holodoc

Siguran sam da se koleginica Marina potajno zahvaljuje i klima glavu u znak odobravanja izrečenog u prethodnom postu što ja ne mogu da tvrdim za sebe... Mislim za onaj deo oko razumevanja :dzavo:

Kako ide uopšte postavka tog zadatka? :) Pošto smo mi diskutovali o datom rešenju a ne o problemu.
<?php
abstract class Ignorance extends Stupidity implements Unavoidable 
    private function 
__construct(){
        
parent::__destruct();
    }; 

// EOF -> life.php

maxogm

30.11.2009, 19:00 #7 Poslednja Izmena: 30.11.2009, 19:03 od maxo
Pravi tekst zadatka je:


Napisati program na programskom jeziku C koji učitava jedan znakovni niz (string) S1 i jedan ceo broj M, a zatim formira
novi znakovni niz S2 samo od onih znakova na čijim su pozicijama odgovarajući bitovi broja M jednaki 1. Smatrati da se
ceo broj predstavlja u 8-bitnoj lokaciji, a da znakovni niz može imati najviše 8 znakova. Na kraju, program ispisuje novi
znakovni niz S2.


E sad veoma moguce je da je postojala i neka druga interpretacija ovog zadatka u kome je neko zaboravio da napise:


Smatrati da se ceo broj predstavlja u 8-bitnoj lokaciji, a da znakovni niz može imati najviše 8 znakova.


E sad ovo resenje sto je Marina napisala je korisceno kao jedno od objasnjenje za deo ovog zadatka.

holodoc

Pa sad ni zadatak nije baš najprecizniji.

Ko što herr Maksimović reče treba precizirati bitnu dužinu karaktera (7-bitni standardni ASCII, 8-bitni prošireni ASCII, dvobajtni pa nadalje Unicode, možda čak i simplified Chinese? :D)
<?php
abstract class Ignorance extends Stupidity implements Unavoidable 
    private function 
__construct(){
        
parent::__destruct();
    }; 

// EOF -> life.php