1937

Bitwise

A bitwise operator is not arithmetic. It is one wiring diagram, run across every column at once and never talking between them. Pick an operator and a column, and here is the circuit your own bits are closing.

The operator

    A
      B
        Shift by
          =

            A7 & 0F = 07

              Try

              A
              A7
              B
              0F
              Result
              07

              Two switches, 1937

              Claude Shannon was twenty-one and writing a master's thesis at MIT about telephone relays. What he proved in it was that the algebra George Boole had invented in 1847 for reasoning about true and false described, exactly, the behaviour of switches in a circuit.

              The move at the centre of it is small enough to draw, which is why it is drawn above. Put two switches in series and current arrives only if both are closed: that is AND. Put two in parallel and either one will do: that is OR. Wire a contact so it opens when energised instead of closing, and you have NOT.

              XOR is the interesting one, because it is not any arrangement of those. Select it above and the drawing changes shape: two changeover contacts, each moving between two paths rather than simply opening and closing, with their travellers crossed. You have used that circuit. It is the light at the end of a hallway with a switch at each end, and the reason flipping either one toggles it.

              What the thesis established is that Boolean algebra and a switching circuit are two descriptions of one thing. The drawing above is not an illustration of the operator beside it; it is the same statement written the other way. The notation has changed a great deal since. The correspondence has not.

              Eight circuits, not one number

              The thing that makes bitwise operators feel strange next to arithmetic is that there is no carry. Add two bytes and column three can change column four. AND two bytes and column three has no idea column four exists: it is a separate circuit with its own two switches, and all eight run at the same instant.

              That independence is the whole reason masking works. A mask is not a number you are doing sums with, it is a row of switches you have deliberately left open, and the columns you left closed pass through untouched.

              A shift is not a computation

              Select << or >> above and the switches vanish, because a shift has none. What replaces them is not empty space: it is the wiring. Every input line is routed to an output line some positions over, the lines whose source has run off the end are tied to the ground rail, and that ground connection is where the zeros come from. Nothing is computed. The bits are simply somewhere else.

              This is why shifting is the cheapest thing a processor does, and why a nibble is pulled out of a byte with a shift and a mask rather than with division and a remainder. Moving the high nibble down four places and masking off the rest is two operations that both cost almost nothing. It is the same answer as dividing by sixteen, arrived at without doing any arithmetic.

              What is real here, and what is not

              The logic is real; the circuit is a schematic

              Every result is computed with the actual operator on an actual integer, and the truth table shown is the one being applied to the column you selected. The circuit is a schematic of the switching arrangement, not a simulation of a relay: there is no coil, no contact bounce, no propagation delay, and no current in amps. It shows which paths are complete, which is the part Shannon's argument turns on.

              XOR is the hallway light, and that is not a metaphor

              AND, OR and NOT each map to one arrangement of ordinary on-off contacts. XOR maps to none of them: no series or parallel combination of plain make-contacts produces it, however you arrange them. What it needs is a contact that moves between two paths, a changeover, and two of those with their travellers crossed is exactly the circuit behind a light switched from both ends of a hallway. That is why flipping either switch toggles the lamp. Wire the travellers straight rather than crossed and you get XNOR, the same circuit inverted. A modern gate is transistors rather than relays, but the reason XOR costs more than AND has not changed.

              Right shift here is logical, not arithmetic

              Zeros come in at the top. A signed right shift in C or Java would copy the sign bit instead, so that shifting a negative number keeps it negative. This page treats the byte as unsigned throughout, which is the honest match for a page about switches rather than about number types.

              The contacts are not clickable, on purpose

              You set a bit in A or B and the contact moves. You cannot move the contact and have the bit follow, and that is not an oversight. In a relay the logical variable energises a coil, and the coil's magnetic field is what drags the contact across; the causation runs one way only. Letting you drag a contact would put the arrow backwards and quietly teach that a switch position and a bit are the same kind of thing. They are not: one is the cause and the other is the mechanism. The coils themselves are not drawn here, which is a simplification this page makes to stay on one screen.

              Eight bits, and no carry anywhere

              The width is fixed at eight because the byte is the family's unit and the page beside this one is about why. Nothing here carries between columns, which is true of these operators and emphatically not true of addition; that is a different circuit and a different piece.

              Sources