Why does the following formula cycle the bits by shifting the binary representation from left to right?

Question

Intuitively, I was trying to come up with a formula that would cycle through the binary representation of numbers from left to right.

Let our range of numbers goes from $0, .., N-1$ and let $m$ denote the number of bits we are going to use.

Then I was told the following would work:

if $i$ is in the range $0 \leq i \leq \frac{N}{2} - 1$, then:

$$j = 2i$$

But if $i$ is in the range$\frac{N}{2} \leq i \leq N -1 $, then:

$$j = 2i+1 -N$$

Apparently, this cyclically shifts the bits in the following way (for an example of m =3):

$000 \rightarrow 000, 001 \rightarrow 100, 010 \rightarrow 001, 011 \rightarrow 101, 100 \rightarrow 010$ etc...

There are two things that bother me. First, doubling a number only shifts the bits to the left by 1. So at least for the case $0 \leq i \leq \frac{N}{2} - 1$, its definitively not shifting it the intended direction.

Second, I have no idea how the second equation relates to shifting in any direction. Does anyone see how it shifts? I see that the times 2 shifts left by one but how does the rest ensure it cyclically shift the bits in any direction?

---

As a side note, I am having a hard time finding the correct tag for this question. Feel free to add the best tag if you think others are better. :)

Answer 1

Hint:

Consider a range $N = 10^6$.

• Why $j = 10 i$ for $i < N/10$ shifts the numbers one position left, e.g. for $$i = 012345_\mathrm{dec}\ \text{ we get }\ j = 123450_\mathrm{dec}?$$
• Why $j = 10 i + \lfloor 10i/N \rfloor(1 - N)$ for $i \geq N/10$ shifts the numbers one position left, e.g. for $$i = 654321_\mathrm{dec}\ \text{we get}\ j = 6543210 + 6\cdot(1 - 10^6) = 543216_\mathrm{dec}?$$

I hope this helps $\ddot\smile$