Bits & Binary
Easy+70 XPNumbers are secretly rows of on/off light switches — and flipping them lets you do clever tricks like erasing duplicates with XOR.
No visualization loaded.
Watch
—
Press Run to begin.
Deep down, a computer doesn't store the number 13 the way you write it. It stores a row of tiny on/off switches — 1 means ON, 0 means OFF. Each switch is worth twice as much as the one to its right: …8, 4, 2, 1. Add up the switches that are ON and you get the number (8 + 4 + 1 = 13). That's BINARY. Once a number is just switches, we can combine two numbers switch-by-switch with bitwise operations — and one of them, XOR, has a superpower: it makes duplicates vanish.
▸What is binary, and what's a 'bit'?
A bit is one switch: it's either 0 (off) or 1 (on). Binary is counting using only these switches. Going right to left, the switches are worth 1, 2, 4, 8, 16… (each one doubles). To read a binary number, add up the place values of the switches that are ON. So 1011 means 8 + 0 + 2 + 1 = 11.
▸What do AND, OR, XOR, and shift do?
They line two numbers up switch-by-switch and combine each column. AND (&) turns a column ON only if BOTH are on. OR (|) turns it ON if EITHER is on. XOR (^) turns it ON only if the two are DIFFERENT (one on, one off). SHIFT (<< or >>) slides all the switches left or right — shifting left by 1 doubles the number, shifting right by 1 halves it.
▸Why is XOR so useful?
Because a number XOR'd with itself is 0 — every column matches, so every column turns off. That means XOR CANCELS pairs. If you XOR a whole list together, every value that shows up twice wipes itself out, and the one value that's alone is all that survives. You find the loner in one pass using no extra memory.
▸What's a bitmask?
A bitmask is a number you use as a row of yes/no flags — one switch per thing you care about (is item 0 chosen? item 1? item 2?). You flip a single switch with OR + a shift, check a switch with AND, and use the whole pattern to remember a set of choices in one cheap integer. It's how you pack many true/false answers into a single number.
▸Why are these operations basically free?
A number is a fixed row of switches (say 32 of them), and the processor flips a whole row in a single step. So AND, OR, XOR, and shifts on a fixed-width number are O(1) — constant time — no matter how big the number's value is.
How the work grows
O(1) per operation (fixed-width) is instant — doesn't grow at all. A number is a fixed row of switches, and the processor flips the whole row in one step. So each AND/OR/XOR/shift is constant time and uses no extra memory — XOR-ing a whole list is one O(n) pass with O(1) space.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.