K&R 2-8 rightrotate (length of integer in bits)

Question

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

I can't see how i can get the bits and put them in the right position without requiring the length of x(the amount of bits).

Am I thinking wrong or do i really need to get the length of x somehow? If so, how would I go about getting this length of x?

The code below is wrong probaply by the way, I just put length_x in to demonstrate my problem.
I hope someone can point me in the right direction.

#include <stdio.h>

unsigned rightrot(unsigned x, int n);

main()
{
    unsigned x = 75;
    int p, n, y;
    p = 5;
    n = 3;
    y = 45;

    printf("%u\n",rightrot(x,n));
}



unsigned rightrot(unsigned x, int n)
{

    oldn = (x & ~(~0 << n)) << length_x;

    x = x >> n | oldn;
    return x;

}

Answer 1

Try:

unsigned int rrot(unsigned int x, int n) {
     int len;
     for (len=31;len>=0 && !((1 << len) & x);len--);
     len++;

     return ((x >> n) | (x << (len - n)) & ((1 << len) - 1);
}

The for loop should find the length in bits of x. It iterates along the bits of n, checking if the bit is high; if so, that is the length of the number.

Note: no checks are made that len is greater than n.

Answer 2

Since it looks like this might be a homework question, let me just give you a hint instead of the complete answer.

Yes, you can do it without explicitly using the size of the variable. You can do rightrot(x,n) by executing rightrot(x,1) n times. Now how do you do rightrot(x,1) without the variable size? There are only two possibilities of the rightmost bit of x: 0 and 1. You can deal with them separately.

Answer 3

int nlz(unsigned x);
// 75 : 1001011 -> 3 bit shift right -> 57 : 111001
unsigned rightrot(unsigned x, int n){
    int length_x = 32 - nlz(x);//32 : unsigned int is assumed to be a 32-bit
    unsigned mask = (1 << length_x) - 1;

    return (x >> n) | mask & (x << (length_x - n));

}

//count zero bit from left
int nlz(unsigned x) {
    int y, m, n;

    y = - (x >> 16);
    m = (y >> 16) & 16;
    n = 16 - m;
    x = x >> m;

    y = x - 0x100;
    m = (y >> 16) & 8;
    n = n + m;
    x = x << m;

    y = x - 0x1000;
    m = (y >> 16) & 4;
    n = n + m;
    x = x  << m;

    y = x - 0x4000;
    m = (y >> 16) & 2;
    n = n + m;
    x = x  << m;

    y = x >> 14;
    m = y & ~(y >> 1);
    return n + 2 - m;
}

Answer 4

unsigned rightRot(unsigned x, int n){
    unsigned msb_1=~(~(unsigned)0 >> 1);

    for(int i=0; i<n; i++){
        if(x&1) {x=(x >>1)|msb_1;}
        else {x=x>>1;}
    }

    return x;
}//problem K&R