XORing Hexadecimal Numbers

The XOR operation is something that comes up quite often while studying certain CS courses. This post describes a technique for performing the operation quickly by hand while dealing with numbers in hexadecimal form - something that could be encountered in a test or exam of such a course.

XORing Binary Numbers

Before moving to hexadecimal numbers, let us talk about XORing binary numbers for a moment. For numbers in binary form, the XOR operation is trivial. For a single bit, we have:

x y x \(\oplus\) y
0 0 0
0 1 1
1 0 1
1 1 0

Extending this to more than 1 bit is also pretty simple - we just carry out the computation bit by bit, e.g. for two 8-bit binary numbers 01101110 and 00111101, we have:

0110 1110
\(\oplus\) 0011 1101
0101 0011

You can think of this as either bit-by-bit addition mod 2, or the process of determining whether the corresponding bits are the same or different (if they are the same, their XOR is 0; if they are different, their XOR is 1). Either way of thinking about it is equally valid.

XORing Hexadecimal Numbers

Now, what about hexadecimal numbers? One approach is to convert the hexadecimal number to binary and then use the above method. The good thing about this is that the conversion does not have to be carried out on the number as a whole: each hexadecimal digit can be converted individually, resulting in 4 binary digits per hexadecimal digit, and concatenating those converted quadruplets gives us the binary representation of the entire hexadecimal number. This means that you can generate the following table on a rough page and use it to help you out in converting from hexadecimal to binary rapidly:

Hex Binary Hex Binary
0 0000 8 1000
1 0001 9 1001
2 0010 A 1010
3 0011 B 1011
4 0100 C 1100
5 0101 D 1101
6 0110 E 1110
7 0111 F 1111

For example, say we have to XOR the hexadecimal numbers 61BE and F26A. We lookup the binary representation of each digit from the above table, compute the XORs as before, and then convert the result back to hexadecimal, again using the table:

6 1 B E
0110 0001 1011 1110
F 2 6 A
\(\oplus\) 1111 0010 0110 1010
1001 0011 1101 0100
9 3 D 4

This method works quite well, honestly. But, hear me out: if we are already spending some time making a table, why not directly make a lookup table for the XORs of all hexadecimal digits with each other, instead of using a table just for base conversions and still doing the computations bit by bit? I'm sure you are wondering whether I am in my senses, considering the fact that this will be the size of such a table:

\(\oplus\) 0 1 2 3 4 5 6 7 8 9 A B C D E F
0 0 1 2 3 4 5 6 7 8 9 A B C D E F
1 1 0 3 2 5 4 7 6 9 8 B A D C F E
2 2 3 0 1 6 7 4 5 A B 8 9 E F C D
3 3 2 0 1 7 6 5 4 B A 9 8 F E D C
4 4 5 6 7 0 1 2 3 C D E F 8 9 A B
5 5 4 7 6 1 0 3 2 D C F E 9 8 B A
6 6 7 4 5 2 3 0 1 E F C D A B 8 9
7 7 6 5 4 3 2 1 0 F E D C B A 9 8
8 8 9 A B C D E F 0 1 2 3 4 5 6 7
9 9 8 B A D C F E 1 0 3 2 5 4 7 6
A A B 8 9 E F C D 2 3 0 1 6 7 4 5
B B A 9 8 F E D C 3 2 1 0 7 6 5 4
C C D E F 8 9 A B 4 5 6 7 0 1 2 3
D D C F E 9 8 B A 5 4 7 6 1 0 3 2
E E F C D A B 8 9 6 7 4 5 2 3 0 1
F F E D C B A 9 8 7 6 5 4 3 2 1 0

And yes, I agree that it would be a silly idea if we're talking about this table. The time it would take to generate this table would be way more than the time required for computing a significant number of XORs with the conversion method outlined above. But, as it happens, I came across an ingenious idea in an interesting Cryptography Stack Exchange answer which resolves this problem and actually does allow us to use such a lookup table for directly calculating hexadecimal XORs. It turns out that the above table can be condensed and expressed in the following form:

\(\oplus\) 4C 5D 6E 7F 08 19 2A 3B
08 19 2A 3B 4C 5D 6E 7F
4C 08 08 19 2A 3B 4C 5D 6E 7F
5D 19 19 08 3B 2A 5D 4C 7F 6E
6E 2A 2A 3B 08 19 6E 7F 4C 5D
7F 3B 3B 2A 19 08 7F 6E 5D 4C

Much better, right? With a bit of practice, this condensed form of the table can be generated in under a minute, and it provides a significant boost to all XOR calculations made from that point onward. The answer I mentioned does not really go into much detail about the method for generating and using this table, so that is what I'll be doing in this post. I'll describe how to make this table, and how to lookup XORs of hexadecimal digits using it.

Generating the Condensed Hexadecimal XOR Table

As this table has two header rows and two header columns, we need a way to talk about them unambiguously. Let us call the first header row and column as the outer header row and column respectively, and the second header row and column as the inner header row and column respectively. The non-header rows and columns of the table will be called first, second, third and fourth as usual. We start by generating the inner header row. Write the first eight hexadecimal digits (from 0 to 7) in order like this:

\(\oplus\) 0 1 2 3 4 5 6 7

Then write down the next eight hexadecimal digits (from 8 to F) adjacent to the previously written digits, like this:

\(\oplus\) 08 19 2A 3B 4C 5D 6E 7F

Next, we write down the outer header row. The first four cells of the outer header row are the last four cells of the inner header row, while the last four cells of the outer header row are the first four cells of the inner header row. That is, the halves are swapped like this:

\(\oplus\) 4C 5D 6E 7F 08 19 2A 3B
08 19 2A 3B 4C 5D 6E 7F

Now, we set up the header columns. They are basically the transpose (or reflection) of the first (i.e. left) half of the header rows, as shown below:

\(\oplus\) 4C 5D 6E 7F 08 19 2A 3B
08 19 2A 3B 4C 5D 6E 7F
4C 08
5D 19
6E 2A
7F 3B

As we are done with the header rows and columns, let us move on towards filling the interior of the table. The first interior row is the same as the inner header row, while the last (i.e. fourth) consists of two halves, with each half being the corresponding half of the inner header row but reversed:

\(\oplus\) 4C 5D 6E 7F 08 19 2A 3B
08 19 2A 3B 4C 5D 6E 7F
4C 08 08 19 2A 3B 4C 5D 6E 7F
5D 19
6E 2A
7F 3B 3B 2A 19 08 7F 6E 5D 4C

As for the second and third rows, they consist of four parts each, with every quarter of the second row being the reversed form of the corresponding quarter of the first row, and every quarter of the third row being the reversed form of the corresponding quarter of the fourth row:

\(\oplus\) 4C 5D 6E 7F 08 19 2A 3B
08 19 2A 3B 4C 5D 6E 7F
4C 08 08 19 2A 3B 4C 5D 6E 7F
5D 19 19 08 3B 2A 5D 4C 7F 6E
6E 2A 2A 3B 08 19 6E 7F 4C 5D
7F 3B 3B 2A 19 08 7F 6E 5D 4C

Note that this is just one of the many possible ways to understand the structure of this table. The table has several different symmetries if you look at it, so you can use any of those properties to memorise its structure. Whichever you use, just remember to practise generating the table a few times so that you are able to do so quickly in your test.

Using the Condensed Hexadecimal XOR Table

Now that we have seen how we can generate this condensed XOR table, let us see how to use it. For this purpose, let us reuse the example we showed previously, i.e. we wish to XOR the two hexadecimal numbers 61BE and F26A. First, we find the XOR of 6 and F using the table. For this, we first find 6 in the header columns. It can be found at the 0th position (i.e. the left digit) of the third row of the outer header column. As we found it in the outer header column, we will look at the outer header row to find F (even though it will be there in the inner header row as well!). We find it at the 1st position (i.e. the right digit) of the fourth column of the outer header row. The value corresponding to these headers inside the table is 19. As the positions of 6 and F within their respective cells were different (0 for 6 and 1 for F), we choose the value at the 1st position (because 0 \(\oplus\) 1 = 1) of 19, i.e. 9. Thus, 6 \(\oplus\) F = 9:

\(\oplus\)4C5D6E7F08192A3B
08192A3B4C5D6E7F
4C0808192A3B4C5D6E7F
5D1919083B2A5D4C7F6E
6E2A2A3B08196E7F4C5D
7F3B3B2A19087F6E5D4C

Next, we need to find the XOR of 1 and 2. 1 is at position 0, second row of the inner header column. So, we try to find 2 in the inner header row. It is found at position 0, third column of the inner header row. As 0 \(\oplus\) 0 = 0, we will take the 0th position of the value at the cell inside the table corresponding to the row and column specified by the headers (which is 3B), i.e. 3:

\(\oplus\)4C5D6E7F08192A3B
08192A3B4C5D6E7F
4C0808192A3B4C5D6E7F
5D1919083B2A5D4C7F6E
6E2A2A3B08196E7F4C5D
7F3B3B2A19087F6E5D4C

B is at position 1, fourth row of the inner header column, so we look for 6 in the inner header row and find it at position 0, seventh column. As the positions are different, we take position 1 of the cell at the fourth row and seventh column (5D), which is D:

\(\oplus\)4C5D6E7F08192A3B
08192A3B4C5D6E7F
4C0808192A3B4C5D6E7F
5D1919083B2A5D4C7F6E
6E2A2A3B08196E7F4C5D
7F3B3B2A19087F6E5D4C

Lastly, E is at position 1, third row of the outer header column, so we look for A in the outer header row and find it at position 1, seventh column. As the positions are the same, we take the digit at position 0 of the cell at the third row and seventh column (4C), which is 4:

\(\oplus\)4C5D6E7F08192A3B
08192A3B4C5D6E7F
4C0808192A3B4C5D6E7F
5D1919083B2A5D4C7F6E
6E2A2A3B08196E7F4C5D
7F3B3B2A19087F6E5D4C

Therefore, we get 61BE \(\oplus\) F26A = 93D4. In general, to find x \(\oplus\) y using this condensed table, search for x in the header columns. If it's found in the inner header column, look for y in the inner header row; if it's found in the outer header column, search for y in the outer header row. Extract the value corresponding to the row and column in which x and y were found - the answer is the digit that is in the position which is the XOR of the positions of x and y in their respective cells. This way, we can lookup the XORs for hexadecimal digits directly from this table.

While this may seem to be a convoluted method, a few practice rounds will make it second nature. Though, of course, any potential benefits of this method will only be realised in case you are required to perform many such computations as part of your test or other task. Otherwise, it might not be feasible to spend time generating this table and you might be better off doing the few computations manually instead. In any case, I found this to be an interesting method for calculating the XORs of hexadecimal digits by hand fast, so thought I should share. See you around, folks!

~ASD0x41

Comments

Post a Comment

Popular Posts