What exactly happens, when I do a bit rotation?

Question

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.

You might want to note that any sort of bit rotation operation operates on the numerals involved, not the numbers. Also, if we consider trinary numbers say with trinary number rotations, then for a rotation of 1110 we can get 1101, 1011, 0111. So, you have 39 for the first number, and 37, 31, and 13 for the 2nd, 3rd, and 4th respectively. — Doug Spoonwood, Nov 18 '11 at 13:21
Possible duplicate of Representing circular bitwise shift mathematically. — hmakholm left over Monica, Nov 18 '11 at 17:44

score 6 · Answer 1 · answered Nov 18 '11 at 13:32

6

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.

answered Nov 18 '11 at 13:32

Dilip Sarwate

25,197

Thank you very much, you just saved my work-free weekend! At least i don't have to lose any sleep over that! :-) – gilaras Nov 18 '11 at 13:36
Also works the other way around, i.e. when you shift to the left, except you have to multiply by 2 mod 15. – Raskolnikov Nov 18 '11 at 13:43
Note: $$ \begin{align} \frac{m}{2}\bmod(2^n-1)&\iff 2k\equiv m \pmod{2^n-1} \ & \iff m \equiv 2k \pmod{2^n-1} \end{align} $$ Since $0\leq m < 2^n-1$: $$ \begin{align} &m = 2k \bmod{(2^n-1)}=2k-(2^n-1)\left\lfloor \frac{2k}{2^n-1}\right\rfloor \ &\left\lfloor \frac{2k}{2^n-1}\right\rfloor=\cases{0 \quad \text{ if }~0\leq k \leq 2^{n-1}-1 \ 1\quad \text{ if }~2^{n-1}\leq k \leq 2^n-1} \end{align} $$ So: $$ 0\leq k \leq 2^{n-1}-1 \implies m=2k \implies k=\frac m 2 \ 2^{n-1}\leq k \leq 2^n-1 \implies m=2k-(2^n-1)\implies k=\frac{m+(2^n-1)}{2} $$ – Vinicius ACP Apr 25 '22 at 04:07
Then, as stated in the answer: $$ \begin{alignat}{1} &~~~~~~~~~m = 2k &\iff& \text{ m is even } &\iff& k=\frac m 2 \ &m = 2k-(2^n-1) &\iff& \text{ m is odd } &\iff& k=\frac{m+(2^n-1)}{2} \end{alignat} $$ – Vinicius ACP Apr 25 '22 at 04:48

score 5 · Accepted Answer · answered Nov 18 '11 at 13:47

5

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)$.

answered Nov 18 '11 at 13:47

Brian M. Scott

616,228

Okay, this confused me even more xD At least on first sight, after reading and thinking through it i guess it made sense (I'm not quite sure, though...) :P Thanks for your answer :-) – gilaras Nov 18 '11 at 13:52
@gilaras: The first expression in $(1)$ subtracts the leading bit $-$ that’s what’s going on inside the parentheses $-$ and then doubles the result to shift everything one place to the left, and finally adds the leading bit back in at the low-order end. The first expression in $(2)$ does a non-circular right shift by dividing by $2$ and ignoring any remainder and then adds the old low-order bit at the top end. – Brian M. Scott Nov 18 '11 at 14:22
Thanks for explaining this to me :-) I think i finally got it :-) – gilaras Nov 18 '11 at 14:40
Note: for circular right shift, $$ \left\lfloor \frac{m}{2}\right\rfloor= \cases{m/2 &\text{ if m is even} \ (m-1)/2 &\text{ if m is odd }} $$ So, in agreement with Dilip's answer:
$$ \begin{alignat}{1} &\text{m is even} &\iff&~~~~~~~k = \frac m 2 + 2^{n-1} \left(m - 2\frac m 2 \right) &\iff& k= \frac m 2 \ &\text{m is odd} &\iff& k = \frac{m-1}{2} + 2^{n-1} \left(m - 2\frac{m-1}{2} \right) &\iff& k= \frac {m+(2^n-1)} {2} \end{alignat} $$
– Vinicius ACP Apr 25 '22 at 04:43

score 1 · Answer 3 · edited Apr 25 '22 at 05:52

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!

I think it must be $Left(x,s,b)\equiv(x\cdot2^s)\bmod(2^b-1)$. The one ("1") in the exponent seems to be wrong. Do you have an idea how to calculate the needed left-rotations that are required to rotate the minimum binary to its maximum? (During rotating a binary there obvious exist a maximum and a minimum, e.g. $1100$ vs. $0011$ - which is a simple example) — , Dec 21 '20 at 11:09
@EldarSultanow Mathematically or programmatically? I'm guessing its programmatically you mean? if so, just remove the leading bits and fill the bits to the end of your required bytes value. no need to rotate then... — Hades, Dec 22 '20 at 14:15
...mathematically: it's a bit more - I formulated the question more precisely here: https://math.stackexchange.com/questions/3957643/rotating-circular-shifting-a-binary-number-what-is-the-rotational-distance-b?noredirect=1#comment8161564_3957643 It would be great if you have an idea. Best, Eldar — , Dec 22 '20 at 14:48

What exactly happens, when I do a bit rotation?

3 Answers3

Linked