Short notes on mathematics and programming

Short notes on mathematics and programming

xor

XOR operation

Cheat sheet
✍️ Bitwise XOR combines two numbers into a third
✍️ Useful identity: a ^ b ^ a = b ^ a ^ a = b
✍️ Notations: ⊕, ^, xor; "sum modulo 2"; either A or B, but not both
✍️ Properties: associativity (a^(b^c)=(a^b)^c), commutativity (a^b=b^a), self-cancellation (x^a^a=x)
✍️ Wikipedia: exclusive or

Lecture
Earlier we mentioned a somewhat "mystical" way to swap two variable values using XOR. To explain this effect, we first reviewed the binary numeral system and conversion between base 2 and base 10. Now let’s examine XOR itself.

This is a useful operation, so it has several notations: ⊕, ^, and xor. On single bits it behaves like "sum modulo 2": the result is 0 when arguments are equal, and 1 when they differ. The two-bit truth table is 0110.

We are interested in the bitwise version: take binary representations of two numbers, apply XOR to each pair of corresponding bits, then assemble the resulting bits back into a number.

Example: 5 ^ 3. In binary: 101 ^ 011. Column by column: 1^0=1, 0^1=1, 1^1=0 -> 110, which is 6. Check in browser console: console.log(5 ^ 3).

Build an 8x8 XOR table for values 0...7:

|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 1 | 0 | 3 | 2 | 5 | 4 | 7 | 6 |
| 2 | 2 | 3 | 0 | 1 | 6 | 7 | 4 | 5 |
| 3 | 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 |
| 4 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 |
| 5 | 5 | 4 | 7 | 6 | 1 | 0 | 3 | 2 |
| 6 | 6 | 7 | 4 | 5 | 2 | 3 | 0 | 1 |
| 7 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |

Now verify the XOR swap algorithm. Let a = 5, b = 4. Track values after each assignment:

a = a ^ b; // a = 5 ^ 4 = 1, b = 4
b = a ^ b; // a = 1, b = 1 ^ 4 = 5
a = a ^ b; // a = 1 ^ 5 = 4, b = 5

As we can see, the algorithm works: values are swapped without a temporary variable.

#education #devTopic #junior