Bit Sets and the XOR Trick

If you've had any amount of interest in programming and spent any amount of time pursuing it, it's very likely that you've come across the admittedly silly^[0] set of questions often used in our industry's broken^[1] hiring/screening processes. of which is how you'd swap two variables without introducing a temporary third one.

One of the famous solutions that works on any numeric pair of values with set size (think pointers or ints) is the XOR Trick^[2]. And it goes like this:

a <- 26 ;;any arbitrary values for a, b
b <- 6

procedure swap (x, y)
    x <- x XOR y
    y <- x XOR y
    x <- x XOR y

swap (ref a, ref b)

print (a) ;;6
print (b) ;;26

This blog post is about trying to explain what happened here on a bitwise level, aimed at beginner and intermediate programmers who may be curious, and would've definitely realized what's going on alone, but never really asked the question.
If you feel like you could learn something new about bitwise still, follow along..

Tell me what happened!

The XOR Trick's sole purpose is to swap the bits stored in two containers with three consecutive XOR operations. It may seem like magic if you don't understand how bitwise XOR works, and since this writeup targets beginners too, let's start from the very basics.

1. What is bitwise

There are very simple pieces of knowledge we need to establish before answering what is bitwise:

1. A variable is a (logical) container that holds a value.

   • by logical container I mean, it doesn't need to exist in one place on the machine.
   • if we say a <- 5 + 6, we say that the container a is expected to hold the value that results from the expression 5 + 6, which is 11.

2. A value, in our context (sory type theory people), is some group of bits that represent a number.

   • everything on the machine is a number. That includes your strings and lists etc...
   • a group of bits like 11010 encode the number 26, but they may also be encoding something that is represented by the number 26, like a character, or a memory address. If you have access to the raw bits, your operations on them will be agnostic to what they represent.

3. An expression is a group of operations on values that result in a new value.

   • this is different from a statement, which is sort of a recipe of operations that may cause effects on the program, but won't result in anything when assigned to a 'container' (aka variable).

4. Normal (arithmetic) operations (think +, -, *, ...), work on the numbers those bits represent, as you'd expect, 1+1 = 2, and 0 * anything = 0.

5. Logical operations (and, or, not, sometimes encoded as &&, ||, ! respectively), those work on logical expressions that evaluate to true/false.

6. Bitwise operations (AND, OR, XOR, INVERT, or often &, |, ^, ~ respectively), work on the internal representation of values as bits.

   • they are representation-agnostic
   • bitwise and logical are sometimes mixed-up, so it is important to remember that logical operations are a conversation is it noon "and" lunch is ready? while bitwise operations are a manipulation. We'll expand on this now.

So No.6 answers what is bitwise.

2. How does bitwise behave

Let's take a quick refresher on truth tables. Truth tables are ways in which we think about the result of a certain bit function depending on its input.

The truth table for a bit function AND:

 x | y | AND
---+---+-----
 0 | 0 |  0
---+---+-----
 0 | 1 |  0
---+---+-----
 1 | 0 |  0
---+---+-----
 1 | 1 |  1

What this tells us is that x AND y is set to 1 only when both x and y are set to 1. Look at the truth tables for the rest on your own, but we need to look at XOR for our exercise here:

 x | y | XOR
---+---+-----
 0 | 0 |  0
---+---+-----
 0 | 1 |  1
---+---+-----
 1 | 0 |  1
---+---+-----
 1 | 1 |  0

XOR only results in 1 when x is set, or y is set, exclusivley. That is, both cannot be set at the same time.
In other words, XOR results in 1 when x, y are different.

Binary bitwise operations like XOR take two groups of bits, and applies the bit function bit-by-bit (or bit-wise) on each corresponding two bits from each group. We can generalise this and say our bitwise operations are bit function mappings. That is, foreach bit in a (or n) bit group(s), do a bit function.

=> 26 ^ 6 = 28 ..why?

26: 11010
6:  00110
--------- XOR foreach
28: 11100

so..

---+---+---+---+---
 1 | 1 | 0 | 1 | 0
---+---+---+---+---
 |   |   |   |   | <-- XOR foreach
---+---+---+---+---
 0 | 0 | 1 | 1 | 0
---+---+---+---+---
 |   |   |   |   |
 V   V   V   V   V
---+---+---+---+---
 1 | 1 | 1 | 0 | 0
---+---+---+---+---


Only the two bits from right would result in 0. The rest are ones
So the result is the number 28 in decimal.

3. OK I get bitwise, can we talk about the actual swapping?

With bitwise operations, I like to see the binary representation of my values like I showed you above (well, usually hex representation because more compact and still a 1:1 mapping to binary, but we're learning here)

From now on, I'll represent my numbers as binary.. to really understand what's happening. Now, let's look at what happens bitwise when we do the three XORs:

a <- 00110
b <- 11010

a <- a XOR b ;;which is 11100 as we've seen

b <- a XOR b
;;a is now 11100 from the previous step, b is 11010,
;;what's the result of XOR? Hint: 00110

a <- a XOR b
;;a is 11100, b is 00110 from previous step, 
;;a becomes 11100 XOR 00110 which is 11010.

;;a and b are successfully swapped.

Still not sure how?

Well, let's look at values and bitwise operations under a different light: a really good tip I want to give, that I learned the hard way, is to think of your numbers as sets of bytes, and think of bitwise operations as mathematical set operations

So let's do the perspective switch before we begin:
AND -> intersection
OR -> union
XOR -> difference
INVERT -> complement

Now, how can we see our values as sets? Take the numbers 6, 26 as example:

6:
+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 |
+---+---+---+---+---+
  |   |   |   |   |
  4   3   2   1   0

26:
+---+---+---+---+---+
| 1 | 1 | 0 | 1 | 0 |
+---+---+---+---+---+
  |   |   |   |   |
  4   3   2   1   0

a: 6  -> 00110 -> {1, 2}
b: 26 -> 11010 -> {1, 3, 4}

The elements of our sets correspond to the positions of bits which are 1 on each number. Take a second look if you're not sure. We index from right and the first bit has index 0 (for mathematical reasons. See^[3] if you don't get base conversions).

Here's a quick exercise to get your set muscles warmed up:

• a ⋃ b = {2,1,3,4} .. a | b = 11110 = 30 (try it)
• a ⋂ b = {1} .. a & b = 00010 = 2
• a – b = {2,3,4} .. a ^ b = 11100 = 28

Here's a and b represented visually with Vinn diagrams:

         ,-----._
a ,'```,---.     \ b
 /    |     | 3   :
 |  2 |  1  |   4 |
  \    \___/     /
   `---'   `----'    (it's more like a cloud..
                      excuse my ascii, still learning)

Initially, a would be the diagram on the left, b would be the right, and they have the bit at index 1 in common. After the switch, the diagram will stay the same but labels a and b will switch places. The important thing with XOR is that no info is lost after an operation as long as the working set hasn't changed.

Now if I've convinced you that XOR corresponds mathematically to set difference, we can do the difference operations while keeping track of our set elements (bits) and see how the switch happens:

0. begin     .. a = {1,2},   b = {1,3,4}
1. a = a – b .. a = {2,3,4}, b = {1,3,4}
2. b = a – b .. a = {2,3,4}, b = {1,2}
3. a = a – b .. a = {1,3,4}, b = {1,2}

         ,-----._
  ,'```,---.:o:o:\
 /::::|ooooo|o3o:o:
 |::2:|oo1oo|:o:4:| b(oo)
  \::::\___/:o:o:/  a(::)
   `---'   `----'

         ,-----._
  ,'```,---.:::::\
 /:o:o|ooooo|:3::::
 |:o2o|oo1oo|:::4:| b(oo)
  \:o:o\___/:::::/  a(::)
   `---'   `----'

         ,-----._
  ,'```,---. ::::\
 / ooo|:o:o:|:3::::
 |oo2o|:o1o:|:::4:| b(oo)
  \oooo\___/:::::/  a(::)
   `---'   `----'

Of course you can colour the vinn diagrams on your own better than my ascii would show, and follow on it for visual aid, but I hope this clears things in a good manner.

Takeaway

Bitwise operations being looked-at as set operations is a useful idea in computer science when dealing with lightweight flags. A great example of this is the Linux syscall open(2) which is declared as follows:

int open(const char *pathname, int flags);

What's interesting is that flags are just an int, and this is deliberate. A quick way to understand why is to examine the flag values:

In decimal, they might not mean much, except being powers of 2.. But in binary, we quickly realize that each flag is more-or-less a singleton set, which in turn implies we can combine the flags by taking the unions of the sets, in other words, bitwise-or

open("/etc/passwd", O_RDWR | O_APPEND | O_NONBLOCK);

and it just works! Sure enough, this is exactly what the manpage wants us to do:

The argument flags must include one of the following access modes: O_RDONLY,
O_WRONLY, or O_RDWR.  These request opening the file read-only, write-only, or
read/write, respectively.

In addition, zero or more file creation flags and file status flags can be
bitwise-or'd in flags.  The file creation  flags  are  O_CLOEXEC, O_CREAT,
O_DIRECTORY, O_EXCL, O_NOCTTY, O_NOFOLLOW, O_TMPFILE, and O_TRUNC.  The file
status flags are all of the remaining flags listed below.
....

I hope with this post you learned something useful out of the completely useless games recruiters play.

[0]: https://simpleprogrammer.com/programming-interview-questions/ Some will even ask you to implement those on a whiteboard. I don't think I need to say much about how this is completely useless and has zero correspondence to actual work ↩︎

[1]: https://daedtech.com/hiring-is-broken/ ↩︎

[2]: https://en.wikipedia.org/wiki/XOR_swap_algorithm ↩︎

[3]: https://mathstats.uncg.edu/sites/pauli/112/HTML/secbinary.html or IDK, ddg it ↩︎