im trying to write a code to rotate a unsigend int by number of bit (without knowing how many bits is unsigend int) i write this code -

unsigned int left_rottate(unsigned int a, int b){
    int temp;
    int bits_size = size_in_bits()-1;
    b %= bits_size;

    while(b > 0){
        temp = (a>> bits_size)&1;
        a = (a <<1) | temp;
        b--;
    }
    return a;
}
 int size_in_bits()
{
    unsigned int x,
     i = 0;

  x = ~0u;
  while ((x & 1) != 0)
    (i = 1, x /= 2);
  return (int) i; 
}

but i dont get the rigth results.

CodePudding user response：

by using 2's complement systems you can do this. so -1 is 0xffffffff (32bit 4byte) 0xffffffffffffffff (64bit 8byte) and so on. so,

int t = -1; // 0xffff  1111_1111_1111_1111
t = t >> 1; // 0x7fff  0111_1111_1111_1111
t = t 1; // 0x8000     1000_0000_0000_0000

by doing this you have the leftmost mask with you.

11111111111111111011111111110111
^                              ^
left                           right

Algorithm:

1. left the leftmost bit using this mask.
2. left shift your number
3. set the bit at 0'th place.

CodePudding user response：

im trying to write a code to rotate a unsigend int by number of bit (without knowing how many bits is unsigend int)

Ok. Your size_in_bits() function is one viable way to determine the number of value bits in an unsigned int, which is what you need. In principle (but not in practice) it is in fact more reliable than the CHAR_BIT * sizeof(unsigned int) approach suggested to you in comments, because C allows that the representation of unsigned int might include one or more padding bits. In an implementation where unsigned int had padding bits, the total number of bits in the representation of unsigned int, given by CHAR_BIT * sizeof(unsigned int), would be strictly greater than then number of value bits.

More briefly, size_in_bits() is not wrong, though it's enormously more expensive than CHAR_BIT * sizeof(unsigned int), which is completely standard and gives the right answer for any implementation you're likely to be using.

So why are you getting incorrect answers? Presumably, because this doesn't make any sense:

    int bits_size = size_in_bits()-1;
    b %= bits_size;

It would make sense to reduce b modulo the size of unsigned int, but that's not what you are doing. You're reducing modulo the size - 1, which is not useful when b is initially equal to or greater than the size_in_bits(). As a concrete example, if the unsigned int size were 32 bits, and a 32-bit rotation were requested, then that would reduce b to 1, whereas if you want to perform such a reduction than the correct reduced rotation would be 0.

Additionally, when b is negative, b %= bits_size will be <= 0. This follows from the definition of the modulus operation:

When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. If the quotient a/b is representable, the expression (a/b)*b a%b shall equal a

(C17 6.5.5/6)

Because of that and the while(b > 0) loop condition, your function will handle all negative b arguments as if they were 0.

Here is a variation on your left_rottate() [sic] function that should do better:

unsigned int left_rottate(unsigned int a, int b){
    static unsigned int bits_size = 0;

    if (bits_size == 0) {
        // compute this once for all
        bits_size = size_in_bits();
    }

    b %= bits_size;

    if (b < 0) {
        // Be sure to choose the non-negative modulus
        b  = bits_size;
    }

    while (b > 0) {
        a = (a >> (bits_size - 1)) | (a << 1);
        b--;
    }
    return a;
}

But I note that once you reduce b to the range [0, bits_size), it is wasteful to perform the rotation one bit at a time. You could easily do it all at once, instead:

    // ...

    if (b != 0) {
        a = (a >> (bits_size - b)) | (a << b);
    }
    return a;
}

CodePudding user response：

If you really need to account for (b < 0) in this case:

#include <limits.h>

unsigned int rol (unsigned int a, int b)
{
    int k = sizeof(int) * CHAR_BIT;

    if (b < 0)
        a = a << ((- b) % k) | a >> ((  b) % k);
    else
        a = a << ((  b) % k) | a >> ((- b) % k);

    return a;
}

With optimizations on, (k) will be evaluated at compile time, and as a power of (2) on any modern platform. The compiler might also recognise these operations as rotate instructions if available. gcc-12 (x86-64) gives me:

    movl    %esi,