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;

}

Are you sure you understood the [**purpose of the exercise?**](http://stackoverflow.com/questions/6637578/kr-understanding-exercise-2-8-exactly-what-is-asked-here) — frsfnrrg, Aug 07 '13 at 19:20

frsfnrrg · Accepted Answer · 2013-08-07T19:33:34.603

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.

edited Aug 07 '13 at 19:33

answered Aug 07 '13 at 19:00

frsfnrrg

136
5

With length I mean the length of the contents of x. – bryanph Aug 07 '13 at 19:08
@bryanph What precisely do you mean with the contents? The length of the type of x (unsigned int), 32 bits? The least number of bits needed to represent the unsigned number?, so for 15, 4, for 128, 8, for 1023, 10? – frsfnrrg Aug 07 '13 at 19:13
Following the variable examples I have in my code: The result of your code would be 1001011 rotated 3 to the right becomes 1100000000000000000000000001001. So this indeed puts the rightmost 3 bits at the leftmost part of the integer. What I am looking for is to get a result of 111001, having the same effect but putting the rightmost bits immediately at the left of the leftmost bits that are shifted right. This is kind of a confusing explanation but I hope you understand what I mean. – bryanph Aug 07 '13 at 19:23

Benawii · Answer 2 · 2013-08-07T19:56:48.667

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.

score 0 · Answer 3 · answered Aug 08 '13 at 11:08

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;
}

score 0 · Answer 4 · edited Mar 16 '14 at 15:02

0

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

edited Mar 16 '14 at 15:02

Kevin Brechbühl

4,717
3
24
47

answered Mar 16 '14 at 14:41

Qamar Alam

1

Could you explain why the cast is necessary in `msb_1`? – pdoherty926 Feb 14 '17 at 17:55

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

4 Answers4