Pitanja
Gde mogu da isprobam ove trikove?
Bitovski kalkulator prikazuje svaki bit rezultata za AND, OR, XOR, pomeranja i rotacije na 8–64 bita, a bitmask kalkulator gradi maske iz pozicija.
Podsetnik bitovskih trikova
Svaki idiom ovde radi u C-u, Go-u, Rust-u, Javi i JavaScriptu (32-bitno) sa istim operatorima; i u Python-u, sa neograničenim celim brojevima.
Staje na jednu uspravnu A4 / Letter stranicu; u prozoru za štampu izaberite „Sačuvaj kao PDF“ da biste zadržali kopiju.
Operatori
| a & b | AND: 1 gde su oba 1 |
| a | b | OR: 1 gde je bar jedan 1 |
| a ^ b | XOR: 1 gde se razlikuju |
| ~a | NOT: okreće sve bitove (= −a − 1 u dvojičnom komplementu) |
| a << n | pomeranje ulevo: × 2ⁿ |
| a >> n | pomeranje udesno: ÷ 2ⁿ, zaokružuje ka −∞ za označene (aritmetičko) |
| a >>> n | logičko pomeranje udesno (JS, Java); neoznačeni tipovi drugde |
Pojedinačni bitovi (bit n, 0 = najniži)
| x & (1 << n) | test: različito od nule ako je postavljen |
| (x >> n) & 1 | uzmi bit kao 0 ili 1 |
| x | (1 << n) | postavi |
| x & ~(1 << n) | obriši |
| x ^ (1 << n) | okreni |
| (x & ~(1 << n)) | (b << n) | postavi bit n na b |
Maske i polja
| (1 << n) - 1 | maska donjih n bitova |
| ((1 << w) - 1) << lo | maska od w bitova počev od lo |
| (x >> lo) & ((1 << w) - 1) | izdvoji w-bitno polje na lo |
| (x & ~m) | ((v << lo) & m) | umetni v u polje sa maskom m |
| (x & FLAGS) == FLAGS | sve zastavice postavljene |
| x & FLAGS | bar jedna zastavica postavljena |
Najniži / najviši bit
| x & -x | izoluj najniži postavljeni bit |
| x & (x - 1) | obriši najniži postavljeni bit |
| x | (x + 1) | postavi najniži nepostavljeni bit |
| x & (x + 1) | obriši završne jedinice |
| x | (x - 1) | postavi završne nule |
| ctz(x) = log₂(x & -x) | indeks najnižeg postavljenog bita (__builtin_ctz, bits.TrailingZeros) |
| 31 - clz(x) | indeks najvišeg postavljenog bita = ⌊log₂ x⌋ |
Testovi
| x && !(x & (x - 1)) | da li je stepen dvojke |
| (x & 1) == 0 | da li je paran |
| (x ^ y) < 0 | suprotni znaci (označeno) |
| (x & (a - 1)) == 0 | poravnat na a (a = 2ⁿ) |
| x == (x & 0xFF) | staje u bajt |
Aritmetika
| (x + a - 1) & -a | zaokruži naviše na umnožak a (a = 2ⁿ) |
| x & -a | zaokruži naniže na umnožak a |
| x & (a - 1) | x mod a (a = 2ⁿ, x ≥ 0) |
| (x + y) >> 1 | prosek (može da prekorači); (x & y) + ((x ^ y) >> 1) ne može |
| x ^= y; y ^= x; x ^= y | zamena bez privremene promenljive (sporije od privremene; kuriozitet) |
| (x ^ (x >> 31)) - (x >> 31) | apsolutna vrednost, 32-bitno označeno |
| x ^ (x >> 1) | binarno → Grejov kod |
Brojanje i obrtanje
| while (x) { x &= x - 1; n++; } | popcount (Kernighan); ili __builtin_popcount, bits.OnesCount, int.bit_count() |
| x ^ y, zatim popcount | Hamingovo rastojanje |
| popcount(x) & 1 | parnost |
| bswap32(x) / bits.ReverseBytes32 | zamena redosleda bajtova (endianness) |
| bits.Reverse32(x) | obrtanje redosleda bitova |
Oprez
- Pomeranje za ≥ širine je nedefinisano u C/C++; maskira se u JS-u i Javi (
1 << 32 == 1). - JS bitovske operacije odsecaju na 32 bita; iznad toga koristite BigInt.
~nad neoznačenim tipovima u C-u proširuje; kastujte nazad.- Pomeranje udesno negativne označene vrednosti je zavisno od implementacije u C-u pre C++20 (u praksi aritmetičko svuda).
- Prioritet:
&se vezuje slabije od==; pišite(x & m) == m.
Rezultati i poruke ovog alata prikazuju se na engleskom.