Does a shift operation distribute over XOR 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)) &amp;= (0b1 \ll n) \oplus ((0b1 \ll n) \gg 1)\\
&amp;= (0b1 \ll n) \oplus (0b1 \ll (n - 1))\\
&amp;= (0b10 \ll (n - 1)) \oplus (0b1 \ll (n - 1))\\
&amp;= 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?
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).