Fundamental C  Shifts And Rotates 
Written by Harry Fairhead  
Monday, 18 March 2019  
Page 2 of 2
Normalizing MasksTypically shifts can be useful when you are normalizing values after having extracted bits using a mask. For example consider the problem of separating out the RGB values given earlier: int RGBcolor=0x010203; int B=RGBcolor & 0x0000FF; int G=RGBcolor & 0x00FF00; int R=RGBcolor & 0xFF0000; G>>=8; R=(unsigned)R>>16; int data=1; data<<= 1; Now R is 1, G is 2 and B is 3, as required. Notice that we can shift G without worrying about the sign bit because it has to be 0. When we shift R then we have to use a logical shift to stop it being interpreted as a negative value. Of course, you can combine the operations into a single expression: int RGBcolor=0x010203; int B=RGBcolor & 0x0000FF; int G=(RGBcolor & 0x00FF00)>>8; int R=((unsigned)RGBcolor & 0xFF0000) >>16; Because the shift operator has a higher priority than logical &, the brackets are needed. RotateThere is another form of shift – the left or right rotate – and while most processors have an instruction that will perform this type of shift in a single operation, for reasons of history C doesn’t have a rotate operator. A right rotate shifts all of the bits to the right and uses the least significant bit that is shifted out as the new most significant. That is, the loworder bit is shifted into the highorder bit. You can see that this is rotation of the bits. Similarly a left rotate shifts all of the bits left and moves the highorder bit to become the new loworder bit. Again you can see that this rotates the bits in the other direction. Rotations don’t correspond to simple multiplication or division and they aren’t useful in the same way as left and right shifts are in isolating bits. What they are used for is in cryptography and signal processing. C may not have a rotate operator. but it is easy to implement a rotate using left and right rotates and logical operators. For example a right rotate is: unsigned int data=0xF; data= data>>1  data<<31; The idea is easy enough to understand. First we perform a right logical shift which leaves the most significant bit zeroed. Next we perform a left logical shift 31 times to move the lowest significant bit to become the highest significant bit. The two are ORed together to give the result 0x80000007. You can see the general principle. If you want a right rotate of n bits of a 32bit int then use: data= data>>n  data<<32n; Similarly, if you want a left rotate of n bits of a 32bit value then use: data= data<<n  data>>32n; Notice that n cannot be negative or equal to 32, which would trigger undefined behavior. Also notice that data has to be unsigned so as to use logical shifts. It is said that most compilers will detect the above idioms and convert the instructions into a machine code rotate instruction if possible. GCC does this optimization, but only if you make sure that the rotation is positive. That is: unsigned int data=0x0F; data= data>> (unsigned) 1  data<< (unsigned)31; compiles to: ror %eax where ror is a rotate right instruction. If you leave off the unsigned qualifiers the line compiles to the equivalent right shift and left shift ORed together. It would be better if C had a rotate operator. Testing a BitFinal version in book EndianismFinal version in book Some Examples.OptionsOverflow Free AverageComputing a ChecksumFinal version in book Summary
Fundamental C: Getting Closer To The MachineNow available as a paperback and ebook from Amazon.
Also see the companion volume: Applying C <ASIN:1871962609> <ASIN:1871962463> <ASIN:1871962617> <ASIN:1871962455>
Related ArticlesRemote C/C++ Development With NetBeans Getting Started With C/C++ On The Micro:bit To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
Comments
or email your comment to: comments@iprogrammer.info


Last Updated ( Monday, 18 March 2019 ) 