Šta rade bitovske operacije
Bitovska operacija posmatra broj kao niz bitova i radi nad svakom pozicijom nezavisno. To su najbrže operacije koje CPU ima i pojavljuju se svuda: zastavice dozvola, mrežne maske, heš funkcije, grafika, kompresija i parsiranje protokola.
| Operacija | Simbol (C, JS, Go, Python) | Pravilo po bitu | Tipična upotreba |
|---|---|---|---|
| AND | & | 1 samo ako su oba bita 1 | Maskiranje bitova, provera zastavice: x & FLAG |
| OR | | | 1 ako je bar jedan bit 1 | Postavljanje zastavice: x | FLAG |
| XOR | ^ | 1 ako se bitovi razlikuju | Preokretanje zastavice, zamena, kontrolne sume |
| NOT | ~ | Obrće svaki bit | Pravljenje inverzne maske: x & ~FLAG briše zastavicu |
| Pomeranje ulevo | << | Pomera bitove ulevo, popunjava nulama | Množenje sa 2ⁿ, pravljenje maske: 1 << n |
| Pomeranje udesno | >> | Pomera bitove udesno | Deljenje sa 2ⁿ, izdvajanje polja |
| Rotacija | rotl / rotr | Pomeranje, ali bitovi koji ispadnu ulaze sa druge strane | Hešovi i šifre |
Aritmetičko i logičko pomeranje udesno
Pomeranje udesno postoji u dve varijante. Logičko pomeranje popunjava nove gornje bitove nulama. Aritmetičko pomeranje kopira bit znaka, pa negativan broj u dvojičnom komplementu ostaje negativan. U C-u i Go-u, >> nad označenim tipom je aritmetičko, a nad neoznačenim logičko. JavaScript ima oba: >> je aritmetičko, a >>> logičko. Postavite širinu na 8 i probajte -8 >> 1 ovde da vidite razliku.
Zašto je širina bitna
U pravom registru bitovi koji se pomere preko vrha se gube, a NOT obrće tačno onoliko bitova koliko registar ima. ~0 je 255 u 8 bitova, 65535 u 16 bitova i 4294967295 u 32. Ovaj kalkulator uvek radi u širini koju izaberete, pa se rezultati poklapaju sa onim što će vaš kod videti u uint8_t, uint32 i slično.
Uobičajeni idiomi
Pitanja
Koja je razlika između logičkih i bitovskih operatora?
Logički operatori (&&, ||, !) posmatraju cele vrednosti kao tačne ili netačne i daju jedan rezultat tačno/netačno. Bitovski operatori (&, |, ^, ~) rade nad svakim bitom operanada i daju broj. 6 && 3 je tačno, ali 6 & 3 je 2.
Zašto NOT daje negativan broj u mom kodu?
Ako je promenljiva označena, najviši bit je bit znaka. ~5 u 32-bitnom dvojičnom komplementu je 0xFFFFFFFA, što označeni int prikazuje kao −6. Sačuvajte rezultat u neoznačeni tip ili ga maskirajte (~5 & 0xFF = 250) da vidite sirovi obrazac bitova.
Šta se dešava sa bitovima pomerenim preko kraja?
U registru fiksne širine oni se odbacuju. Pomeranje ulevo zato može da izgubi gornje bitove (prekoračenje); pomeranje udesno gubi donje bitove (zato x >> 1 zaokružuje nadole). Rotacije su drugačije: bitovi ulaze ponovo sa druge strane.
Da li XOR broja sa samim sobom uvek daje nulu?
Da. Svaki bit se poredi sa identičnim bitom, a XOR jednakih bitova je 0. Zato je x ^ x = 0 i zato XOR može da se iskoristi za pronalaženje jedinog nesparenog elementa u listi u kojoj se sve ostalo pojavljuje dvaput.
Mogu li ovo da koristim za 64-bitne vrednosti?
Da. Alat koristi cele brojeve proizvoljne preciznosti i maskira na širinu koju izaberete, pa su 64-bitne operacije tačne, za razliku od ugrađenih JavaScript operatora koji staju na 32 bita.