9

I'm working through the exercises in the K&R book. Currently I'm stuck at exercise 2-8, which is says the following:

Write a function rightrot(x, n) that returns the value of the integer x rotated to the right by n bit positions.

The trouble I have is that I cannot seem to picture what the result SHOULD look like.

How or what do I rotate? Do I take the leftmost bit and put it to the rightmost position of x, after x is shifted to the left and repeat this for n bits? Or do I take a chunk (n bits) and put it n bits to the right while leaving the rest of the rightmost bits unchanged?

Any helpful answer is appreciated. Thanks.

Miroslav Cetojevic
  • 701
  • 1
  • 5
  • 14
  • 2
    You can do both:) That can be a good exercise. – zw324 Jul 09 '11 at 21:30
  • 1
    Yes well, I think so, too. But in this case I want to understand the exact implication of this exercise. – Miroslav Cetojevic Jul 09 '11 at 21:36
  • Do all options. It is an exercise after all :) I think the wanted behaviour is to make the binary digits less significant and move the least significant ones to the most significant positions: with 8 bit unsigned integers `"00000011"` rotated 2 would become `"11000000"`. Beware of the sign bit! – pmg Jul 09 '11 at 21:43
  • I didn't start with K&R, and On my entire life I did this with a preprocessor macro and some bitwise operations. Then when I first bought my original book and saw this exercise, I keep wondering if a function is really needed in this case. – sidyll Jul 10 '11 at 00:38
  • I'm going by the book for learning purposes ;-) – Miroslav Cetojevic Jul 10 '11 at 07:21

2 Answers2

8

Rotating means you're essentially shifting to the left or right but the bits otherwise "lost" will reappear on the other side.

It's a lot easier to explain with a decimal number:

Rotate 123456789 to the right by 3 digits will result in 789123456. Rotate 123456789 to the left by 4 digits will result in 567891234.

So you'll essentially take n bits from one side and attach them to the others. It's a lot easier to understand if you think of all digits sitting on a circle or wheel you're rotating around the center.

To avoid confusin just replace "rotate" with "move" or "shift" and don't forget to save the bits otherwise lost.

Mario
  • 35,726
  • 5
  • 62
  • 78
  • A bit late, but thanks for the idea. I managed to implement a version in the spirit of your answer. Unfortunately, I can't post it here as I'm missing the source (hard drive went limb, waiting for the fix). – Miroslav Cetojevic Aug 10 '11 at 14:50
2

Right idea but the other way.

Get rightmost bit. Shift right. Set the leftmost bit. Do this n times.

QuentinUK
  • 2,997
  • 21
  • 20