Fundamental C - Shifts And Rotates
Written by Harry Fairhead   
Monday, 18 March 2019
Article Index
Fundamental C - Shifts And Rotates
Rotates

Normalizing Masks

Typically 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.

Rotate

There 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 low-order bit is shifted into the high-order bit. You can see that this is rotation of the bits.

Similarly a left rotate shifts all of the bits left and moves the high-order bit to become the new low-order 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 32-bit int then use:

data= data>>n | data<<32-n;

Similarly, if you want a left rotate of n bits of a 32-bit value then use:

data= data<<n | data>>32-n;

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 Bit

Final version in book

Endianism

Final version in book

Some Examples.

Options

Overflow Free Average

Computing a Checksum

Final version in book

Summary

 

  • There are four bitwise logical operators &, |, ^ and ~. These should not be confused with the logical operators &&, || and !.

  • The bitwise logical operators behave differently on signed and unsigned types.

  • A mask is a way of controlling which bits a bitwise operation affects.

  • There are two shift operators: the << arithmetic or logical shift left and >> an arithmetic shift right.

  • Arithmetic shift left corresponds to multiplying an integer type by 2 and an arithmetic shift right divides by 2.

  • Arithmetic shift right isn't exactly the same as integer division by 2 for negative values as it rounds towards negative infinity.

  • There is no rotate operator in C, but you can construct one.

  • Masks can also be used to test the state of a bit or group of bits.

  • There is no standard for the order in which parts of a multi-byte value are stored. Little endian stores the low-order bits first and big endian stores the high-order bits first.

Cbookcover

Fundamental C: Getting Closer To The Machine

Now available as a paperback and ebook from Amazon.

  1. About C
      Extract Dependent v Independent
                  & Undefined Behavio
  2. Getting Started With C Using NetBeans
  3. Control Structures and Data
  4. Variables
      Extract Variables 
  5. Arithmetic  and Representation
      Extract Arithmetic and Representation 
  6. Operators and Expression
      Extract Side Effects, Sequence Points And Lazy Evaluation
      First Draft of Chapter: Low Down Data
  7. Functions Scope and Lifetime
  8. Arrays
      Extract  Simple Arrays 
      Extract  Ennumerations 
  9. Strings
      Extract  Simple Strings 
  10. Pointers
      Extract  Starting Pointers
      Extract  Pointers, Cast & Type Punning
  11. Structs
      Extract Basic Structs 
      Extract Typedef ***NEW
  12. Bit Manipulation
      Extract Shifts And Rotates 
  13. Files
     Extract Files 
  14. Compiling C – Preprocessor, Compiler, Linker
     Extract Compilation & Preprocessor

Also see the companion volume: Applying C

<ASIN:1871962609>

<ASIN:1871962463>

<ASIN:1871962617>

<ASIN:1871962455>

 

 

 

Related Articles

Remote C/C++ Development With NetBeans

Raspberry Pi And The IoT In C

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.

Banner


Introducing Jetpack Compose for Desktop
10/11/2020

JetBrain's Jetpack Compose for Desktop is an open source project being developed in collaboration with Google’s Jetpack Compose, intended to simplify and accelerates UI development for desktop appli [ ... ]



TypeScript 4.1 Adds Temporal Literal Types
23/11/2020

TypeScript has been updated with new checking flags, editor productivity updates, and speed improvements, alongside new features including support for temporal literal types.


More News

square

 



 

Comments




or email your comment to: comments@i-programmer.info

 



Last Updated ( Monday, 18 March 2019 )