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
    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.2011-11-18
  • 0
    I'm not sure I really get your point ... o.o2011-11-18
  • 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
    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 :-)2011-11-18
  • 0
    @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.2011-11-18
  • 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
    Thank you very much, you just saved my work-free weekend! At least i don't have to lose any sleep over that! :-)2011-11-18
  • 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