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.

Fundamental C: Getting Closer To The Machine

Now available as a paperback and ebook from Amazon.

1. About C
     Extract Dependent v Independent
                 & Undefined Behavior 
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: Expressions
     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
     Extract: String I/O ***NEW!!
10. Pointers
      Extract  Starting Pointers
      Extract  Pointers, Cast & Type Punning
11. Structs
      Extract Basic Structs
      Extract Typedef
    
12. Bit Manipulation
      Extract Basic Bits
      Extract Shifts And Rotates 
    
13. Files
     Extract Files
     Extract Random Access 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>

• Harry Fairhead is the author of Raspberry Pi IoT in C (I/O Press). This extract is from his new book, Fundamental C, where he takes an in-depth look at C for use in any close-to-the-hardware context.

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.

Comments

Make a Comment or View Existing Comments Using Disqus

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