1

today, I have been trying to write a function, which should rotate a given 64 bit integer n bits to the right, but also to the left, if the n is negative. Of course, bits out of the integer shall be rotated in on the other side.

I have kept the function quite simple.

void rotate(uint64_t *i, int n) 
  uint64_t one = 1;
  if(n > 0) {
      do {
           int storeBit = *i & one;
           *i = *i >> 1;
           if(storeBit == 1)
              *i |= 0x80000000000000;
           n--;
          }while(n>0);
   }
 }

possible inputs are:

uint64_t num = 0x2;
rotate(&num, 1); // num should be 0x1
rotate(&num, -1); // num should be 0x2, again
rotate(&num, 62); // num should 0x8

Unfortunately, I could not figure it out. I was hoping someone could help me.

EDIT: Now, the code is online. Sry, it took a while. I had some difficulties with the editor. But I just did it for the rotation to the right. The rotation to the left is missing, because I did not do it.

  • 1
    Is there any code inside the `rotate()` function somewhere else? A function declaration does not actually mean something will happen unless it's implemented somewhere. – jonhopkins Nov 07 '13 at 16:19
  • @glglgl: Well, I considered the 64 bit integer as one number. So, I shifted it one by one, e.g. to the right, until n was downsized to zero. Everytime, I stored the value of the bit, which was rotated out and I rotated that bit in on the other side. –  Nov 07 '13 at 16:24
  • 2
    @user2965601, that sounds exactly like what you should be doing. Can you edit your question to show what you have so far, and what the incorrect output looks like? – jonhopkins Nov 07 '13 at 16:25
  • @jonhopkins: No, the code should be in rotate and then I call it in the main function. –  Nov 07 '13 at 16:25
  • 1
    @user2965601 we really need to see the code in `rotate` in order to help and pointing out what parts are not clear would help as well. Preferably an [SSCCE](http://sscce.org/), i.e. with headers, main etc... – Shafik Yaghmour Nov 07 '13 at 16:27
  • 1
    @user2965601 In order to help you find out what you failed on, we need your code. Your code of `rotate()`. The one that doesn't work. – glglgl Nov 07 '13 at 16:27
  • @user2965601, by "somewhere else", I was just referring to the fact that you only showed us a function declaration, ie `void rotate(uint64_t *i, int n);`. So I was assuming you have the actual implementation, `void rotate(uint64_t *i, int n) { // your code }` somewhere else in your file. – jonhopkins Nov 07 '13 at 16:28
  • We cannot help you with code we cannot see. Please include your copy of the `rotate` function. – Raymond Chen Nov 07 '13 at 16:30
  • The code is online. Sry, it took a while, but I had some difficulties with the code editor. –  Nov 07 '13 at 16:40
  • http://stackoverflow.com/questions/3323633/efficient-way-of-doing-64-bit-rotate-using-32-bit-values – Exceptyon Nov 07 '13 at 16:41
  • @user2965601, your number to put the bit back at the top, `0x80000000000000`, looks a bit short. I'm pretty sure if you add two more 0s to the end of it, it should start working correctly. – jonhopkins Nov 07 '13 at 16:45
  • `if (x) { do { ...} while (x); }` would better be written as `while (x) { ... }`. – glglgl Nov 08 '13 at 07:55

3 Answers3

2
uint64_t rotate(uint64_t v, int n) {
    n = n & 63U;
    if (n)
        v = (v >> n) | (v << (64-n));
    return v; }

gcc -O3 produces:

.cfi_startproc
andl    $63, %esi
movq    %rdi, %rdx
movq    %rdi, %rax
movl    %esi, %ecx
rorq    %cl, %rdx
testl   %esi, %esi
cmovne  %rdx, %rax
ret
.cfi_endproc

not perfect, but reasonable.

Chris Dodd
  • 119,907
  • 13
  • 134
  • 226
1
int storeBit = *i & one;

@This line you are assigning an 64 bit unsigned integer to probably 4 byte integer. I think your problem is related to this. In little endian machines things will be complicated if you do, non-defined operations.

cycrel
  • 97
  • 2
  • 10
  • You are right. This was not very clever of me. I will take care of this. Thank you. –  Nov 07 '13 at 16:54
  • I think if you use a compiler with generating warnings to these kind of errors, would be helpful to you. – cycrel Nov 07 '13 at 16:56
0
if(n > 0)

doesnt takes negative n

Luka Rahne
  • 10,336
  • 3
  • 34
  • 56
  • The last line of the question: "The rotation to the left is missing, because I did not do it." – jonhopkins Nov 07 '13 at 16:57
  • If I get a negative n, I just make it positive and then I start the rotation to the left. But the code for the negative n is missing anyway, because I haven't done it yet. –  Nov 07 '13 at 16:57