Zanima me sta radi deo koda “k+= k & -k” u resenju zadatka “broj sortiranih trojki” i zasto se koristi.
Deo koda se nalazi ispod naslova “Fenvikovo Drvo” u resenjima u prvoj funkciji.
https://petlja.org/biblioteka/r/Zbirka2/broj_sortiranih_trojki
& je bitska I (AND) operacija. Ona radi tako što za svaki bit oba operanda, proveri da li su oba jednaka 1 i u rezultatu taj bit postavi na 1, a u suprotnom u rezultatu taj bit postavi na 0. Na primer:
| Dec | Bin |
|---|---|
| 6 | 0110 |
| 10 | 1010 |
| 6 & 10 | 0010 |
k & -k izdvaja najniži bit postavljen na 1. Na primer, za broj 10 (1010), rezultat će biti 2 (0010), za broj 9 (1001) rezultat će biti 1 (0001) dok će za broj 8 (1000) rezultat biti 8. Zbog toga zašto ovo radi to što radi, morao bi da razumeš kako se brojevi predstavljaju u komplementu dvojke. Komplement dvojke, ukratko, je način predstavljanja celih brojeva u računaru koji nam dozvoljava da najviši bit tog broja koristimo kao indikator da li je broj pozitivan ili negativan. Ovo postižemo tako što, ako broj predstavljamo na N bita, prvih 2^{N-1}-1 brojeva su pozitivni, a zatim dolazi 2^{N-1} negativnih brojeva obrnutim redosledom, tako da naš brojevni sistem za N = 4 izgleda otprilike ovako:
| Binarna predstava | Neoznačen broj | Označen broj |
|---|---|---|
0000 |
0 | 0 |
0001 |
1 | 1 |
0010 |
2 | 2 |
0011 |
3 | 3 |
| … | … | … |
0111 |
7 | 7 |
1000 |
8 | -8 |
1001 |
9 | -7 |
1010 |
10 | -6 |
| … | … | … |
1110 |
14 | -2 |
1111 |
15 | -1 |
0000 |
0 | 0 |
gde “neoznačen broj” predstavlja prirodan broj koji najviši bit tretira kao i svaki drugi a “označen” predstavlja ceo broj koji najviši bit tretira kao bit znaka. Ovo za posledicu ima da broj konvertujemo iz pozitivnog u negativni i obrnuto tako što mu izvrnemo (“komplementiramo”) sve bitove (0 postaje 1, 1 postaje 0) i na njega dodamo 1. Baš zbog ovog dodavanja 1 je najniži bit broja jedini bit koji nakon pretvaranja broja u negativan ostaje 1, dok svi ostali postaju 0, pa se operacijom & sa nenegiranim brojem dobija taj bit. Na primer:
| Dec | Bin (B) |
Komplementiran (K) |
Negiran (K+1) |
Rezultat (B & (K+1)) |
|---|---|---|---|---|
| 7 | 0111 | 1000 | 1001 | 0001 |
| 4 | 0100 | 1011 | 1100 | 0100 |
Ovo nam služi kako bismo došli do sledećeg elementa Fenvikovog stabla u kojem treba ažurirati prefiksnu sumu. Fenvikovo stablo je struktura koja predstavlja niz nad kojim se lako može izračunati prefiksna suma tako što se u strukturi i ne čuvaju sami elementi niza već njihove sume, na specifičan način. Na primeru sa Vikipedije, ako bismo u Fenvikovom stablu računali prefiksnu sumu od 11 (1011), sabrali bismo elemente 11 (1011), 10 (1010) i 8 (1000) (pretpostavlja se da je niz indeksiran od 1 pa je element na poziciji 0 uvek jednak nuli, štaviše, implementacija iz rešenja tog zadatka ne bi radila ukoliko bismo pokušali da povećamo element na poziciji 0, barem koliko ja vidim). Iz ovoga se vidi zašto se u funkciji za prefiksnu sumu koristi k -= k & -k (kako bi se izbacio najniži bit broja i došlo do sledećeg broja za sabiranje). Zbog ovog specifičnog načina računanja prefiksne sume, pri izmeni vrednosti nekog elementa se moraju ažurirati svi elementi krećući od k-tog pa na njega dodavajući njegov najniži bit.
Ne znam koliko je ovoga što sam sad objasnio bilo jasno.
Hvala, jasnije je!