
XOR Fractals
Posted: Posted February 8thEdited February 8th by Xhin
 If you have some kind of image editor with layering, here's a fun trick for you.
1. Make a repeating horizontal black and white gradient.
2. On the next layer, make a repeating vertical black and white gradient.
3. Set the top layer to XOR the bottom layer.
You get this crazy thing:
I understand what XOR is and what it does but this kind of result is still really really unintuitive, so I've been playing with the math to try and understand it better.
Here's a summary of what XOR is:
XOR
the XOR operator is used somewhat like the + or * operators. You take two numbers, XOR them together and get a new number. The way this works comes down to binary values. For each bit, you do this function:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
Basically, XOR is true if both inputs are different, otherwise it's false. For numbers larger than one bit, you do this result on each bit and concatenate them together:
01 XOR 10 = 11
00 XOR 01 = 01
10 XOR 11 = 01
To try and figure out what was going on, I decided to make my own gradients using black, two shades of gray and white represented by the numbers 00, 01, 10 and 11 and then XOR them together. What i got was a similar fractalkind of pattern, but more interestingly, I noticed some interesting patterns in my XOR chart itself:
 00  01  10  11


00  00  01  10  11


01  01  00  11  10


10  10  11  00  01


11  11  10  01  00


Every single row contains the pattern [00,01,10,11] however the direction the pattern runs alternates left and right. Similarly, every single column contains the pattern [00,01,10,11] and the direction alternates left and right as well. I realize the rows and columns are the same thing, but seeing the chart like this is interesting because both axes are gradients.
I thus did the next logical step and used my image editor to "paint" the chart:
If you take the 16 biggest chunks to be the equivalent to the 16 values in the chart, you see the same exact patterns.. the allblack diagonal (00) crossing with the allwhite diagonal (11), the alternating gradients in each row and column (made by averaging the details in each box, or with a good blur tool).
So this is neat, it helps explain the overall structure. But why does it recurse infinitely like a fractal? Well, let's take the topleft quadrant of boxes:
If we wanted to add more "detail" to the gradient, say an extra two bits worth, then you would just use the same pattern from before, only apply it to each preexisting gradient value... so [0000,0001, 0010, 0011, 0100, 0101, 0110, 0111] is a perfect gradient of the two values with the two extra bits. You would put that on both axes, and then XOR all the extra bits together..
Sure enough, the value chart looks exactly like the picture, only now you have that extra 00 in front of it, so the colors are going to be darker overall but the pattern will still be there.
Every time you add two more bits of detail, the pattern repeats itself on a deeper level. Bitmaps have 24 bits available per pixel so even with small image spaces you're going to get these wonderfully detailed fractals.
This still isn't an intuitive result. I think the problem for me is that while any individual 16x16 grid makes sense, when seeing the whole thing you have these sharp edges everywhere. Somehow it "knows" to put up borders between sections. I started looking closer at the "borders" and I made another discovery:
The middle box is yet another microcosm of the whole pattern. This is cool but what's interesting is it isn't some shifted version of the whole pattern with extra bits, it is the whole pattern. The values are exactly the same as they would be if it was blown up 200%%%%. These jarring borders are present because they were present in the original pattern, and the 2 white and 2 black boxes have extra alternating detail because they had extra alternating detail in the original pattern as well.
But then I noticed something more about the "borders"  everywhere there is a jarring "border", the values on either side are opposites of one another. 01 and 10 are opposites, 11 and 00 are opposites. So how are those two patterns connected? Well, 01 and 00 are opposites too, it's just a different bit that's negated.
At this point I realized I was looking at this whole thing wrong, these aren't "gradients" that I'm looking at, they're alternating types of negation. If you look at the two middle columns you have the sequences:
[01,00,11,10] = A
[10,11,00,01] = B
In sequence A to go from 01 to 00, you negate the right bit. next, you negate both bits, then you negate the right bit. Then to get back to the original 01, you negate both bits again.
In sequence B, to go from 10 to 11, you negate the right bit. Then both bits, then the right bit again. Then to get back to the original 10, you negate both bits again.
So instead of a gradient what you're really looking at is an alternating pattern of negating the right bit and negating both bits over and over:
Here I've represented rightbit negation in red and bothbit negation in blue. If you expand these patterns out, you get some kind of checkerboardlike pattern:
This means you're not looking at a gradient at all, you're looking at alternating squares. The consequences of blue squares are just a lot more jarring to look at.
I felt like I understood the XOR fractals better, but I had a problem with the new pattern I've made  where are all the leftnegates? Why is the pattern so biased towards rightnegating? Well it turns out both leftnegating and nonegating are present in the pattern alongside rightnegating and bothnegating:
Here, I've representing leftnegating by yellow and nonegating by green. These form a nice checkerboard pattern of their own.


There are 6 Replies
