Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
    
I'm not sure I really get your point ... o.o –  gilaras Nov 18 '11 at 13:31
    
Possible duplicate of Representing circular bitwise shift mathematically. –  Henning Makholm Nov 18 '11 at 17:44
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.