[Solved]: Does a shift operation distribute over XOR

ignougroup
Problem Detail: 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?

Asked By : Morwenn

Answered By : Ilmari Karonen

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/58264

Leave a Reply