Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

[Zadatak] Operacije nad bitima i maske

[es] :: C/C++ programiranje :: C/C++ za početnike :: [Zadatak] Operacije nad bitima i maske

[ Pregleda: 2003 | Odgovora: 10 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Nemanja Avramović
Engineering Manager
MENU Technologies
Beograd, Srbija

Član broj: 32202
Poruke: 4392
91.150.113.*

Sajt: https://avramovic.info


+46 Profil

icon [Zadatak] Operacije nad bitima i maske29.10.2007. u 18:51 - pre 214 meseci
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:

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

Laravel Srbija.

[NE PRUŽAM PODRŠKU ZA PHP PREKO PRIVATNIH PORUKA!]
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4941
*.dynamic.sbb.co.yu.



+646 Profil

icon Re: [Zadatak] Operacije nad bitima i maske29.10.2007. u 21:05 - pre 214 meseci
Odmah da napomenem da nisam stručan za operacije sa bitovima (ima tu puno caka koje treba formalno naučiti da bi se odradila dobra optimizacija), ali evo jedno rešenje, onako kako sam ja razumeo. Ja sam razumeo da od pozicije P (0-31) ulevo ide određeni broj bitova N, pa da taj pattern predstavlja masku. Ti svakako testiraj, jer ovo je totalno ad hoc.

Code:

#include <stdio.h>
#include <stdlib.h>

/*
   x = 8
   p = 3
   n = 3
   y = ?
   x = 00000000000000000000000000001000
   M = 00000000000000000000000000111000 (od pozicije 3 (cetvrte s desna), 3 jedinice)
   y = 00000000000000000000000000110000
   y = 48

   x = 8
   p = 1
   n = 1
   y = ?
   x = 00000000000000000000000000001000
   M = 00000000000000000000000000000010 (od pozicije 1 (druge s desna), 1 jedinice)
   y = 00000000000000000000000000001010
   y = 10

*/

int main()
{
   unsigned int x, p, n, m, y; /* x je ulaz, p pozicija, n duzina bitnog polja,  m je maska, y izlaz */

   while ( 1 )
   {
      printf( "Unesite ceo broj X: " );
      scanf( "%d", &x );
   
      if ( !x )
      {
         printf ( "Kraj rada!\n" );
         break;
      }
      
      int unsigned_int_size_in_bits_zero_index = sizeof(unsigned int)*8-1;
      do
      {
         printf( "Uneti poziciju P (od 0 do %d): ", unsigned_int_size_in_bits_zero_index );
         scanf( "%d", &p );
      } while ( p < 0 || p > unsigned_int_size_in_bits_zero_index );

      do
      {
         printf( "Uneti sirinu N (od 0 do %d): ", unsigned_int_size_in_bits_zero_index - p);
         scanf( "%d", &n );
      } while ( n < 0 || n > ( unsigned_int_size_in_bits_zero_index - p ) );

      m = ( 1 << n ) - 1;
      m <<= p;
      y = x ^ m;
   
      printf( "Rezultat: %d\n", y );
   }
  
   system("PAUSE");    
   return 0;
}


 
Odgovor na temu

Nemanja Avramović
Engineering Manager
MENU Technologies
Beograd, Srbija

Član broj: 32202
Poruke: 4392
77.46.209.*

Sajt: https://avramovic.info


+46 Profil

icon Re: [Zadatak] Operacije nad bitima i maske29.10.2007. u 22:40 - pre 214 meseci
Hvala, mada si mnogo ti to zakomplikovao (mnogo provera radiš, nismo mi još na tom nivou ). Analiziraću kod sutra, imam fore do ponedeljka sledećeg da uradim zadatak, i da razumem kako sve to radi.

Hvala još jednom
Laravel Srbija.

[NE PRUŽAM PODRŠKU ZA PHP PREKO PRIVATNIH PORUKA!]
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4941
*.tekostolac.co.yu.



+646 Profil

icon Re: [Zadatak] Operacije nad bitima i maske30.10.2007. u 06:35 - pre 214 meseci
Citat:

Hvala, mada si mnogo ti to zakomplikovao (mnogo provera radiš, nismo mi još na tom nivou ).

Ah, pa to je zbog ovoga:
"Zadate vrednosti p i n moraju biti razumne pozitivne vrednosti. [...]. Potrebno je da program obrađuje više skupova ulaznih podataka.".

A sam kod je svega tri izraza (reda), mada garantovano može da bude i kraće kad se optimizuje.


[Ovu poruku je menjao X Files dana 30.10.2007. u 08:55 GMT+1]
 
Odgovor na temu

Nemanja Avramović
Engineering Manager
MENU Technologies
Beograd, Srbija

Član broj: 32202
Poruke: 4392
77.46.222.*

Sajt: https://avramovic.info


+46 Profil

icon Re: [Zadatak] Operacije nad bitima i maske30.10.2007. u 17:15 - pre 214 meseci
Razumem, razumem. Nego, jel može neko pojašnjenje oko pravljenja maski (sve ostalo mi je valjda jasno) i to konkretno kod (vako smo radili u školi):
maska = ~(~0 << n) << p;
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?
Šta npr. raditi kad između jedinica treba da imam x nula u maski? :P npr. 000110100
Kako to radi? 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)?
Laravel Srbija.

[NE PRUŽAM PODRŠKU ZA PHP PREKO PRIVATNIH PORUKA!]
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4941
*.dynamic.sbb.co.yu.



+646 Profil

icon Re: [Zadatak] Operacije nad bitima i maske30.10.2007. u 17:48 - pre 214 meseci
Koristi Win kalkulator (dec/bin, Not, i sl.), imaš puno korisnih opcija za proveru medjurezultata:


m = ~(~0 << n) << p;

~(~0 << 3) << 3
~(11111111111111111111111111111111 << 3) << 3
~(11111111111111111111111111111000) << 3
00000000000000000000000000000111 << 3
00000000000000000000000000111000

Drugim recima, prve dve linije (izraza) mog primera zamenjujes ovom jednom.
 
Odgovor na temu

Nemanja Avramović
Engineering Manager
MENU Technologies
Beograd, Srbija

Član broj: 32202
Poruke: 4392
77.46.222.*

Sajt: https://avramovic.info


+46 Profil

icon Re: [Zadatak] Operacije nad bitima i maske30.10.2007. u 18:17 - pre 214 meseci
E to. Hvala ti puno, sad mi je jasno
Laravel Srbija.

[NE PRUŽAM PODRŠKU ZA PHP PREKO PRIVATNIH PORUKA!]
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4941
*.dynamic.sbb.co.yu.



+646 Profil

icon Re: [Zadatak] Operacije nad bitima i maske30.10.2007. u 18:20 - pre 214 meseci
A da, a kako da se napravi maska od nula medju jedinicama ;)

Možda ovako:
m = ~(~(~0 << n) << p);
... samo jedna tilda ~(prethodni izraz) oko izraza ;) Mada sigurno se i to može optimizovati.
 
Odgovor na temu

Nemanja Avramović
Engineering Manager
MENU Technologies
Beograd, Srbija

Član broj: 32202
Poruke: 4392
77.46.222.*

Sajt: https://avramovic.info


+46 Profil

icon Re: [Zadatak] Operacije nad bitima i maske30.10.2007. u 18:39 - pre 214 meseci
Nisam mislio od nula među jedinicama nego sa jednom nulom između jedinica koje su među nulama recimo ovako: 000000110100

Ovako nešto?

~(~(~(~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?
Laravel Srbija.

[NE PRUŽAM PODRŠKU ZA PHP PREKO PRIVATNIH PORUKA!]
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4941
*.dynamic.sbb.co.yu.



+646 Profil

icon Re: [Zadatak] Operacije nad bitima i maske30.10.2007. u 18:45 - pre 214 meseci
Deluje da je tako :)

Svakako prouči:
http://graphics.stanford.edu/~seander/bithacks.html

Tu je dato dosta caka kako nešto uraditi kraće (brže). Mislim da se sa gornjeg linka ovo može upotrebiti: http://graphics.stanford.edu/~seander/bithacks.html#MaskedMerge
... uz razliku: & i |

P.S.
Off Topic:
Šta bi, neće SUP /SUP :) ?
 
Odgovor na temu

Nemanja Avramović
Engineering Manager
MENU Technologies
Beograd, Srbija

Član broj: 32202
Poruke: 4392
77.46.222.*

Sajt: https://avramovic.info


+46 Profil

icon Re: [Zadatak] Operacije nad bitima i maske30.10.2007. u 18:50 - pre 214 meseci
Aj pogledaću te linkove, mada mrzim da čitam na engleskom

P.S. Ma neće...
Laravel Srbija.

[NE PRUŽAM PODRŠKU ZA PHP PREKO PRIVATNIH PORUKA!]
 
Odgovor na temu

[es] :: C/C++ programiranje :: C/C++ za početnike :: [Zadatak] Operacije nad bitima i maske

[ Pregleda: 2003 | Odgovora: 10 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.