/* Program demonstrira upotrebu bitovskih operatora */ #include #include /* funkcija prikazuje binarnu reprezentaciju celog broja u memoriji */ void print_bits(int x) { int size_of_int = sizeof(int) * 8; /* broj bitova celog broja */ unsigned int mask; /* maska koju cemo koristiti za "ocitavanje" bitova */ /* maska u pocetku ima postavljen bit najvece tezine, a svi ostali bitovi su nule. Nakon toga, u svakoj iteraciji se ta jedinica pomera u desno, kako bismo ocitali naredni bit, gledano s leva u desno. Odgovarajuci karakter ('0' ili '1') se ispisuje na ekranu. */ for (mask = 1 << (size_of_int - 1); mask != 0; mask >>= 1) putchar(mask & x ? '1' : '0'); putchar('\n'); } /* funkcija vraca broj jedinica u binarnoj reprezentaciji broja x pomeranjem broja x*/ int count_bits(unsigned int x) { int size_of_int = sizeof(unsigned int) * 8; int br = 0; unsigned int mask = 1 << size_of_int - 1; /* maska se postavlja na vrednost 100000...0000000, i sluzi za ocitavanje bita najvece tezine. U svakoj iteraciji x se pomera u levo za 1 mesto, i ocitavamo sledeci bit. Petlja se zavrsava kada vise nema jedinica tj. kada x postane nula. */ for (; x; x <<= 1) mask & x ? br++ : 1; return br; } /* funkcija vraca broj jedinica u binarnoj reprezentaciji broja x pomeranjem broja maske */ int count_bits1(unsigned int x) { int br = 0; unsigned int mask = 1; /* maska se postavlja na vrednost 00000...00000001, pa se u svakoj iteraciji petlje jedinica pomera levo i sluzi za ocitavanje konkretnog bita. Petlja se zavrsava kada vise nema jedinica u maski tj. kada maska postane nula. */ for (; mask; mask <<= 1) mask & x ? br++ : 1; return br; } /* funkcija vraca celobrojno polje bitova, desno poravnato, koje predstavlja n bitova pocev od pozicije p u binarnoj reprezentaciji broja x, pri cemu se pozicija broji s desna ulevo, gde je pocetna pozicija 0 */ unsigned int get_n_bits(unsigned int x, unsigned int n, unsigned int p) { /* maska kod kod koje su poslednjih n bitova jedinice, a ostalo su nule */ unsigned int last_n_1 = ~(~0 << n); /* pomeramo trazeno polje bitova u x udesno do kraja, a zatim maskiramo ostale bitove, i vracamo vrednost */ return last_n_1 & (x >> p - n + 1); } /* funkcija vraca broj x kome su n bitova pocev od pozicije p postavljeni na vrednosti n bitova najnize tezine binarne reprezentacije broja y */ unsigned int set_n_bits(unsigned int x, unsigned int n, unsigned int p, unsigned int y) { /* 0000....00011..1111 -- n jedinica na kraju */ unsigned int last_n_1 = ~(~0 << n); /* 111..1100..0011..1111 - n nula pocev od pozicije p */ unsigned int middle_n_p_0 = ~(last_n_1 << p - n + 1); /* x sa resetovanih n bita na pozicijama pocev od p */ unsigned int x_reset_middle = x & middle_n_p_0; /* y cijih je n bitova najnize tezine pomereno tako da stoje pocev od pozicije p. Ostali bitovi su nule */ unsigned int y_shift_middle = (y & last_n_1) << p - n + 1; return x_reset_middle | y_shift_middle; } /* postavlja na nulu n bitova pocev od pozicije p. Pozicije se broje pocev od pozicije najmanjeg znacaja, pri cemu se broji od nule */ unsigned int reset_n_bits(unsigned int x, unsigned int n, unsigned int p) { /* formiramo masku oblika 11111...1110000...00001111...11111 pri cemu postoji n nula pocev od pozicije p */ unsigned int mask = ~(~(~0 << n) << p - n + 1); return x & mask; } unsigned int invert_n_bits(unsigned int x, unsigned int n, unsigned int p) { /* formiramo masku oblika 0000...00011111...1111000...0000 pri cemu ima n jedinica pocev od pozicije p */ unsigned int mask = ~(~0 << n) << p - n + 1; /* ekskluzivno ili invertuje sve bitove gde je odgovarajuci bit maske 1. Ostali bitovi ostaju nepromenjeni. */ return x ^ mask; } /* rotacija ulevo za n mesta */ unsigned int rotate_left(unsigned int x, unsigned int n) { unsigned int first_bit; unsigned int size_of_int = sizeof(unsigned int) * 8; unsigned int first_bit_mask = 1 << size_of_int - 1; int i; /* n puta vrsimo rotaciju za po jedan bit u levo */ for (i = 0; i < n; i++) { /* odredjujemo prvi bit */ first_bit = x & first_bit_mask; /* pomeramo sadrzaj u levo, a zatim po potrebi ukljucujemo krajnji desni bit */ x = x << 1 | first_bit >> size_of_int - 1; } return x; } /* funkcija rotira bitove broja x za n mesta u desno */ unsigned int rotate_right(unsigned int x, unsigned int n) { unsigned int last_bit; unsigned int size_of_int = sizeof(unsigned int) * 8; int i; /* n puta ponavljamo rotaciju za jedno mesto udesno */ for (i = 0; i < n; i++) { last_bit = x & 1; /* bit najmanje tezine */ x = x >> 1 | last_bit << size_of_int - 1; } return x; } /* funkcija vraca ceo broj ciji su bitovi rasporedjeni poput odraza u ogledalu u odnosu na x. */ unsigned int mirror(unsigned int x) { unsigned int last_bit; unsigned int size_of_int = sizeof(unsigned int) * 8; int i; unsigned int result = 0; for (i = 0; i < size_of_int; i++) { last_bit = x & 1; /* bit najmanje tezine */ result <<= 1; /* pomeramo ulevo rezultat */ result |= last_bit; /* postavljamo bit najmanje tezine */ x >>= 1; /* pomeramo x udesno */ } return result; } /* funkcija vraca najveci neoznaceni broj sastavljen iz istih bitova kao i x */ unsigned int greatest_number(unsigned int x) { unsigned int size_of_int = sizeof(unsigned int) * 8; /* formiramo masku 100000...0000000 */ unsigned int first_bit_mask = 1 << size_of_int - 1; /* inicijalizujemo rezultat na 0 */ unsigned int result = 0; /* dokle god imamo jedinice u broju x, pomeramo ga ulevo. */ for (; x; x <<= 1) /* za svaku jedinicu, potiskujemo jednu novu jedinicu sa leva u rezultat */ if (first_bit_mask & x) { result >>= 1; result |= first_bit_mask; } return result; } /* funkcija vraca najmanji neoznacen broj sa istim binarnim ciframa kao i x */ unsigned int smallest_number(unsigned int x) { /* inicijalizujemo rezultat na 0 */ unsigned int result = 0; /* dokle god imamo jedinice u broju x, pomeramo ga udesno. */ for (; x; x >>= 1) /* za svaku jedinicu, potiskujemo jednu novu jedinicu sa desna u rezultat */ if (1 & x) { result <<= 1; result |= 1; } return result; } int main() { print_bits(0xABCDEF32U); printf("Broj bitova: %d\n", count_bits(0xABCDEF32U)); print_bits(get_n_bits(0xABCDEF32U, 5, 10)); print_bits(set_n_bits(0xABCDEF32U, 5, 10, 077)); print_bits(reset_n_bits(0xABCDEF32U, 5, 10)); print_bits(invert_n_bits(0xABCDEF32U, 5, 10)); print_bits(rotate_left(0xABCDEF32U, 5)); print_bits(rotate_right(0xABCDEF32U, 5)); print_bits(greatest_number(0xABCDEF32U)); print_bits(smallest_number(0xABCDEF32U)); print_bits(mirror(0xABCDEF32U)); return EXIT_SUCCESS; }