Boolean Logic: The Four Operations Hardware Actually Has
AND, OR, NOT and XOR are not programming conveniences layered over arithmetic. They are the primitive operations from which arithmetic itself is constructed, and they remain the cheapest instructions a CPU offers.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Four operations, and what each is actually for
The truth table below defines all four. What is worth attaching to each is its *characteristic use*, because that is what makes them recognisable in unfamiliar code rather than something to look up each time.
AND clears: any bit ANDed with 0 becomes 0, so AND with a mask isolates the bits you kept and zeroes everything else — the standard way to extract a field. OR sets: any bit ORed with 1 becomes 1, so OR with a mask turns flags on without disturbing others. XOR toggles and detects difference: a bit XORed with 1 flips, and any value XORed with itself is zero. NOT inverts every bit, which is how masks get built from their complements.
XOR earns particular attention because its properties are unusual. It is its own inverse — applying the same value twice returns the original — which is why it appears in checksums, in parity bits, in the one-time pad, and in the swap-without-a-temporary trick. That last one is worth recognising and not writing: modern compilers generate better code for an ordinary swap, and the XOR version fails when both operands are the same location.
| Operation | 0,0 | 0,1 | 1,0 | 1,1 | Characteristic use |
|---|---|---|---|---|---|
| AND | 0 | 0 | 0 | 1 | Clear bits — isolate a field with a mask |
| OR | 0 | 1 | 1 | 1 | Set bits — turn flags on without touching others |
| XOR | 0 | 1 | 1 | 0 | Toggle bits; detect difference; self-inverse |
| NOT | 1 | 1 | 0 | 0 | Invert every bit — build a mask from its complement |
Bitwise and logical are the same idea at different widths
Most languages have two families: && and || for conditionals, & and | for bit patterns. The distinction is not that one is high-level — it is that the logical operators short-circuit and the bitwise ones do not.
a && b evaluates b only if a was true, which makes it a control-flow construct that compiles to a conditional branch. a & b always evaluates both and combines them with a gate array. That difference matters twice over: for correctness, when the right-hand side has a side effect or would fault; and for performance, because the branching version is subject to Misprediction: What a Wrong Guess Costs while the bitwise version is not.
That second point is the seed of Branchless Code: A Trade, Not an Upgrade. Replacing an unpredictable branch with arithmetic or a bitwise select can be faster on data the predictor cannot learn — and slower on data it can, because a well-predicted branch is nearly free while the branchless version always does all the work. Which wins is a property of your data, not of the technique.
1// Short-circuit: the right side is not evaluated when the left decides.2if (ptr !== null && ptr.value > 0) { /* safe */ }3if (ptr !== null & ptr.value > 0) { /* faults: both sides evaluated */ }4 5// Short-circuit is a BRANCH. Bitwise is a GATE ARRAY.6// On unpredictable data the branch costs a misprediction;7// on predictable data it costs almost nothing and skips work.8 9// Standard flag idioms, all single-cycle:10const READ = 1 << 0, WRITE = 1 << 1, EXEC = 1 << 211 12let p = READ | WRITE // set: 0b01113const canExec = (p & EXEC) !== 0 // test: false14p |= EXEC // set: 0b11115p &= ~WRITE // clear: 0b10116p ^= READ // toggle: 0b10017 18// XOR is its own inverse -- the basis of parity and checksums.19const parity = [1, 0, 1, 1].reduce((a, b) => a ^ b, 0) // 1From logic to everything else
The reason this module starts here is that these operations are sufficient. NAND alone is functionally complete — every other operation, including all of arithmetic, can be built from NAND gates and nothing else. That is not merely a theoretical curiosity; it is why fabrication processes optimise a small number of gate types heavily and compose everything from them.
The path upward is short and concrete. XOR gives you the sum bit of a single-bit addition; AND gives you the carry. Put them together and you have a half adder. Chain half adders with carry propagation and you have arbitrary-width addition (Building an Adder: Where Arithmetic Comes From). Add negation and you have subtraction (Two's Complement: One Circuit for Addition and Subtraction). Add comparison and control and you have a processor.
The diagram below is that chain. Each level is built only from the level beneath it, and the whole of The ALU: Where Arithmetic Actually Happens sits at the top of it.
Key points
- AND clears, OR sets, XOR toggles and detects difference, NOT inverts — each is one gate per bit.
- A 64-bit bitwise operation is 64 gates in parallel and costs one cycle; width is effectively free.
- Logical operators short-circuit and compile to branches; bitwise operators always evaluate both sides.
- XOR is its own inverse, which is why it underpins parity, checksums and stream ciphers.
- NAND is functionally complete: all arithmetic is ultimately composed from logic gates.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Operands → gate array: both registers are presented to a bank of gates, one per bit position.
- 2Gates → outputs: every bit position is computed simultaneously; there is no iteration over the width.
- 3Result → register: the combined pattern is written back, typically in a single cycle.
- 4Flags → condition codes: the result may set zero and negative flags that a following branch can test.
- 5Composition → arithmetic: XOR and AND together form a half adder, which is the base case of addition.
- • Treating bitwise operators as an optimisation over logical ones; they are different operations with different evaluation semantics.
- • Assuming a 64-bit bitwise operation costs more than an 8-bit one — the gates operate in parallel.
- • Believing branchless code is universally faster; on predictable data a branch is nearly free and skips work entirely.
- • Using XOR swap in production code, where it is slower and breaks when both operands alias.
Consequences, controls and cost
- • Masking and flag manipulation are among the cheapest operations available, so packing related flags into one word costs almost nothing to use.
- • Replacing a branch with bitwise arithmetic removes misprediction risk at the price of always doing all the work.
- • Confusing `&` with `&&` produces both correctness bugs, when the right side must not be evaluated, and different performance characteristics.
- • Set operations over small universes can be represented as bitmasks, making membership tests single instructions.
- • Use named constants for masks and flags; the operation is cheap but a bare literal is unreadable.
- • Prefer short-circuit operators where the right side may be unsafe to evaluate, and bitwise ones where both sides are cheap and side-effect free.
- • Represent small sets as bitmasks when membership tests are hot — union, intersection and difference become single instructions.
- • Do not hand-write XOR swaps or similar tricks; compilers produce better code and the tricks have aliasing edge cases.
- • Inspect the disassembly to confirm a mask compiled to a single instruction rather than a branch or a call.
- • Compare branch-miss counters between a branching and a branchless version on your actual data distribution ([[performance-counters]]).
- • Benchmark bitmask set operations against a hash set at your real cardinality; the crossover is lower than most people expect.
- • Bitmask sets are extremely fast but limited to a small fixed universe and awkward to grow.
- • Bit-packed flags save space at the cost of readability and of a migration problem when the layout must change.
- • Branchless rewrites always perform all the work, which loses to a predictable branch that skips most of it.
Scope
§224 — what these claims are specific to.
- GENERALBitwise semantics are consistent across essentially all hardware and languages. What varies is shift behaviour at the edges: in C++ shifting by more than the width is undefined, while JavaScript masks the shift count to five bits.