Rotating (circular shifting) a binary number - what is the rotational distance between the minimum and maximum?

Question

I started continuing thoughts from What exactly happens, when I do a bit rotation?. Let us take a binary number $B$ of length $L$ with $N$ ones, for example $L=8$, $N=5$ and $B=10110101=181$, the minimum (obtainable by rotating $B$) is $B_{min}=01011011=91$ and the maximum is $B_{max}=11011010=218$. The (left-)rotational distance $d(B_{min},L)=r$ is the required amount of left rotates from the minimum to the maximum. In this example $d(B_{min},L)=r=3$, since we obtain the maximum $11011010$ by three left rotates ($r=3$) of the minimum $01011011$.

What is the general formula of calculating the rotational distance $d(B_{min},L)$?

What we know so far is that $B_{max}=(B_{min}\cdot2^r)\bmod{(2^L-1)}$ which means in our example $218=(91\cdot2^3)\bmod(255)$ and thus $r$ might be obtained by the discrete logarithm, which is not so manageable.

Hopefully there is way to calculate $r$ explicitely (avoiding trial-&-error).

Maybe we can show that $L\mid N\cdot r+1$

Answer 1

In order that the divisibility $L\mid N\cdot r+1$ is given, we must show that:

• $\gcd(B_{min},2^L-1)\mid B_{max}$
• $2^L-1\mid2^rB_{min}-B_{max}$

which leads us to the diophantine equation that must have an integer solution $a,b$:

$(2^L-1)\cdot b=2^{\frac{a\cdot L-1}{N}}\cdot B_{min}-B_{max}$

In our example $a=b=2$ provide a solution: $(2^8-1)\cdot b=2^{\frac{a\cdot 8-1}{5}}\cdot91-218$.