XOR, 1's complement addition and modulo-2 division

1. Write 0xB6 in binary.
   Stuck? Peek at 0.2.2 Binary, decimal and hex; powers of 2

   • Binary places: 1, 2, 4, 8, 16, 32, 64, 128, …; MSB left, LSB right.
   • Hex: one digit = 4 bits; A–F = 10–15; group from the right.
   • k bits → 2ᵏ values, 0 … 2ᵏ − 1.
   • Bits needed for N values = smallest k with 2ᵏ ≥ N.
   • 2¹⁰ = 1024 · 2¹⁶ = 65,536 · 2²⁰ ≈ 1.05 M · 2³² ≈ 4.29 × 10⁹.

   Read lesson 0.2.2

2. Bits in 3 KB?
   Stuck? Peek at 0.2.1 Bits, bytes and prefixes: powers of 10 for rates, powers of 2 for sizes

   • 1 B = 8 b. Lower-case b = bit, upper-case B = byte.
   • Rates: k = 10³, M = 10⁶, G = 10⁹ (bps).
   • Sizes: K = 2¹⁰, M = 2²⁰, G = 2³⁰ (bytes) — unless the question says 1000.
   • Time to push out = (size in bits) ÷ (rate in bit/s).
   • ms = 10⁻³ s, µs = 10⁻⁶ s, ns = 10⁻⁹ s.

   Read lesson 0.2.1

3. What carries bits on a link?
   Stuck? Peek at 0.1.1 Why networks exist: hosts, links and sending data

   • Network = devices + links that exchange data.
   • Host = where a message starts or ends (laptop, phone, server).
   • Link = physical path: copper (voltage), fibre (light), wireless (radio).
   • All content → bits → signals → bits → content; meaning comes from an agreed encoding.
   • One link per pair of n hosts: n(n − 1)/2 links — too many, so links are shared.

   Read lesson 0.1.1

Signals on a link get disturbed: a spark, a scratch on a fibre, a microwave oven near Wi-Fi. A 0 can arrive as a 1. The receiver needs a cheap way to notice. The tricks it uses are made of three bit operations you learn today: XOR, 1's complement addition and modulo-2 division. Phase 2 turns each one into an error-catching method.

XOR outputs 1 when its two input bits are different. What is 1011 XOR 1011? And what happens if you XOR a pattern with the same key twice?

1011 XOR 1011 = 0000 — anything XOR itself is zero. XOR twice with the same key gives back the original: (A ⊕ K) ⊕ K = A. That "undo" property is why XOR shows up everywhere.

AND, OR, NOT, XOR

Bitwise operators work on each position independently:

XOR properties

• a ⊕ 0 = a; a ⊕ a = 0; order does not matter.
• (a ⊕ k) ⊕ k = a — XOR undoes itself.
• XOR is addition without carry: 1 + 1 = 0, nothing carried.
• The number of 1s in a ⊕ b counts the positions where a and b differ.

1's complement

1's-complement addition adds two k-bit numbers normally, and if a carry falls off the left end, that carry is wrapped around and added back at the right end ("end-around carry").

Modulo-2 arithmetic

In modulo-2 arithmetic there are no carries and no borrows: addition and subtraction are both XOR. A bit string can be read as a polynomial: 1011 = x³ + x + 1 (the 1s mark which powers of x are present).

Modulo-2 long division

Long division where each "subtract" is an XOR. At each step look at the leading bit of the current chunk: if it is 1, XOR with the divisor (quotient bit 1); if 0, XOR with zeros (quotient bit 0). Bring down the next bit and repeat. The remainder has one bit fewer than the divisor.

        11101   ← quotient
101 ) 1101011
      101   ← leading 1: XOR with divisor
      ---
       111
       101   ← leading 1: XOR with divisor
       ---
        100
        101   ← leading 1: XOR with divisor
        ---
         011
         000   ← leading 0: XOR with zeros
         ---
          111
          101   ← leading 1: XOR with divisor
          ---
           10   ← remainder (2 bits)

Putting it together

• XOR marks differences and undoes itself; it is addition without carries.
• 1's-complement addition wraps the carry around; the complement flips every bit.
• Modulo-2 division uses XOR at each step; the remainder is one bit shorter than the divisor.

• In modulo-2 division, decide by the leading bit, not by "is the chunk bigger than the divisor".
• The remainder always has exactly (divisor length − 1) bits — keep leading zeros (0010, not 10).
• 1's-complement addition wraps the carry back in; ordinary binary addition just drops it.

XOR = "spot the difference". Wrap-around = the carry walks round the back and rejoins at the start.

XOR (spotting differences), 1's-complement sums and modulo-2 remainders are exactly the three error-catching tools of Phase 2. Next (0.2.4): shared links are a game of chance — what is the probability that exactly one of many senders speaks? For that we need logarithms and basic probability.

1. MCQ

   1101 ⊕ 0110 = ?

   1. 1011
   2. 0100
   3. 1111
   4. 0011
2. NAT

   8-bit 1's-complement sum of 11111111 and 00000001, as a decimal number?

   Write your answer before opening the key.

3. MCQ

   Remainder of 1101011 ÷ 101 in modulo-2 division:

   1. 10
   2. 01
   3. 11
   4. 00
4. MSQ

   Which are true in modulo-2 arithmetic?

   1. Addition and subtraction are the same operation.
   2. 1 + 1 = 0 with no carry.
   3. The bit string 10011 is the polynomial x⁴ + x + 1.
   4. The remainder of division by a 5-bit divisor has 5 bits.
5. MCQ

   The 16-bit 1's complement of 0x1A5C is:

   1. 0xE5A3
   2. 0xE5A4
   3. 0x1A5B
   4. 0xA5C1

• AND (mask), OR, NOT (flip), XOR (1 where bits differ).
• a ⊕ a = 0, a ⊕ 0 = a, (a ⊕ k) ⊕ k = a.
• 1's complement = flip all bits; 1's-complement addition wraps the end carry back in.
• Modulo-2: + = − = XOR, no carries; bits ↔ polynomial.
• Mod-2 division: leading 1 → XOR divisor; leading 0 → XOR zeros; remainder = (divisor length − 1) bits.

• bitwise AND / OR / NOT
• XOR (⊕)
• 1's complement
• 1's-complement addition (end-around carry)
• modulo-2 arithmetic
• polynomial view of a bit string
• modulo-2 division, remainder

1. a ⊕ a = ?
   Reveal answer

   0. And (a ⊕ k) ⊕ k = a.
2. How does 1's-complement addition treat the final carry?
   Reveal answer

   It wraps it around and adds it at the right end.
3. Remainder length for a 5-bit divisor?
   Reveal answer

   4 bits.
4. 10011 as a polynomial?
   Reveal answer

   x⁴ + x + 1.

• 1's-complement sum, fast: add in decimal or hex as usual; if the result ≥ 2ᵏ, subtract 2ᵏ and add 1. — k-bit words; repeat if the wrap itself overflows (rare).
• Complement of a hex word: subtract from 0xFFFF (each digit from F). — 16-bit words; for k bits subtract from 2ᵏ − 1.