Does a shift operation distribute over XOR

Question

In this question, we abuse the mathematical notation to express bitwise operations in the following way:

• $\ll$ is a binary left shift
• $\oplus$ is a bitwise XOR
• $0b1, 0b110, 0b10 \ldots$ are used to denote raw bits
• $repr$ is a function associating to a number a given bit representation
• $\mathbb{B}$ is the set of natural numbers to which $repr$ associates a two's complement bit representation
• $\mathbb{G}$ is the set of natural numbers to which $repr$ associates a Gray code bit representation

---

I was trying to prove that the binary representation of a power of $2$ in binary reflected Gray code was always two ones followed by zero or more zeroes, except for $2^0$. The demonstration is roughly as follows:

We know that the two's representation of powers of $2$ can be expressed as follows:

$$ \forall n \in \mathbb{N} : repr(2_\mathbb{B}^n) = 0b1 \ll n $$

And the function $to\_gray$ can be expressed as follows:

$$ \forall n \in \mathbb{B} : to\_gray(n) = n \oplus (n \gg 1) $$

Therefore, we have the following equivalence (ignoring the special case when $n = 0$):

$$\begin{align*} \forall n \in \mathbb{N} : repr(to\_gray(2_\mathbb{B}^n)) &= (0b1 \ll n) \oplus ((0b1 \ll n) \gg 1)\\ &= (0b1 \ll n) \oplus (0b1 \ll (n - 1))\\ &= (0b10 \ll (n - 1)) \oplus (0b1 \ll (n - 1))\\ &= 0b11 \ll (n - 1) \end{align*}$$

However, the last line of the demonstration assumes that $\ll$ distributes over $\oplus$. Is this assumption true or does it only work for my specific use case?

Answer 1

Yes, bit shifts distribute over all bitwise logical operations $\odot$ for which $0 \odot 0 = 0$,* in the sense that: $$(a \odot b) \ll n = (a \ll n) \odot (b \ll n)$$ and: $$(a \odot b) \gg n = (a \gg n) \odot (b \gg n).$$ In particular, these identities hold true for bitwise AND, OR and XOR.

To show this, let $x_k$ denote the $k$-th bit of the number $x$.* Then, for each bit $k$, we have (by definition) the following identities:

$$\begin{aligned} (x \ll n)_k &= x_{k-n} \\ (x \gg n)_k &= x_{k+n} \\ (x \odot y)_k &= x_{k} \odot y_k \\ \end{aligned}$$

and thus:

$$\begin{aligned} ((a \odot b) \ll n)_k &= (a \odot b)_{k-n} \\ &= a_{k-n} \odot b_{k-n} \\ &= (a \ll n)_k \odot (b \ll n)_k \\ &= ((a \ll n) \odot (b \ll n))_k \\ \end{aligned}$$

(and correspondingly for right shifts). Since this identity holds for all bits $k$, it also holds for the entire bitstrings.

The key observation here is that bit shifts just renumber the bits of the bitstring (and possibly discard and/or introduce some new bits at the ends), while bitwise logical operations like XOR, by definition, operate identically and independently on each bit position. Thus, the two types of operations are effectively orthogonal in their effects.

---

<sup>*) By convention, for out-of-range bit indexes, we define $x_k = 0$ when $k < 0$, and either $x_k = 0$ (for logical shifts) or $x_k = x_{k_{\max}}$ (for arithmetic shifts) when $k > k_{\max}$, where $k_{\max}$ is the highest valid bit index of the bitstring $x$. This corresponds to the convention that the lowest bits of a left-shifted number are set to $0$, and the highest bits of a right-shifted number are either set to $0$ or set to equal the highest bit of the original number, depending on the type of right shift used.

As a consequence, for operations where $0 \odot 0 \ne 0$, such as NAND and NOR, the identity $(x \odot y)_k = x_{k} \odot y_k$ may not hold when $k$ is out of range. Thus, for such operations, the distributive properties given above may not hold for the lowest $n$ bits (for $\ll n$) and the highest $n$ bits (for $\gg n$, where $\gg$ is a logical shift). However, arithmetic right shifts with sign extension (as well as right shifts on arbitrary-length numbers with implicit sign extension) do fully distribute over all bitwise logical operations.</sup>

Answer 2

Shift is right-distributive over XOR, and over many other operations as well (AND, OR, addition, min, max)

As for why, informally for the bitwise operations I'd explain it as: bitwise operations are like pointwise operations (if you view a number as a function from bit index to the bit at that index), translating (or permuting, etc) the positions distributes over doing the operation. Eg if we have two numbers $f$ and $g$ as such functions, then $(f ⊕ g)(k) = f(k) ⊕ g(k)$ so $(f ⊕ g)(k + j) = f(k + j) ⊕ g(k + j)$, here $f(k + j)$ is just $f$ shifted by $j$ so this showed that it didn't matter whether the shift is done after the XOR or on both of its operands. In general this applies to any remapping of the coordinates, ie $(f ⊕ g)(r(k)) = f(r(k)) ⊕ g(r(k))$ where $r$ is any function from $\mathbb{N}$ to $\mathbb{N}$.

As pointed out in the comments, this also relies on the operator to map two zeroes to an other zero, ie $0 ⊕ 0 = 0$.

Or simpler but less general, using string notation, let's say we have two number $a$ and $b$ and let their XOR be $c$, then $a0^k ⊕ b0^k = c0^k$ and $(a⊕b)0^k = c0^k$ (by substitution).

Answer 3

The following doesn't answer the question, since shifts aren't permutations, as pointed out by user2357112 in the comments.

---

Any permutation operator is right-distributive over any bitwise operator. It clearly makes no difference whether you combine the bits and then permute their order, or permute the bits and then combine them.

More formally, let $\pi$ is any permutation of $\{1, \dots, n\}$ and write $\Pi$ for the operator that maps $(x_1, \dots, x_n)$ to $(x_{\pi(1)}, \dots, x_{\pi(n))}$. Let $\odot$ be any bitwise operator. We have \begin{align*} \Pi((x_1, \dots, x_n)\odot(y_1, \dots, y_n)) &= \Pi((x_1\odot y_1), \dots, (x_n\odot y_n)) \\ &= ((x_{\pi(1)}\odot y_{\pi(1)}), \dots, (x_{\pi(n)}\odot y_{\pi(n)}))\\ &= (x_{\pi(1)}, \dots, x_{\pi(n)}) \odot (y_{\pi(1)}, \dots, y_{\pi(n)})\\ &= \Pi(x_1, \dots, x_n)\odot \Pi(y_1, \dots, y_n)\,. \end{align*}

Answer 4

Left- and right-shifts right-associate with any bitwise binary operator $\odot$ that has $0\odot0=0$:

\begin{align*} (\langle x_1, \dots, x_n\rangle\odot\langle y_1, \dots, y_n\rangle)\ll1 &=\langle x_1\odot y_1, \dots, x_n\odot y_n\rangle \ll1\\ &=\langle x_2\odot y_2, \dots, x_n\odot y_n, 0\rangle\\ &=\langle x_2\odot y_2, \dots, x_n\odot y_n, 0\odot0\rangle\\ &=\langle x_2, \dots, x_n, 0\rangle \odot \langle y_2, \dots, u_n, 0\rangle\\ &=(\langle x_1, \dots, x_n\rangle\ll1)\odot(\langle y_1, \dots, y_n\rangle\ll1)\,. \end{align*}

The case of right-shifts and shifts of more than one bit are similar. For cyclic shifts, see my other answer; in that case, it's not required that $0\odot0=0$.