Bitové operace: AND, OR, XOR a k čemu doopravdy jsou

Tohle je statická kopie kapitoly pro vyhledávače. Interaktivní verze má animované obrázky, kontrolní otázky a tlačítka, která příklad načtou do kalkulačky.

Bitové operace: AND, OR, XOR a k čemu doopravdy jsou

Tyhle čtyři operátory pracují na každém bitu zvlášť a nezajímá je, jaké číslo z těch bitů dohromady vyjde. To je celé. Sčítání má přenos z bitu do bitu; tohle ne.

Dvě čísla a čtyři operace. Přepínej mezi nimi a sleduj, který sloupec se změní — pravidlo je vidět na jednotlivém sloupci, ne na výsledném čísle.

operace	pravidlo na jednom bitu	na co se používá
`a & b` AND	1 jen když obojí	ptát se: „je tenhle bit nastavený?“
`a \| b` OR	1 když aspoň jedno	zapínat bity
`a ^ b` XOR	1 když se liší	přepínat, porovnávat, kontrolní součty
`a & ~b`	1 když v a a ne v b	vypínat bity

XOR je zvláštní a stojí za vlastní odstavec

Je sám sobě inverzní: x ^ k ^ k = x. To má tři důsledky, které se objevují pořád dokola:

Přepínač. x ^= maska obrátí právě ty bity, které jsou v masce. Nepotřebuje vědět, jak byly nastavené předtím.
Kontrola. XOR všech bajtů zprávy je nejjednodušší kontrolní součet. Chytí každou lichou chybu v jednom sloupci — a nechytí dvě chyby ve stejném sloupci. Proto existuje CRC, o kterém je celá kapitola v LinkLabu.
Šifra, která není šifra. šifra = text ^ klíč se dešifruje tímtéž. Když je klíč opravdu náhodný, dlouhý jako zpráva a použije se jednou, je to jednorázová tabulka a je prokazatelně nerozluštitelná. Když se klíč použije dvakrát, stačí ty dvě zprávy XORovat mezi sebou a klíč zmizí.

x ^ k ^ k = xXOR je sám sobě inverzní

De Morgan

Dvě identity, které platí na každém bitu, a proto na celém slově:

~(a & b) = ~a | ~b ~(a | b) = ~a & ~bDe Morganovy zákony

Praktický užitek: podmínku „ne (je to A a zároveň B)“ jde přepsat na „není to A nebo není to B“, a druhá varianta jde často vyhodnotit dřív.

Logické a bitové operátory nejsou totéž. V C a v JavaScriptu je && logické „a“, které vyhodnocuje zkráceně a vrací pravdu nebo nepravdu, kdežto & je bitové a vyhodnotí obě strany vždycky. Záměna & za && často „funguje“, protože 1 & 1 je 1 — a rozbije se až ve chvíli, kdy je jedna strana třeba 2, protože 1 & 2 je 0.