CODEWITHSUNDEEP
c++
David Salvador
David Salvador

Reputation: 23

Bit Rotation Function

I'm taking an online class that calls to create a function called Rotation that will take an object and rotate it count amount of bits. This is the code I currently have

unsigned Rotate(unsigned object, int count)
{  
   /*Initialize number of bits*/
   int numOfBits = CountBits(); 

   if (count < 0)
   {
      /*Negate count if it was a negative value*/
      count = -count;

      return (object << count) | (object >> (numOfBits - count));
   }
   else
      return (object >> count) | (object << (numOfBits - count));
}

the code for CountBits is:

const int SHIFT_COUNT = 1;  //Set bit shift count to 1

    int CountBits()
    {
       unsigned int uiValue = 1;  //Initial value to shift bits
       int bitCount;              //Variable to store the bit count

       /*Left-shift one bit at a time until the value equals zero*/
       for (bitCount = 0; uiValue != 0; bitCount++)
          uiValue <<= SHIFT_COUNT;

       return bitCount;
    }

I believe that my code is working correctly for the first two tests where it rotates by 1 and -1. However, when (numOfBits - count) is either negative or larger than the width of object, I'm being flagged for shifting violation error:

32-bit object shifted (>>) by 3217 bits

Object shifted (<<) by -3185 bits

Is there a particular way these types of shifts should be handled in my above code?

Upvotes: 2

Views: 237

Answers (2)

Toby Speight
Toby Speight

Reputation: 30876

Bit shifts of more than an object's size are Undefined Behaviour. A conforming program shall not invoke Undefined Behaviour.

However, we know that when we rotate by the object's size, we end up with the original object, so we just need to shift by the residue of count modulo the object size:

#include <limits.h>

unsigned Rotate(unsigned object, int count)
{
    static const int max_bits = sizeof object * CHAR_BIT;

    count %= max_bits;
    if (!count)
        /* avoid undefined shift right */
        return object;
    if (count < 0)
        /* force a positive quotient */
        count += max_bits;

    return (object << count) | (object >> (max_bits - count));
}

int main()
{
    unsigned u = 0xFF00;
    unsigned v = Rotate(u, 260); /* 256 + 4 */
    return v != 0xFF000;
}

Upvotes: 0

Serge Ballesta
Serge Ballesta

Reputation: 149075

You are not supposed to shift more than the size of the object. That means you should wrap the passed number in the limits ] -numOfBits; numOfBits [, because rotating +numOfBits of -numOfBits is just a no-op.

Code could become:

unsigned Rotate(unsigned object, int count)
{  
   /*Initialize number of bits*/
   int numOfBits = CountBits(); 

   count %= numOfBits;

   if (count < 0)
       ...

Upvotes: 2

Related Questions