Uporedi vreme izvrsavanja sledeca 2 programa
#include <iostream> using namespace std; const int Nmax=10000000; int a[Nmax]; int main() { int i, brParnih=0; //for (i=0; i<Nmax; i++) a[i]=3*i+1; for (i=0; i<Nmax; i++) a[i]=3*i+2; for (i=0; i<Nmax; i++) if (a[i] %2) brParnih++; //if (a[i] &1) brParnih++; cout <<brParnih << endl; return 0; }
#include <iostream> using namespace std; const int Nmax=10000000; int a[Nmax]; int main() { int i, brParnih=0; for (i=0; i<Nmax; i++) a[i]=3*i+1; for (i=0; i<Nmax; i++) if (a[i] &1) brParnih++; cout <<brParnih << endl; return 0; }
PRIMER
#include <stdio.h> #include <ctype.h> main() {int c; c=getchar(); printf("\nisalpha(%c)=%d", c, isalpha(c)); printf("\nisdigit(%c)=%d", c, isdigit(c)); printf("\nisalnum(%c)=%d", c, isalnum(c)); printf("\nislower(%c)=%d", c, islower(c)); }Uporedite naredna dva programa koja ispisuju broj velikih slova, malih slova i cifara u tekstu koji se učitava sa standardnog ulaza do kraja daototeke (EOF):
BITOVSKI OPERATORI (BITWISE operatori)
& bitovsko AND 1&1=1 0&1=0 0&0=0
Neka bit b ima vrednost 0 ili 1.
Onda b & 0 =0, b&1=b
AKO ZELITE DA NEKE BITOVE POSTAVITE NA NULA, MORATE URADITI OPERACIJU AND SA 0
Primer: 255 & 15= ?
255 -> 1111 1111
15 -> 0000 1111
255&15-> 0000 1111 -> dekadno 15
Primer: Dato je unsigned x; Koliko je x & 01?
B4, B3, ..., B0 su bitovi na pozicijama 4,3,...0
x binarno Bn Bn-1 ....B4 B3 B2 B1 B0
X&01= Bn Bn-1 ....B4 B3 B2 B1 B0
& 0 0 .... 0 0 0 0 1
===================================
0 0 .... 0 0 0 0 B0
ZAKLJUCAK x & 01 vraca kao rezultat nulti bit broja x
| BITOVSKO OR 1 | 1 = 1, 1 | 0 =1, 0 | 0 = 0
Ako bit b ima vrednost 0 ili 1, onda b | 0= b, b | 1 = 1
AKO ZELITE DA POSTAVITE NEKI BIT NA 1, RADITI OPERACIJU OR SA 1com
Primer: 255 | 15 = ?
255 -> 1111 1111
|15 -> 0000 1111
======================
255 <- 1111 1111
Primer: Dato je unsigned x; Sta je rezultat rada x= x | 01
x Bn Bn-1 ... B3 B2 B1 B0
| 0 1 ... 0 0 0 1
==============================
Bn Bn-1 ... B3 B2 B1 1
ODGOVOR>
rezultat je broj X kome je 0-ti bit postavljen na 1
POSTAVITI 5. bit (B4) na 1, a ostale sacuvati
x Bn Bn-1 .... B6 B5 B4 B3 B2 B1 B0
| 0 0 ..... 0 0 1 0 0 0 0 (dekadno gledano, ova maska je broj 16)
======================================
Bn Bn-1 .... B6 B5 1 B3 B2 B1 B0
X | 16 postavlja 5. bit u X na 1, a ostale bitove ne menja
ZAKLJUCAK x | pow(2, n-1) postavlja n-ti bit u x na 1
KAKO POSTAVITI NAJNIZA 3 BITA U X na 1ce?
X | 7
X Bn Bn-1 ... B3 B2 B1 B0
| 0 0 ... 1 1 1 0
=====================================
Bn Bn-1 ... B3 1 1 1
***************************************************************
^ caret BITOVSKO XOR, XOR JE ekskluzivna disjunkcija
tj. ^ JE not EQUIVALENT
1 ^ 0 = 1, 1 ^ 1 =0, 0 ^ 0 = 0
AKO bit b ima vrednost 0 ili 1, onda b ^ 1 = !b , b ^ 0 = b
255 ^ 15 = ?
255 -> 1111 1111
15 -> 0000 1111
^ ==============
1111 0000 256 -1 - 15 = 240
Primer: Dato je unsigned x; Sta je rezultat naredbe x = x ^ 01;
x -> Bn Bn-1 .... B2 B1 B0
01 -> 0 0 .... 0 0 1
^ ===========================
Bn Bn-1 .... B2 B1 !B0
ODGOVOR> Rezultat je broj X kome je 0-ti bit invertovan, a ostali bitovi su nepromenjeni
~ BITOVSKO NOT invertuje bitove
Ako je u 8-bitnom registru smesten dekadni broj 7, onda
~7= INVERTOVANO(0000 0111) = 1111 1000 tj. dekadno 248
CEMU JE JEDNAKO ~1?
CEMU JE JEDNAKO ~0?
AKO JE SIZEOF (int) = 1, tj. ako se int registruje u 1 bajtu,
tj. u 8 bitova, onda se:
1 registruje kao 0000 0001
0 registruje kao 0000 0000
TE JE ~1 = INVERTOVANO(0000 0001) = 1111 1110 tj. 254
~1 = (2 na sizeof(int)*8) -2
TE JE ~0 = INVERTOVANO (0000 0000) = 1111 1111
~0 daje citav registar napunjen bitovima koji su 1
>> SHIFT RIGHT, POMERANJE NADESNO,
EFEKAT DELJENJA STEPENOM DVOJKE
NA PRIMER 32 >> 3 je isto sto i 32 / 23,
ali 32 >> 3 se brze izvrsava
<< SHIFT LEFT, POMERANJE NALEVO
NAPRIMER 3 << 5 je isto sto i 3 * 25,
ali se 3 << 5 brze izvrsava
60. (Demonstracija bitskih operatora) Sta je rezultat rada sledeceg programa?
#include <stdio.h>
main()
{
printf( "255 & 15 = %d\n", 255 & 15 );
printf( "255 | 15 = %d\n", 255 | 15 );
printf( "255 ^ 15 = %d\n", 255 ^ 15 );
printf( "2 << 2 = %d\n", 2 << 2 );
printf( "16 >> 2 = %d\n", 16 >> 2 );
}
Izlaz iz programa je:
255 & 15 = 15
255 | 15 = 255
255 ^ 15 = 240
2 << 2 = 8
16 >> 2 = 4
61. Napisati funkciju print bits koja stampa bitove u zapisu datog neoznacenog celog broja x i program koji ilustruje rad sa tom funkcijom. Uocimo da funkcijom print bits se zapravo stampa binarna predstava broja x.
/*
Funkcija print_bits stampa bitove datog celog broja x.
Vrednost bita na poziciji i je 0 ako i samo ako se dobija 0 pri konjunkciji broja x sa
maskom
000..010....000 (ovu masku cine sve nule, osim 1ce na poziciji i)
Funkcija krece od pozicije najvece tezine kreirajuci masku pomeranjem jedinice u levo
za (broj_bitova(x) - 1) mesto, i zatim pomerajuci ovu masku za jedno mesto u levo u svakoj
sledecoj iteraciji sve dok maska ne postane 0.
*/
#include <stdio.h>
void print_bits(unsigned x){
unsigned wl = sizeof(unsigned)*8; /* wl je broj bitova za registrovanje unsigned promenljive */
unsigned mask; /* maska bitova */
for (mask = 1<<wl-1; mask; mask >>= 1) putchar(x&mask ? '1' : '0');
putchar('\n');
}
main()
{
print_bits(127);
print_bits(128);
print_bits(0x00FF00FF);
print_bits(0xFFFFFFFF);
}
Izlaz iz programa:
00000000000000000000000001111111
00000000000000000000000010000000
00000000111111110000000011111111
11111111111111111111111111111111
ZADACI ZA VEZBU
62. NCP koji proverava da
li se na k-tom bitu broja koji se ucitava sa standardnog ulaza nalazi 1. Pozicija k se ucitava sa
standardnog ulaza. Uzeti u obzir da numeracija bitova je takva da bit najmanje tezine (krajnji desno)
je nulti bit, a ne prvi bit.
#include <stdio.h>
main(){
unsigned n,k;
printf("Unesite broj i poziciju tog broja koju zelite da proverite:\n");
scanf("%u%u",&n,&k);
if ((n&(1 << k))!=0) printf("Bit je 1\n");
else printf("Bit je 0\n");
return 0;
}
63. NCP koji postavlja na k-to mesto 1
#include <stdio.h>
void print_bits(unsigned x);
main(){
unsigned n,k;
printf("Unesite broj i poziciju tog broja koju zelite da proverite:\n");
scanf("%u%u",&n,&k);
printf("Binarno\v uneseni broj je\n");
print_bits(n);
printf("Novi broj je %d\n",(n |(1<<k)));
printf("Binarno, novi broj je\n");
print_bits((n |(1<<k)));
return 0;
}
void print_bits(unsigned x){
unsigned wl = sizeof(unsigned)*8; /* wl je broj bitova za registrovanje unsigned promenljive */
unsigned mask; /* maska bitova */
for (mask = 1<<wl-1; mask; mask >>= 1) putchar(x&mask ? '1' : '0');
putchar('\n');
}
Izrazom a>>b vrsi se pomeranje sadrzaja operanda a predstavljenog u binarnom obliku za b mesta u desno. Popunjavanje upraznjenih mesta na levoj strani zavisi od tipa podataka i vrste racunara. Ako se pomeranje primenjuje nad operandom tipa unsigned popunjavanje je nulama.
Ako se radi o oznacenom operandu popunjavanje je jedinicama kada je u krajnjem levom bitu jedinica, a nulama kada je u krajnjem levom bitu nula.
64. Napisati funkciju koja broji bitove postavljene na 1 u neoznacenom celom broju.
int bitcount(unsigned x)
{
int b;
for(b=0; x!=0; x>>=1)
if (x & 01) b++;
return b;
}
Rešen primer za vežbu: NCP koji izracunava sumu bitova datog neoznacenog broja.
#include <stdio.h>
/* Pomocna funkcija - stampa bitove neoznacenog broja */
void print_bits(unsigned x)
{
int wl = sizeof(unsigned)*8;
unsigned mask;
for (mask = 1<<wl-1; mask; mask >>= 1)
putchar(x&mask ? '1' : '0');
putchar('\n');
}
/* uporedite sa funkcijom iz prethodnog zadatka */
int sum_of_bits(unsigned x)
{
int br;
for (br = 0; x; x>>=1)
if (x&1) br++;
return br;
}
main()
{
printf("Binarni zapis broja 127 je\n"); print_bits(127);
printf("Suma bitova broja 127 je %d\n",sum_of_bits(127));
printf("Binarni zapis broja 128 je\n");print_bits(128);
printf("Suma bitova broja 128 je %d\n",sum_of_bits(128));
printf("Binarni zapis broja 0x00FF00FF je\n"); print_bits(0x00FF00FF);
printf("Suma bitova broja 0x00FF00FF je %d\n",sum_of_bits(0x00FF00FF));
printf("Binarni zapis broja 0xFFFFFFFF je\n");print_bits(0xFFFFFFFF);
printf("Suma bitova broja 0xFFFFFFFF je %d\n",sum_of_bits(0xFFFFFFFF));
}
Rešen primer za vežbu: Napisati funkcije get bits, set bits, invert bits za (redom) izdvajanje, postavljanje i invertovanje pojedinacnih bitova. Potom napisati C program koji ilustruje rad ovih funkcija.
#include <stdio.h>
/* Pomocna funkcija - stampa bitove neoznacenog broja */
void print_bits(unsigned x)
{
int wl = sizeof(unsigned)*8;
unsigned mask;
for (mask = 1<<wl-1; mask; mask >>= 1)
putchar(x&mask ? '1' : '0');
putchar('\n');
}
/* Funkcija vraca n bitova broja x koji pocinju na poziciji p */
unsigned get_bits(unsigned x, int p, int n)
{
/* Gradimo masku koja ima poslednjih n jedinica
0000000...00011111
tako sto sve jedinice ~0 pomerimo u levo za n mesta
1111111...1100000
a zatim komplementiramo
*/
unsigned last_n_1 = ~(~0 << n);
/* x pomerimo u desno za odgovarajuci broj mesta, a zatim
konjunkcijom sa konstruisanom maskom obrisemo pocetne cifre */
return (x >> p+1-n) & last_n_1;
}
/* Funkcija vraca modifikovano x tako sto mu je izmenjeno n bitova
pocevsi od pozicije p i na ta mesta je upisano poslednjih n bitova broja y */
unsigned set_bits(unsigned x, int p, int n, unsigned y)
{
/* Maska 000000...000111111 - poslednjih n jedinica */
unsigned last_n_1 = ~(~0 << n);
/* Maska 1111100..000111111 - n nula pocevsi od pozicije p */
unsigned middle_n_0 = ~(last_n_1 << p+1-n);
/* Brisemo n bitova pocevsi od pozicije p */
x = x & middle_n_0;
/* Izdvajamo poslednjih n bitova broja y i pomeramo ih na poziciju p */
y = (y & last_n_1) << p+1-n;
/* Upisujemo bitove broja y u broj x i vracamo rezultat */
return x | y;
}
/* Invertuje n bitova broja x pocevsi od pozicije p */
unsigned invert_bits(unsigned x, int p, int n)
{
/* Maska 000000111...1100000 - n jedinica pocevsi od pozicije p */
unsigned middle_n_1 = ~(~0 << n) << p+1-n;
/* Invertujemo koristeci ekskluzivnu disjunkciju */
return x ^ middle_n_1;
}
main()
{
unsigned x = 0x0AA0AFA0;
print_bits(x);
print_bits(get_bits(x, 15, 8));
print_bits(set_bits(x, 15, 8, 0xFF));
print_bits(invert_bits(x, 15, 8));
}
Izlaz iz programa:
00001010101000001010111110100000
00000000000000000000000010101111
00001010101000001111111110100000
00001010101000000101000010100000
65. Napisati funkcije
:
Potom napisati C program koji ilustruje rad ovih funkcija.
#include <stdio.h>
/* Pomocna funkcija - stampa bitove neoznacenog broja */
void print_bits(unsigned x)
{
int wl = sizeof(unsigned)*8;
unsigned mask;
for (mask = 1<<wl-1; mask; mask >>= 1)
putchar(x&mask ? '1' : '0');
putchar('\n');
}
/* Funkcija vrsi rotaciju neoznacenog broja x za n pozicija u desno */
unsigned right_rotate(unsigned x, int n)
{
int i;
int wl = sizeof(unsigned)*8;
/* Postupak se ponavlja n puta */
for (i = 0; i < n; i++)
{
/* Poslednji bit broja x */
unsigned last_bit = x & 1;
/* x pomeramo za jedno mesto u desno */
x >>= 1;
/* Zapamceni poslednji bit stavljamo na pocetak broja x*/
x |= last_bit<<wl-1;
}
return x;
}
/* Funkcija obrce binarni zapis neoznacenog broja x tako sto bitove cita unatrag */
unsigned mirror(unsigned x)
{
int i;
int wl = sizeof(unsigned)*8;
/* Rezultat inicijalizujemo na poslednji bit broja x */
unsigned y = x & 1;
/* Postupak se ponavlja wl-1 puta */
for (i = 1; i<wl; i++)
{
/* x se pomera u desno za jedno mesto */
x >>= 1;
/* rezultat se pomera u levo za jedno mesto */
y <<= 1;
/* Poslednji bit broja x upisujemo na poslednje mesto rezultata */
y |= x & 1;
}
return y;
}
main()
{
unsigned x = 0xFAF0FAF0;
print_bits(x);
print_bits(mirror(x));
print_bits(right_rotate(x, 2));
}
Izlaz iz programa:
11111010111100001111101011110000
00001111010111110000111101011111
00111110101111000011111010111100
Zadaci za vezbu:
Zadatak 7. Napisati operator dodeljivanja koji ce broju x tipa unsigned sacuvati n krajnjih desnih bitova, a ostale postaviti na nulu.
x=x&~(~0 << n); ili x&=~(~0 << n);
Zadatak 8. Napisati operator dodeljivanja koji ce u x ocistiti n bitova (postaviti nule) pocev od pozicije p.
x&=~(~(~0<<n)<<(p-1))
Zadatak 9. Napisati operator dodeljivanja kojim se invertuje x (prevodi jedan u nulu i nula u jedan) pocev od pozicije p na duzini n.
x^=(~(~0<<n)<<(p-1));