I've been struggling through the reasoning behind the generalization of Josephus problem and got confused on the very last step. Then I searched online but seems that this problem is not that well-discussed. I've totally get the one block transformation, but can't really understand how it works in multiple case.
So, according to the explanation below (multiple block transformation), where does the binary shift come from as we definitely do not shift $b_{m}$?
It seems to me, that we have the second binary block and we do circular shift from there, can anyone clarify how this logic works?
Let $i_1, ..., i_k$ be the indices of $1$ bits in the binary representation of $n$, where the least significant bit is at position $1$, the second least significant bit is at position $2$ and so on (observe that $n$ is uniquely defined this way). Furthermore, let $i'_1, ..., i'_k$ be the indices of $1$ bits of $f(n)$. Since we know that upon $f$, each block of $(1, 0, ..., 0)$ in $n$ gets transformed into $(1, -1, ..., -1)$, which is essentially $(0, ..., 0, 1)$, we get the following:
\begin{align} i'_k &= i_{k-1} + 1\\ i'_{k-1} &= i_{k-2} + 1\\ &\;\;\vdots \notag \\ i'_1 &= 1 \end{align}
However, the transformation defined by the equation above is exactly what the circular binary shift does - it 'extracts' the most significant $1$ bit, increments the positions of all remaining $1$ bits by a value of $1$ and finally sets the extracted bit at the rightmost position of $1$.