CODEWITHSUNDEEP
cbit-manipulation
Brandon
Brandon

Reputation: 123

Bit Rotation in C

The Problem: Exercise 2-8 of The C Programming Language, "Write a function rightrot(x,n) that returns the value of the integer x, rotated to the right by n positions."

I have done this every way that I know how. Here is the issue that I am having. Take a given number for this exercise, say 29, and rotate it right one position.
11101 and it becomes 11110 or 30. Let's say for the sake of argument that the system we are working on has an unsigned integer type size of 32 bits. Let's further say that we have the number 29 stored in an unsigned integer variable. In memory the number will have 27 zeros ahead of it. So when we rotate 29 right one using one of several algorithms mine is posted below, we get the number 2147483662. This is obviously not the desired result.

unsigned int rightrot(unsigned x, int n) {
    return (x >> n) | (x << (sizeof(x) * CHAR_BIT) - n);
}

Technically, this is correct, but I was thinking that the 27 zeros that are in front of 11101 were insignificant. I have also tried a couple of other solutions:

int wordsize(void) {    // compute the wordsize on a given machine...
    unsigned x = ~0;
    int b;
    for(b = 0; x; b++)
        x &= x-1;
    return x;
}

unsigned int rightrot(unsigned x, int n) {
    unsigned rbit;
    while(n --) {
        rbit = x >> 1;
        x |= (rbit << wordsize() - 1);
    }
    return x;

This last and final solution is the one where I thought that I had it, I will explain where it failed once I get to the end. I am sure that you will see my mistake...

int bitcount(unsigned x) {
    int b;
    for(b = 0; x; b++)
        x &= x-1;
    return b;
}

unsigned int rightrot(unsigned x, int n) {
    unsigned rbit;
    int shift = bitcount(x);
    while(n--) {
        rbit = x & 1;
        x >>= 1;
        x |= (rbit << shift);
    }
}

This solution gives the expected answer of 30 that I was looking for, but if you use a number for x like oh say 31 (11111), then there are issues, specifically the outcome is 47, using one for n. I did not think of this earlier, but if a number like 8 (1000) is used then mayhem. There is only one set bit in 8, so the shift is most certainly going to be wrong. My theory at this point is that the first two solutions are correct (mostly) and I am just missing something...

Upvotes: 7

Views: 10969

Answers (4)

momotaro
momotaro

Reputation: 145

In my opinion, the spirit of the section of the book which immediately precedes this exercise would have the reader do this problem without knowing anything about the size (in bits) of integers, or any other type. The examples in the section do not require that information; I don't believe the exercises should either.

Regardless of my belief, the book had not yet introduced the sizeof operator by section 2.9, so the only way to figure the size of a type is to count the bits "by hand".

But we don't need to bother with all that. We can do bit rotation in n steps, regardless of how many bits there are in the data type, by rotating one bit at a time.

Using only the parts of the language that are covered by the book up to section 2.9, here's my implementation (with integer parameters, returning an integer, as specified by the exercise): Loop n times, x >> 1 each iteration; if the old low bit of x was 1, set the new high bit.

int rightrot(int x, int n) {
    int lowbit;

    while (n-- > 0) {
        lowbit = x & 1;            /* save low bit */
        x = (x >> 1) & (~0u >> 1); /* shift right by one, and clear the high bit (in case of sign extension) */
        if (lowbit)
            x = x | ~(~0u >> 1);   /* set the high bit if the low bit was set */
    }

    return x;
}

Upvotes: 4

shivani jain
shivani jain

Reputation: 1

int bitcount(unsigned x) {
    int b;
    for(b = 0; x; b++)
        x &= x-1;
    return b;
}

unsigned rightrot(unsigned x,int n) {
   int b = bitcount(x);
   unsigned a = (x&~(~0<<n))<<(b-n+1);
   x>> = n;
   x| = a;
}

Upvotes: 0

user149341
user149341

Reputation:

A bitwise rotation is always necessarily within an integer of a given width. In this case, as you're assuming a 32-bit integer, 2147483662 (0b10000000000000000000000000001110) is indeed the correct answer; you aren't doing anything wrong!

0b11110 would not be considered the correct result by any reasonable definition, as continuing to rotate it right using the same definition would never give you back the original input. (Consider that another right rotation would give 0b1111, and continuing to rotate that would have no effect.)

Upvotes: 8

user191776
user191776

Reputation:

You could find the location of the first '1' in the 32-bit value using binary search. Then note the bit in the LSB location, right shift the value by the required number of places, and put the LSB bit in the location of the first '1'.

Upvotes: 0

Related Questions