Sierpiński triangle? In my bitwise AND?

Exploring a peculiar bit-twiddling hack at the intersection of 1980s geek sensibilities.

I’m an ethusiastic promoter of the C language. One of the outmoded cultural phenomena associated with C are bit-twiddling hacks: a collection of brain-teasers that implement improbably complex algorithms using bitwise arithmetic. They are often developed under the guise of code optimization, but they mostly serve to impress your friends and confuse enemies.

I have also previously written about fractals; they’re pieces of mathematical curiosa that enjoyed a near-mythical status in 1980s, but are no longer talked about in polite company. One of the better-known fractals is the Sierpiński triangle. It is constructed by taking an ordinary (filled) triangle and then successively removing middle one-fourths from what’s left:

The first steps of building the Sierpiński triangle.

The fractal has some interesting properties; most notably, the surface area decreases by 25% in each iteration while the perimeter increases by 50%, so the respective limits are 0 and ∞. This is despite the figure retaining the same overall footprint as the starting triangle.

Anyway — there is this astonishingly simple bit-twiddling hack that somehow produces the Sierpiński triangle (demo):

#include <stdint.h>
#include <stdio.h>

#define LEN (1 << 6)

int main() {
  for (uint32_t y = 0; y < LEN; y++) {
    for (uint32_t x = 0; x < LEN; x++)
      printf((x & y) ? "  " : "MM");
    putchar('\n');
  }
}

In essence, we iterate over a pair of integer coordinates, x and y, and then color each cell depending on whether bitwise x & y is zero or non-zero. That’s it! For a pair of counters running from 0 to 63, the result is this:

What.

Increasing the range of the counters adds more detail, producing a finer-grained fractal with more and more nested triangles. But… why?

A hand-wavy explanation is that the bit-twiddling part is mostly a red herring. There’s nothing clever about bitwise AND; the magic is the positional numeral system! If we visualize the process of counting from 0 to 63 in binary, we get the following bit pattern:

Binary count from 0 to 63 (left to right).

The value of the least significant bit is toggling with every tick, the next bit is flipping back and forth at half the frequency, and so on. This can be thought as a fractal pattern in itself: as we increase the size of the counter, the visualization acquires more and more self-similar detail, with no hard limit in sight. In fact, if you squint your eyes, the pattern does look a bit like a succession of somewhat squished (log-scale) triangles.

For a more precise tie-in to the Sierpiński shape, we do need to peek under the hood of the x & y operation. We’re calculating a bitwise AND of two counters, but what is the result of that?

Well, it’s sufficient for any bit of x & y to be set to satisfy the condition in the program, so let’s start by looking at the MSB. If you’re used to binary numbers, it should be obvious that in our 6-bit (64-value) case, the most significant bit of the x coordinate will be zero for all values less than 32, and one for all values equal to or above that threshold:

\(\begin{array}{|c|c|} \hline \textbf{Counter state} & \textbf{Binary} \\ \hline x = 0 & 000000 \\ x = 1 & 000001 \\ x = 2 & 000010 \\ ... & ... \\ x = 31 & 011111 \\ x = 32 & \color{crimson}1\color{black}00000 \\ x = 33 & \color{crimson}1\color{black}00001 \\ ... & ...\\ x = 63 & \color{crimson}1\color{black}11111 \\ \hline \end{array}\)

This divides the x axis into two halves; the same is true for the y coordinate, so we end up with four quadrants in the two-dimensional plot. Only in the bottom right quadrant (32x32 cells), both of the MSBs are set:

\(\begin{array}{|c|c|c|} \hline & MSB(x) = 0 & MSB(x) = 1 \\ \hline MSB(y) = 0 & 0 & 0 \\ \hline MSB(y) = 1 & 0 & \color{crimson}{1} \\ \hline \end{array}\)

In other words, plotting the MSB of x & y nets us the following:

Plotting the value of the MSB of x & y.

Next, let’s have a look at the second most significant bit (#4). The value cycles at twice the frequency of the MSB, wrapping around in the middle. The same is happening in the y axis. In effect, we get the same pattern as before, but tiled twice in each axis:

\(\begin{array}{|c c| c c|} \hline * & * & * & * \\ *& 1 & * & 1 \\ \hline * & * & * & * \\ *& 1 & * & 1 \\ \hline \end{array}\)

In other words, the operation sets the bottom right sub-quadrants of every original quadrant.

The following visualization shows the regions where bit #4 of x & y is set. These regions are superimposed on top of the previously-calculated layout for the MSB:

Squares set after taking into account bit #4.

There are no surprises with bit #3. The pattern wraps around four times in each axis, lighting up the following regular grid of blocks:

Contributions of bit #3 (in teal).

Again, we can express it as a divide-and-set operation running at a finer scale and toggling the bottom right sub-sub-quadrants:

\(\begin{array}{|c c| c c|c c| c c|} \hline * & * & * & * & * & * & * & * \\ * & 1 & * & 1 & *& 1 & * & 1 \\ \hline * & * & * & * & * & * & * & * \\ * & 1 & * & 1 & *& 1 & * & 1 \\ \hline * & * & * & * & * & * & * & * \\ * & 1 & * & 1 & *& 1 & * & 1 \\ \hline * & * & * & * & * & * & * & * \\ * & 1 & * & 1 & *& 1 & * & 1 \\ \hline \end{array}\)

The same goes for bit 2, wrapping around eight times and adding a regular pattern of 64 blocks:

Contributions of bit #2 (in teal).

After two more steps, we end up with the following result; the dark blue cells are coordinates that were never set in any of the passes, netting the familiar triangle:

Mr. Sierpiński, I presume?

In effect, the algorithm is an iterative block-removal approach in disguise; it just doesn’t look that way because the passes are “parallelized” by the arithmetic logic unit of a CPU — at least up to the maximum hardware-supported bit width of an integer.

---

I write well-researched, original articles about geek culture, electronic circuit design, and more. If you like the content, please subscribe. It’s increasingly difficult to stay in touch with readers via social media; my typical post on X is shown to less than 5% of my followers and gets a ~0.2% clickthrough rate.