3
$\begingroup$

We know that the integers $1\le k\le 2^n-1$ (which for the purposes of this post may be identified with their binary expansions) can be mapped to their Gray code equivalents with $k \oplus (k >> 1)$. And so if we want to find which bit has changed from one code word to the next, we can compute $((k+1)\oplus((k+1)>>1))-(k\oplus(k>>1))$. This will have an integer value $\pm 2^m$ for some $m$, and the value of $m$ is the position of the bit which has changed, and the sign determines whether that bit has been added or subtracted. For example, for $n=8$, the differences are $$ 2, -1, 4, 1, -2, -1 $$ (We assume we start with a code word which consists of single 1 followed by zeros, that is, $k=2^{n-1}$.)

Not myself being a combinatorialist, but trying to implement some combinatorial algorithms, I'm wondering if there's an efficient way of generating those differences. Is using bit operations as above pretty much the best, or is there a better, faster, method?

$\endgroup$

1 Answer 1

1
$\begingroup$

If you just want one term of the sequence, you're not going to be able to do better than the bit operations. (Maybe there's some way to rearrange them to have fewer bit operations, maybe not.)

If you want to generate the whole sequence, then there's a nice repeating pattern that lets you generate many terms quickly.

First, let's add a starting term of $1$ from the sequence (the change from $k=0$'s Gray code to $k=1$'s Gray code). Then we can quickly extend the first $2^n-1$ terms to the first $2^{n+1}-1$ terms, as follows:

  1. Append $2^n$. For example, $1,2,-1,4,1,-2,-1$ becomes $$1,2,-1,4,1,-2,-1\color{red}{,8}.$$
  2. Duplicate the first $2^n-1$ terms. For example, the previous sequence becomes $$1,2,-1,4,1,-2,-1,8\color{red}{,1,2,-1,4,1,-2,-1}.$$
  3. Change element in position $3 \cdot 2^{n-1}$ from $2^{n-1}$ to $-2^{n-1}$. For example, the previous sequence becomes $$1,2,-1,4,1,-2,-1,8,1,2,-1,\color{red}{-4},1,-2,-1.$$

Without the signs included, the sequence $$1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, \dots$$ follows a simpler rule: the $k^{\text{th}}$ term is the highest power of $2$ dividing $k$, and follows the rule $\frac{(k \oplus (k-1))+1}{2}.$ It is sequence A006519 in the OEIS. As for the signs, you just want the subsequence of terms equal to $\pm 2^m$ alternate in sign separately for every $m$.

$\endgroup$
1
  • $\begingroup$ Thank you for the advice to use the OEIS - I don't know why I didn't think of it myself. And in fact the sequence I want is A055975. $\endgroup$
    – Alasdair
    Commented Dec 22, 2019 at 3:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .