More on bit-reversal

Introduction

Carrying on from the Danielson-Lanczos notes, we will discuss some interesting aspects of bit reversal here. We will consider all binary numbers that can be formed with \(N\) bits, calling it the set \(S(N)\). So,

\[\begin{align*} & S(0)=\Phi \\ & S(1)=\{0,1\} \\ & S(2)=\{00,01,10,11\}_2=\{0,1,2,3\}_{10} \dots \end{align*}\]

where the subscript denotes the base of the set. This will be omitted further below where the distinction is obvious. Now denote by \(R_N\) the action of bit-reversal applied to \(S(N)\), i.e., \(R_N=\)Rev\((S(N))\). A key property of bit-reversal is that it is an involution: reversing twice returns the original number, so \(\texttt{Rev}(\texttt{Rev}(x))=x\) for all \(x \in S(N)\). This means every element either maps to itself (a fixed point) or belongs to a pair \(\{x,\texttt{Rev}(x)\}\) that swaps under reversal. Much of the structure that we discuss in this document follows from this fact.

\[\begin{align*} R_0&=\Phi \\ R_1&=\{0,1\} \\ R_2&=\{00,10,01,11\}_2=\{0,2,1,3\}_{10} \\ R_3&=\text{Rev}(\{000,001,010,011,100,101,110,111\}_2) \\ &=\{000,100,010,110,001,101,011,111\}_2=\{0,4,2,6,1,5,3,7\}_{10} \\ R_4&=\{0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15\}_{10} \dots \end{align*}\]

There are some things to notice here. First, that some numbers reverse to themselves. \(R_2(3)\), \(R_3(2)\) and \(R_4(17)\) are some of them. By \(R_N(p)\) we mean the \(p\)-th element of the set with indexing starting from \(0\). Second, that every \(R_N\) can be formed from \(R_{N-1}\) by a simple procedure that has been explained in the earlier document on the Danielson-Lanczos method. To construct the bit-reversed array for \(N=p\), take the one for \(N=p/2\) and after each element \(i\), insert an index \(2^{N-1}\). We will rewrite the arrays given above but with the new elements colored red. The elements in black are carried over from the previous \(N\).

\[\begin{align} & N=1 \implies \{0,1\} \nonumber \\ & N=2 \implies \{0,{\color{red}{2}},1,{\color{red}{3}}\} \nonumber \\ & N=3 \implies \{0,{\color{red}{4}},2,{\color{red}{6}},1,{\color{red}{5}},3,{\color{red}{7}}\} \nonumber \\ & N=4 \implies \{0,{\color{red}{8}},4,{\color{red}{12}},2,{\color{red}{10}},6,{\color{red}{14}},1,{\color{red}{9}},5,{\color{red}{13}},3,{\color{red}{11}},7,{\color{red}{15}}\} \label{cycred} \end{align}\]

Cycles

Coming back to the first point, let us call the points that reverse to themselves cycles.¹ Also, denote the set of cycles of \(R_N\) by \(C_N\). Thus,

\[\begin{align*} C_0&=\Phi \\ C_1&=\{0,1\} \\ C_2&=\{0,3\} \\ C_3&=\{0,2,5,7\} \\ C_4&=\{0,6,9,15\} \\ C_5&=\{0,4,10,14,17,21,27,31\} \\ C_6&=\{0,12,18,30,33,45,51,63\} \\ C_7&=\{0,8,20,28,34,42,54,62,65,73,85,93,99,107,109,127\} \\ C_8&=\{0,24,36,60,66,90,102,126,129,153,165,189,195,219,231,255\} \end{align*}\]

Cycles can be found by simply finding the symmetric binary numbers for a certain \(N\). We are interested in where these cycles occur in \(R_N\). To see this, we will color the cycles in blue in the sets below.

\[\begin{align} R_1&= \{ {\color{blue}{0}},1\} \nonumber \\ R_2&= \{ {\color{blue}{0}},2,1,{\color{blue}{3}}\} \nonumber \\ R_3&= \{ {\color{blue}{0}},4,{\color{blue}{2}},6,1,{\color{blue}{5}},3,{\color{blue}{7}}\} \nonumber \\ R_4&= \{ {\color{blue}{0}},8,4,12,2,10,{\color{blue}{6}},14,1,{\color{blue}{9}},5,13,3,11,7,{\color{blue}{15}}\} \nonumber \\ R_5&= \{ {\color{blue}{0}},16,8,24,{\color{blue}{4}},20,12,28,2,18,{\color{blue}{10}},26,6,22,{\color{blue}{14}},30,1,{\color{blue}{17}},9,25,5,{\color{blue}{21}},13,29,3,19,11,{\color{blue}{27}},7,23,15,{\color{blue}{31}}\} \label{r_blue} \end{align}\]

Obviously, \(R_N(2^{N-1})=1\) and \(R_N(1)=2^{N-1}\). The two trivial cycles are \(0\dots0\) and \(1\dots1\), which are the first and last elements. One can also spot easily the cycles \(100\dots001\) and \(011\dots110\). The former is two places before the “central” \(1\) and the latter right after it. See the elements \(R_N(2^{N-1}-2)\) and \(R_N(2^{N-1}+1)\) in the above sets. For example, \({\color{blue}{14}}\) and \({\color{blue}{17}}\) in \(R_5\), and \({\color{blue}{6}}\) and \({\color{blue}{9}}\) in \(R_4\).

How many cycles are present in \(R_N\)? By counting up to \(N=8\), we get the following table.

N	Cycles	N	Cycles
1	2	5	8
2	2	6	8
3	4	7	16
4	4	8	16

Let us denote the number of cycles in \(R_N\), or the number of elements in \(C_N\), as \(\mathcal{N}_N\). We may conjecture that if \(N\) is even, then \(\mathcal{N}_N=2^{N/2}\), and if \(N\) is odd, then \(\mathcal{N}_N=2^{(N+1)/2}\). This can easily be verified by looking at binary numbers in \(5\) and \(6\) bits. Take \(00100\). Finding a cycle under bit-reversal is equivalent to fixing the middle element — the 1 here — and folding one side onto the other. The elements to the left of the middle one can be chosen in \(2^{(N-1)/2}\) ways, and the middle element can be either \(0\) or \(1\). So, multiplying by two gives \(\mathcal{N}_{N\text{ odd}}=2^{(N+1)/2}\). For the even \(N\) case, consider \(001100\). Here it is merely a question of folding straight down the middle, so we only need to choose our bits on one side, giving \(\mathcal{N}_{N\text{ even}}=2^{N/2}\). Combining both odd and even cases, we can write the number of cycles for \(N\) bits as \(\mathcal{N}_N=2^{\lceil N/2 \rceil}\). This sequence \(\{2,2,4,4,8,8,16,16,\dots\}\) appears in the On-Line Encyclopedia of Integer Sequences (OEIS) as A060546. A consequence of the involution property is that the remaining \(2^N - \mathcal{N}_N\) elements pair off into 2-cycles, so the total number of 2-cycles is \((2^N - 2^{\lceil N/2 \rceil})/2\).

Distribution

How are the cycles distributed in \(R_N\)? We have already noted the locations of the trivial ones at the two ends of the set and the two close to the “central” \(1\). Let us write down the number of elements between consecutive cycles for the first few \(N\)’s, represented by Distances in the table below.

N	Distances	N	Distances
1	0	5	3,5,3,2,3,5,3
2	2	6	11,5,11,2,11,5,11
3	1,2,1	7	7,11,7,5,7,11,7,2,7,11,7,5,7,11,7
4	5,2,5	8	23,11,23,5,23,11,23,2,23,11,23,5,23,11,23

We see that the distances between consecutive cycles are symmetric about the middle distance of 2. It may be more useful to write the distances as a mere difference of their position indices, which would increase values in the table above by \(1\). We represent this distance by DiffIndex. The symmetric part to the right of the central distance is denoted by an ellipsis.

N	DiffIndex	N	DiffIndex
1	0	5	4,6,4,3,…
2	3	6	12,6,12,3,…
3	2,3,…	7	8,12,8,6,8,12,8,3,…
4	6,3,…	8	24,12,24,6,24,12,24,3,…

We are beginning to see some kind of structure. Apart from the central distance of \(3\), we see a doubling for each \((2k-1,2k)\) pair. Now look at the progression from \(N=3\) to \(N=5\) to \(N=7\). We see that we can take a mirror image around the central \(3\), multiply all distances by \(2\), reappend the central \(3\) at the end of that sequence to obtain the next set of differences. Thus, to get the \(N=7\) set, take the \(N=5\) one of \(4,6,4,3,\dots\). Mirroring about \(3\) gives \(4,6,4,3,4,6,4\). Doubling leads to \(8,12,8,6,8,12,8\). This gives the first set of distances. To generate the full set, we just need to mirror it after crossing the central distance of \(3\), giving \(8,12,8,6,8,12,8,3,\dots\). The same logic holds for going from \(N=4\) to \(N=6\) to \(N=8\).

Now look at the value of the first nontrivial cycle for a \((2k-1,2k)\) pair. You will see that there is a tripling. Why? What is the smallest cycle we can form after \(0\dots0\)? Writing down all possible cycles as we will show below for a couple of cases, we will see that it is the binary number with all zeroes except a one in the middle when \(N\) is odd and two ones in the middle when \(N\) is even. Their values in base \(10\) are \(2^{(N-1)/2}\) for the former and \(2^{N/2}\) for the latter. Taking the difference of these two numbers gives us \(3(2^{(N-1)/2})\), which is triple the one for \(N=2k-1\).

Generating cycles

Let us now write down the cycles for \(N=7\) and \(N=8\) in both binary and base \(10\). Look at the \(N=7\) table first. Note that the central bit in the binary numbers alternates between \(0\) and \(1\). For every consecutive \(0,1\) pair, we have the same 3-bit binary number — underlined in green in the tables below — which is mirrored about the central element to make the cycle. What is the value of this underlined binary in base \(10\)? It is shown in blue in the tables below. Now look at equation \eqref{r_blue}! These are exactly the values in our bit-reversed arrays \(R_N\)! For odd \(N\), we reproduce the array \(R_{(N-1)/2}\) and for even \(N\) we get \(R_{N/2}\). There is no central bit for \(N=8\) so the mirror is simply in the middle of the binary sequence.

The central bit in (a) is colored brown, the bits to the right are underlined in green, and the decimal value of the underlined binary is shown in blue. There is no central bit in (b).

The tables below show \(N=9\) and \(N=10\).

Cycles with decimal and binary values for N=9 and N=10.

We see that to construct cycles for any even \(N\), we just need the bit-reversed array \(R_{N/2}\). A suitable mirroring of the elements of this set leads to \(C_N\). We don’t need to search for all symmetric combinations of bits. Similarly for odd \(N\). And thus we can write the generator of cycles for \(N\) bits as \(R_{\lfloor N/2 \rfloor}\). The tables below show similar cycles for \(N\in\{3,4,5,6\}\).

More on distribution of cycles

Differences

In this section we will look at our data visually in the form of plots. First we will plot the DiffIndex sequence of distances between cycles. The figures below are plots of the DiffIndex sequence with the x-axis being the position of the distance value. We see our middle distance of \(3\) with the curve being mirrored about it. Looking at the values and the shapes makes the algorithm of arriving at the next pattern in the even and odd sets clear. For example, to obtain the curve for \(N=5\), take the points in the \(N=3\) curve, double their difference values, append the value 3 and take a mirror image about that point.

More structures can be seen if we plot these curves in the same graph. Specifically, we become more aware of some levels, which are shown as horizontal lines. The figure below shows the DiffIndex sequence for consecutive \(N\) values, followed by even \(N\) and odd \(N\) separately. In the even case, the levels are formed from the middle values of \(3\) and its subsequent doublings, so they are \(3,6,12,24,48,\dots\). In the odd case we have a more interesting situation. Look at the panel for \(N=3\) in the first figure above. We have the presence of the distance of \(2\) along with \(3\). Its doublings lead to another set of levels at powers of \(2\), but they are present only for odd \(N\).

The last figure above shows the sequences for odd \(N\) with the \(x\)-axis truncated to a factor of \(8\) for ease of viewing, which causes the curves for the top 3 \(N\) values to be cut.

Distribution of cycles

Here we will simply plot the binary number versus its bit-reversed value, both in decimal. The figure below shows this mapping for \(N=7\). Notice that logarithmic scaling to the base 2 has been used for both axes. Red dots signify our cycles, also called palindromes. The purple dots are the bit-reversed numbers. There is an immediately noticeable symmetry about the \(y=x\) line.

Another feature that can be observed is that with increasing value, the numbers near the top and right boundary seem to follow a curve. This is more evident in the next figure. We see what looks like a kite with curved edges. What is the equation of this edge? It is an easy matter to verify that for the top sheath it is

\[\begin{align*} & y_k=2^{N-k}x_k \\ \text{for} \quad & x_k=2^k-1, \quad k \leq N. \end{align*}\]

Interchange \(y\) and \(x\) for the equation for the sheath on the right. Thus for the top sheath \(x_k=\{1,3,7,15,31,63,127,\dots\}\). These are binary numbers of the form \(0\dots01\), \(0\dots011\), \(0\dots0111\) and so on. This is understandable if we consider their bit-reversals. To make large binary numbers we need as many ones as possible that multiply the larger powers of \(2\). So we should have \(y_k\)’s like \(10\dots0\), \(110\dots0\), \(1110\dots0\), etc. The points that make up this sheath are related to another interesting pattern that we will discuss later.

A diversion into primes

Any discussion involving natural numbers is inevitably bound to include primes. The table below gives the number of \(N\)-bit primes, i.e., the number of primes present in binary numbers of \(N\) bits. For example, with \(N=4\) we have the range in decimal as \([8,16)\) with the primes being \(11_{10}=1011_2\) and \(13_{10}=1101_2\) which reverse to each other. For \(N=5\) the range is \([16,32)\) and the set of primes is \(\{17,19,23,29,31\}\), which reverses to \(\{17,25,29,23,31\}\), giving us 4 reversals to prime numbers and 2 cyclic primes. All the sequences in the table may be described as follows and are given in the OEIS.

1. Total Primes: Number of \(N\)-bit primes — A374403
2. Rev to Prime: Number of \(N\)-bit primes that reverse to primes — A366910
3. Cyclic Primes: Number of \(N\)-bit primes that reverse to themselves — A117773

We immediately observe a periodic occurrence of zeroes in the sequence of cyclic primes. Barring \(N=2\), there are no cyclic primes for even \(N\).

N	Total Primes	Rev to Prime	Cyclic Primes
1	0	0	0
2	2	1	1
3	2	2	2
4	2	2	0
5	5	4	2
6	7	6	0
7	13	9	3
8	23	14	0
9	43	27	3
10	75	36	0
11	137	69	7
12	255	94	0
13	464	178	12
14	872	308	0
15	1612	589	23
16	3030	908	0
17	5709	1540	40
18	10749	2814	0
19	20390	5158	94
20	38635	9210	0