I'm sitting in my office and having difficulties to get to know that exactly happens, when I do a bit rotation of a binary number.
An example: I have the binary number 1110. By doing bit rotation, I get 1101, 1011, 0111 ... so I have 14 and get 7, 11, 13 and 14 again.
I can't get a rule out of it... can somebody help me?
Excuse my bad English, I'm just so excited about this problem.
$\endgroup$ 33 Answers
$\begingroup$Interpret the bits as representing a number in standard binary representation (as you are doing). Then, bit rotation to the right is division by $2$ modulo $15$, or more generally, modulo $2^n-1$ where $n$ is the number of bits. Put more simply, if the number is even, divide it by $2$, while if it is odd, add $15$ and then divide by $2$. So from $14$ you get $7$. Since $7$ is odd, add $15$ to get $22$ and diivide by $2$ to get $11$. Add $15$ and divide by $2$ to get $13$ and so on.
The calculations are somewhat different if the bits are interpreted in $2$s-complement representation.
$\endgroup$ 4 $\begingroup$If you have an $n$-bit binary number $m$, possibly with leading zeroes, a circular left shift gives you $$2\left(m-2^{n-1}\left\lfloor \frac{m}{2^{n-1}}\right\rfloor\right)+\left\lfloor \frac{m}{2^{n-1}}\right\rfloor=2m-(2^n-1)\left\lfloor\frac{m}{2^{n-1}}\right\rfloor,\tag{1}$$ and a circular right shift gives you $$\left\lfloor\frac{m}2\right\rfloor+2^{n-1}\left(m-2\left\lfloor\frac{m}2\right\rfloor\right)=2^{n-1}m-(2^n-1)\left\lfloor\frac{m}2\right\rfloor.\tag{2}$$
Changing the base from $2$ to $b$ merely requires changing $2$ to $b$ everywhere in $(1)$ and $(2)$.
$\endgroup$ 4 $\begingroup$For reasons that are irrelevant, I was looking for the arithmetic or mathematical equivalance of a bitwise rotation. Scavaging the internet, not much can be found. Even this post here is quite rare.
After looking at the difference answers, they didn't provide an adequate solution, but some of the answers here provided a nice starting point.
So I tried to make the most simplistic mathematical equation or representation for bitwise rotation (left and right) and here is what I came up with:
Left Rotation:
$ \normalsize{ \operatorname{Left}~\!(x,s,b)\equiv(x\cdot2^{s})~\bmod(2^{b}-1) } $
Example:
x = 5 (value) -> 0000 0101
s = 7 (steps or rotations)
b = 8 (bits)
$ \normalsize{ \operatorname{Left}~\!(5,7,8)\equiv(5\cdot2^{7})~\bmod(2^{8}-1)=130 } $
result = 130 -> 1000 0010
What is happening?
Well moving the bits 1 position to the left in a radix 2 or binary is the same as multiplying by $2^1$.
Moving 7 position is the equivalence of multiplying by $2^7$
To make sure that the movement actually rotates within a certain amount of bits we are taking the remainder of the outcome based on the amounts of bits.
Right Rotation:
$ \normalsize{ \operatorname{Right}~\!(x,s,b)=\operatorname{Left}~\!(x,b-(s~\bmod b),b) } $
First I wanted to make right rotation equation independent from the left rotation, but that would've made the equation much more complex. (because if the rotation surpasses the range or bits-container, it's much harder to redefine it.)
The left rotation equation is very simple, as it just multiplies the value and if the value is bigger than the 'mask', 'container' or better said value of $2^{b}-1$, it will take the remainder of it and thus our wanted result.
And if we rotate 1 position to the right in 8 bits, it is the same as rotating 7 times to the left. Hence we can use the Left rotation equation with a modified step argument or variable.
To make sure we have the correct amount of steps in case that steps or rotations is bigger than our bits. We take the remainder of it:
$ \normalsize{ b - (s ~\bmod b) } $
As this is isn't quite a popular thing, because if you would program it, you could simply use bitwise operations, but from a mathematical standpoint it is an interesting thing and thus why I decided to answer this ca. 9 year old question.
I hope you like it!
$\endgroup$ 3
