1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.


*) 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.

$\endgroup$
  • $\begingroup$ (0 NOR 0)<<1=10. (0<<1 NOR 0<<1)=(00 NOR 00)=11. I think you need the requirement that operation maps two instances of the introduced bit to the introduced bit. (Ie. if you are introducing a 0 bit you need the operation to map two 0 bits to 0) $\endgroup$ – Taemyr Jun 5 '16 at 10:00
  • $\begingroup$ I like your explanation. It's really clear, thanks :) $\endgroup$ – Morwenn Jun 5 '16 at 18:21
4
$\begingroup$

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*}

$\endgroup$
  • $\begingroup$ This argument doesn't quite work because shifts aren't permutations. For example, if you were to left shift two integers and then XNOR them rather than XORing, the LSB would be 1, but if you were to XNOR and then left shift, the LSB would be 0. $\endgroup$ – user2357112 Jun 5 '16 at 1:41
  • $\begingroup$ @user2357112 Yes, you're right. :-( Thanks for pointing that out. I removed the claim that shifts are permutations so I believe what remains is correct, but irrelevant to the actual question. $\endgroup$ – David Richerby Jun 5 '16 at 2:43
  • $\begingroup$ It works for the question at hand. If your words are $b$ bits, it works for the upper $b-1$ bits of the result. As you shift in $0$s (why do we assume that?) it works as long as the result of $0 \oplus 0=0$, which is why it works for XOR and not for XNOR. $\endgroup$ – Ross Millikan Jun 5 '16 at 5:09
  • $\begingroup$ @RossMillikan It can be made to work. But the whole detour via permutations becomes pointless. $\endgroup$ – David Richerby Jun 5 '16 at 9:20
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ The first part of this answer doesn't quite work, because a shift doesn't just move the original bits around. A left shift or zero-extending right shift will also introduce a bunch of zeros that weren't in the original number. You need to rely on the fact that 0 XOR 0 is 0; if you were working with an operation like XNOR, where 0 XNOR 0 is 1, none of this would work. $\endgroup$ – user2357112 Jun 5 '16 at 4:31
  • $\begingroup$ Actually, multiplication in $GF(2^k)$ doesn't quite match ordinary bit shifting (even assuming that you meant to map $x \ll n$ into $x \odot 2^n$; otherwise it doesn't work at all) because any bits that get shifted off the top will trigger a reduction, and thus effectively get XORed back into the lower bits. However, it turns out that ordinary multiplication by $2^n$ (modulo a power of two, if you want to work with a limited number of bits) does correspond to a left shift by $n$ bits. $\endgroup$ – Ilmari Karonen Jun 5 '16 at 9:06
  • $\begingroup$ @user2357112 true, I hadn't thought of operations that introduced ones "for free", well that's annoying, I'm not sure how to fix it with that, let's just call it a precondition then.. $\endgroup$ – harold Jun 5 '16 at 9:47
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.