Fundamental C - Shifts And Rotates
Monday, 18 March 2019
Article Index
Fundamental C - Shifts And Rotates
Rotates

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.

#### 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. ## Fundamental C: Getting Closer To The Machine

#### Now available as a paperback and ebook from Amazon.

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

 Python Tops IEEE Spectrum's Rankings For Fourth Time27/07/2020IEEE Spectrum has an interactive app that ranks the popularity of dozens of programming languages, well 55 to be precise. It has just published its rankings for 2020, the 7th year of this ex [ ... ] + Full Story Language Popularity Retrospective05/08/2020In the latest edition of the RedMonk Language Rankings, Python has displaced Java to occupy second place, below JavaScript which holds on to its long-help top position. This is hardly unexpected - Pyt [ ... ] + Full Story More News 