What do bitwise operators look like in 3d?

Question

The hypothetical relation is $z = \mathrm{xor}\left(x,y\right)$ where xor is any bitwise operator such as AND, OR, NAND, etc. I see that these operations may be defined for integers trivially using binary-decimal conversion.

In the same way, can't we perform bitwise arithmetic on real numbers? For example, the following is $\mathrm{xor}\left(1.5, 2.75\right)$:

    01.01
xor 10.11
---------
=   11.10

The answer is 3.5.

What do the 3D plots of the binary bitwise operators look like, and what are some interesting mathematical properties? (e.g. gradient)

By the way, if you plot any of these using Sage, can I see the code? I couldn't get bitwise operations to work this way.

Answer 1

Basically, it looks like this:

^{(Image rendered in POV-Ray by the author, using a recursively constructed mesh, some area lights and lots of anti-aliasing.)}

In the picture, the blue square on the $x$-$y$ plane represents the unit square $[0,1]^2$, and the yellow shape is the graph $z = x \oplus y$ over this square, where $\oplus$ denotes bitwise $\rm xor$.

Note that this graph is discontinuous at a dense subset of the plane. In the 3D rendering above, no attempt has been made to accurately portray the precise value of $x \oplus y$ at the points of discontinuity, and indeed, it is not generally uniquely defined. That is because the discontinuities occur at points where $x$ or $y$ is a dyadic fraction, and therefore has two possible binary expansions (e.g. $\frac12 = 0.100000\dots_2 = 0.011111\dots_2$).

As can be seen from the picture, the graph is self-similar, in the sense that the full graph over $[0,1]^2$ consists of four scaled-down and translated copies of itself. Indeed, this self-similarity is evident from the properties of the $\oplus$ operation, namely that:

• $\displaystyle \frac x2 \oplus \frac y2 = \frac{x \oplus y}2$, and
• $\displaystyle x \oplus \left(y \oplus \frac12\right) = \left(x \oplus \frac12\right) \oplus y = (x \oplus y) \oplus \frac12$.

The first property implies that the graph of $x \oplus y$ over the bottom left quarter $[0,1/2]^2$ of the square $[0,1]^2$ is a scaled-down copy of the full graph, while the second property implies that the graphs of $x \oplus y$ in the other quarters are identical to the first quarter, except that the lower right and upper left ones are translated up by $\frac12$.

The resulting fractal shape is also known as the Tetrix or the Sierpinski tetrahedron, and is a 3D analogue of the 2-dimensional Sierpinski triangle, which is also closely linked with the $\rm xor$ operation — one way to construct approximations of the Sierpinski triangle is to compute $2^n$ rows of Pascal's triangle using integer addition modulo $2$, which is equivalent to logical $\rm xor$.

It may be surprising to observe that this fully 3-dimensional fractal shape is indeed (at least approximately, ignoring the pesky multivaluedness issues at the discontinuities) the graph of a function in the $x$-$y$ plane. Yet, when viewed from above, each of the four sub-tetrahedra indeed precisely covers one quarter of the full unit square (and each of the 16 sub-sub-tetrahedra covers one quarter of a quarter, and so on...).

Answer 2

Here's what XOR looks like. Black is $z=0$; White is $z=1$. The x and y axes run from $[0,1]$.

I used the (naive) formula

$ x \oplus' y = \left(\lfloor 2^{20}x\rfloor \oplus \lfloor 2^{20}y\rfloor\right)2^{-20} $

At least with this naive interpretation, the function does not seem continuous.

EDIT: using analogous formulas, here are

AND:

OR:

They all look pretty similar, but the 0:1 ratio difference is noticable.

The XOR looks like a fractal, rather than an addition plot.

Answer 3

I can't compete with k_g's pretty picture, but to list some interesting properties. Firstly, we have that $\oplus$ (which we'll use to denote xor - or the "symmetric sum") under a suitable domain (like $(\mathbb R -\mathbb Q) \cup \{0\}$ to avoid issues of non-unique representations, or, more abstractly, infinite sequences of bits): $$x\oplus x = 0$$ $$0\oplus x = x$$ $$x \oplus y = y\oplus x$$ $$(x\oplus y)\oplus z =x\oplus (y\oplus z)$$ Hey, those are kind of like the same properties that addition has! Abstractly, we could link this operation to addition through the concept of an (abelian) group, which basically is a way to study "nicely behaved" operations. An interesting thing here is that the way to "undo" this addition is to do it again - that is, if we have $x\oplus c$ and want to find $x$, then we just find it as $x=(x\oplus c)\oplus c$, so we don't need a separate subtraction operation.

We also have some properties which explain the fractal nature of k_g's image (and why it is discontinuous everywhere). In particular, we get: $$(2x)\oplus (2y) = 2(x\oplus y)$$ which describes a sort of self-similarity. In addition to using the algebraic properties from before, we can therefore see that we could write a procedure for generating the plot as a fractal:

• Start with any bounded function over $[0,1]\times[0,1]$. Call this $f_0$.
• Define $f_i$ by copying $f_0$ four times to make a bigger square, increasing the two off-diagonal entries by $1$ and then scaling everything down by a factor of two. Symbolically, we get: $$f_{i+1}(x,y)=\begin{cases}f_i(\frac{x}2,\frac{y}2)&&\text{if }x < \frac{1}2,y<\frac{1}2\\f_i(\frac{x-1}2,\frac{y}2)+\frac{1}2&&\text{if }x > \frac{1}2,y<\frac{1}2\\f_i(\frac{x}2,\frac{y-1}2)&&\text{if }x < \frac{1}2,y>\frac{1}2\\f_i(\frac{x-1}2,\frac{y-1}2)+\frac{1}2&&\text{if }x > \frac{1}2,y>\frac{1}2\end{cases}$$ where we see that $f_{i+1}$ is composed of $4$ copies of $f_i$. As we do this longer and longer, we get an array that sort of looks like: $$f_0:\qquad\begin{matrix}0\end{matrix}$$ $$2f_1:\qquad\begin{matrix}0&&1\\1&& 0\end{matrix}$$ $$4f_2:\qquad\begin{matrix}0&&1&&2&&3\\1&& 0&&3&&2\\2&&3&&0&&1\\3&&2&&1&&0\end{matrix}$$ $$8f_3:\qquad\begin{matrix}0&&1&&2&&3&&4&&5&&6&&7\\1&&0&&3&&2&&5&&4&&7&&6\\2&&3&&0&&1&&6&&7&&4&&5\\3&&2&&1&&0&&7&&6&&5&&4\\4&&5&&6&&7&&0&&1&&2&&3\\5&&4&&7&&6&&1&&0&&3&&2\\6&&7&&4&&5&&2&&3&&0&&1\\7&&6&&5&&4&&3&&2&&1&&0\end{matrix}$$ And we could keep going on like that to generate a big table of $\oplus$, but let's not. The important thing to note is how each table is composed of shifted copies of the last table, leading to a fractal nature. This method is basically using something called "fixed point iteration" to define $\oplus$ - if $f_i(x,y)$ were already $x\oplus y$, then $f_{i+1}$ would not change it. It happens that the map taking $f_i\mapsto f_{i+1}$ always moves towards $\oplus$ - in a precise sense, it is a "contraction map" meaning that if every value of $f_{i}(x,y)$ is within a margin of $d$ of $x\oplus y$, then $f_{i+1}(x,y)$ is within a margin of $\frac{d}2$ everywhere- which gives precise bounds on how accurate this method is.

We can, interestingly, prove that $x\oplus y$ is continuous except where $x$ or $y$ is a dyadic rational - that is, expressible as $\frac{a}{2^b}$. So, it is continuous almost everywhere, but discontinuous at a dense set (which is highly counterintuitive). To prove this, choose any $\varepsilon>0$ and some $n$ with $2^{-n}<\varepsilon$. Then, we can choose some $\delta$ such that neither the interval $(x-\delta,x+\delta)$ nor $(y-\delta,y+\delta)$ contains a number of the form $\frac{a}{2^n}$, which is possible if neither is a dyadic rational. Then, as long as we restrain $x'$ and $y'$ within these intervals, the first $n$ digits (after the decimal point) of $x'\oplus y'$ will agree with those of $x\oplus y$, and thus be within $2^{-n}<\varepsilon$ of each other. This proves continuity at those points - and, as we see from k_g's picture, each of those lines across the picture occurs when $x$ or $y$ is a dyadic rational (with more extreme jumps occurring when $b$ in $x=\frac{a}{2^b}$ is small).

I would tend to doubt that it is differentiable anywhere except $0$, but I might think on that further before saying anything definitive.