Provjera da li je neki broj 2^n

Friday, August 28, 2015


Tema današnjeg blog posta je mini tutorijal ili programerski zadatak školskog tipa, a on glasi kako provjeriti da li je neki broj, broj 2n (broj 2 na n). Još jedno dodatno objašnjenje to su brojevi: 2, 4, 8, 16, 32, 64, 128, 256 ... sve do 2n.

Da bi došli do rješenja ovog zadatka koristi ćemo ovu metodu proračuna:

 1| bool Provjera(int broj) {
 2|
 3|  return (broj != 0) && ((broj & (broj - 1)) == 0);
 4|
 5| }

Par koraka kroz koje prolazi naš kod tj. kako dolazimo do zaključka da li je broj 2n:
  • Koristit cemo binarni operator & tj (Binarno AND )
  • To će za nas pretvoriti brojeve u binarnu formu i
  • Binarno AND će usporediti vrijednosti tj uradit će AND-iranje i vidjet da li je rezultat nula
  • Na kraju ćemo uraditi logičko && sa lijevim dijelom i vratiti odgovarajući rezultat.

Objašnjeno korak po korak:

Recimo da smo funkciji kao parametar poslali broj 16,

 return (16 != 0) && ((16 & (16-1)) == 0);

Sa lijeve strane vidimo da 16 nije jednako nuli te će ta strana vratiti true.. ostali dijelovi izgledaju ovako

 ((16 & (16-1)) == 0);

Što je ustvari jednako:

 ((16 & 15) == 0);

Pitanje je šta tačno znači 16 & 15 , binarni ekvivalent broju 16 je ‭10000‬ dok 15 u binarnom obliku iznosi ‭01111‬. Važno je da napomenemo da & brojeve 16 i 15 "gleda" u binarnoj formi.
Tako da imamo:

 10000‭ = 16
 01111‬ = 15

Zamislimo operator & kao neku matematičku operaciju pri kojoj važi pravilo da ako su oba člana jednaka 1 onda je rezultat 1, a u ostalim slučajevima imamo:

 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0, i zadnje 0 & 1 = 0

Ako se vodimo ovim pravilom imamo ovakav rezultat:

 10000
 01111
 -----
 00000

I očito je da kao rezultat imamo nulu. Ako se vratimo na naš return dio on izgleda ovako:

 return (16 != 0) && ((16 & (16-1)) == 0);

Kada ovo prevedemo po maloprije naučenoj logoci AND-iranja, mi ustvari imamo:

 return true && (0 == 0);

što je ustvari;

 return true && true;

A true i true uvijek će vratiti true... tako da na mjesto poziva funkcije vraćamo bool vrijednost true. Vi ako želite da se uvjerite da li je ovo zaista radi, uzmite neki veći broj pa sami probajate izračunati i uvjerit se u ispravnost ovog koda.


Nadam se da sam vam pomogao sa ovim blog post tutorijalom, te se nadam da ste uspješno pronašli odgovor na ovo često pitanje u školskim zadacima.

Pozdrav! Almir Vuk | AV Development

You Might Also Like

0 comments