bit rotate on unsigned int in c

Question

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.

Answer 1

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

unsigned int t = -1; // 0xffff  1111_1111_1111_1111 using forced conversion in 2's complement.
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.

Answer 2

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

Answer 3

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, %ecx
    movl    %edi, %eax
    rorl    %cl, %eax
    roll    %cl, %edi
    testl   %esi, %esi
    cmovns  %edi, %eax
    ret

clang-15 doesn't recognise the pattern. However, if we make the 'power of (2)' assumption, and replace: % k with: & (k - 1), clang makes the deduction, generating more-or-less identical code.

Answer 4

In order to get the number of bits in an unsigned int, you can use the following algorithm (simple and capable to get the number of 1s in an unsignded of unknown size --- upto a limit that can be large, as the number of operations is low)

unsigned long count_ones(unsigned long n)
{
    /* assume numbers will not be larger than 128bits */
    n = (n & 0xaaaaaaaaaaaaaaaaUL) >>  1) + (n & 0x5555555555555555UL);
    n = (n & 0xccccccccccccccccUL) >>  2) + (n & 0x3333333333333333UL);
    n = (n & 0xf0f0f0f0f0f0f0f0UL) >>  4) + (n & 0x0f0f0f0f0f0f0f0fUL);
    n = (n & 0xff00ff00ff00ff00UL) >>  8) + (n & 0x00ff00ff00ff00ffUL);
    n = (n & 0xffff0000ffff0000UL) >> 16) + (n & 0x0000ffff0000ffffUL);
    n = (n & 0xffffffff00000000UL) >> 32) + (n & 0x00000000ffffffffUL);
    return n;
}

you can get the number of bits of any unsigned integer by calling the above function as:

     unsigned nbits = count_ones((the_unsigned_type_you_want_to_measure) ~0UL);

I suggest you to cache the value as suggested in John Bollinger's answer, as the statements above don't need to be called twice, but it is very efficient code (it translates into a small list of machine instructions with no loops, very efficient)

Once you have the number of bits to rotate (and the number of bits to complete a full rotation) I recommend you to this code:

unsigned long rotate_bits(unsigned long n, unsigned bits_to_rotate)
{
    static int nbits = 0;
    if (nbits == 0) {
        /* the static nature of nbits makes to call only once to the function below */
        nbits = count_ones((unsigned long) ~0UL);
    }
    bits_to_rotate %= totalbits;  /* so we don't overflow */
    return (n << bits_to_rotate) | (n >> (nbits - bits_to_rotate));
}