5. AND, OR, XOR, NOT: Bit-by-Bit Logic

The concept

Every conversion in Part A treated a bit pattern as a single number — decimal 181, 0xb5, and 1011 0101 were all the same amount, just written three different ways. This lesson introduces a different kind of operation, one where the bits aren't read as a number at all, but combined one position at a time.

That "one position at a time" part is worth pausing on: it runs against an instinct reinforced throughout Lessons 2 and 4 — place-value addition carries, so a full position spills into its neighbor (0111 + 1 = 1000, a carry rippling through three positions). None of the four operations below carry, borrow, or let one position affect another. The result's bit 3 depends only on bit 3 of the input(s) — never bit 2, never bit 4. Even if two numbers being combined don't line up in some other way, position 3 only ever talks to position 3.

Four operations, each one a simple rule applied independently at every position:

• AND — the result bit is 1 only when both input bits are 1.

• OR — the result bit is 1 when either input bit (or both) is 1.

• XOR ("exclusive or") — the result bit is 1 when the two input bits differ.

• NOT — the only operation here with one input instead of two: it flips every bit, 1 becomes 0 and 0 becomes 1.

  a: 0 0 1 1 b: 0 1 0 1 a AND b: 0 0 0 1 a OR b: 0 1 1 1 a XOR b: 0 1 1 0

  a: 0 1 NOT a: 1 0

Each table above is the entire operation. Applying one to two 8-bit numbers just means running its table eight times, once per position, with the positions never interacting.

Example 1 — AND

Take A = 0110 1101 and B = 1010 1011, and AND them position by position:

bit index:  7  6  5  4  3  2  1  0
A:          0  1  1  0  1  1  0  1
B:          1  0  1  0  1  0  1  1
A AND B:    0  0  1  0  1  0  0  1

Only positions 5, 3, and 0 have a 1 in both A and B, so those are the only positions where the result has a 1. A AND B = 0010 1001.

Example 2 — OR

Same A and B, this time OR'd:

bit index:  7  6  5  4  3  2  1  0
A:          0  1  1  0  1  1  0  1
B:          1  0  1  0  1  0  1  1
A OR B:     1  1  1  0  1  1  1  1

Every position except bit 4 has a 1 in at least one of A or B, so every one of those positions comes out 1 in the result. A OR B = 1110 1111.

Example 3 — XOR

Same A and B again, this time XOR'd:

bit index:  7  6  5  4  3  2  1  0
A:          0  1  1  0  1  1  0  1
B:          1  0  1  0  1  0  1  1
A XOR B:    1  1  0  0  0  1  1  0

Positions 5, 4, and 3 have matching bits in A and B (both 1 at position 5, both 0 at position 4, both 1 at position 3), so those come out 0. The rest differ, so those come out 1. A XOR B = 1100 0110.

Example 4 — NOT

NOT only takes one input. Take A = 0110 1101 and flip every bit:

bit index:  7  6  5  4  3  2  1  0
A:          0  1  1  0  1  1  0  1
NOT A:      1  0  0  1  0  0  1  0

NOT A = 1001 0010. There's a handy check here: A and NOT A should always add up to all-ones (255 for 8 bits), since every position contributes its place value to exactly one of the two numbers, never both and never neither. A is 109 (Lesson 2's running example) and NOT A is 128 + 16 + 2 = 146. Sure enough, 109 + 146 = 255.