2
$\begingroup$

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.

  • 0
    Possible duplicate of [Representing circular bitwise shift mathematically](http://math.stackexchange.com/questions/82418/representing-circular-bitwise-shift-mathematically).2011-11-18

2 Answers 2

3

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

  • 0
    Thanks for explaining this to me :-) I think i finally got it :-)2011-11-18
3

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.

  • 0
    Also works the other way around, i.e. when you shift to the left, except you have to multiply by 2 mod 15.2011-11-18