Bit manipulation is almost dead in high-level languages, but it is a core technique in C. In fact, it is one of the reasons for using C.  This extract, from my new book on programming C in an IoT context, looks at shifts and rotates.

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>

Bit Manipulation

Bit manipulation is almost dead in high-level languages and it isn’t as common in C as it once was. If you are writing low-level programs that interact in any way with the hardware, however, then bit manipulation will still be an essential part of what you do and, to get things right and to make sure you are doing things in sensible ways, you need to master the technique. The good news is that it isn’t difficult once you start to think about the contents of memory as a bit pattern that has many interpretations.

Sections in the chapter but not in this extract:

1. The Bitwise Operators

2. Signed v Unsigned

3. Masks

4. Using Masks

Shifting Values

As well as the basic logical operators, C also provides two shift operators which move the pattern of bits to the left or the right.

The << operator shifts the pattern of bits to the left shifting in zero into the low-order. So for example:

int data=0x0F;
int result=data << 4;

shifts the bit pattern in data four places to the left and so result contains 0xF0.

Similarly the >> operator shifts to the right, but there is a small complication concerning what is shifted into the new bit positions. What happens depends on whether the value being shifted is signed or unsigned.

For an unsigned value 0 is shifted into the highest order bit.

For a signed value the same bit is shifted in as the one moved out. That is, if the highest order bit was a 1 then a 1 is shifted into the vacant position and it if was a 0 a 0 is shifted in.

You can see that in the signed case the motivation with a right shift is to maintain the sign. That is, a shift keeps a positive number positive and a negative number negative. This sort of shift is usually called an arithmetic shift as distinct from a logical shift that always shifts a 0 in.

Notice that a left shift always shifts a 0 in, but this can change the sign of the value as a new bit becomes the sign bit.

For example:

int data=0x0F;
int result=data >>3;

shifts the bit pattern in data three places to the right and so result contains 1 since 1111 shifted three places right is 0001.

Not Quite Multiply And Divide

Notice that, for integers, shifting one place to the left is the same as multiplying the value by two and shifting one place to the right is the same as integer division by two but only for positive values. For example:

int data=1;
int result=data <<1;

stores 2 in result and:

int data=8;
int result=data >>1;

stores 4 in result.

Things are slightly more complicated for negative values. If you try

int data=7;
int result=data >>1;

then result is 3 which is what you would get with integer division i.e. 3.5 is truncated or rounded down to 3. However if you try:

int data=-7;
int result=data >>1;

you will find that result is -4. This is not what you would get with integer division which would give -3 after truncation. Right shift divides by 2 but with rounding towards the next smallest negative integer. This is a subtle point that often causes errors.

The reason for this behavior is the way the sign bit is extended For example:

int data=-1;
int result=data >>1;

stores -1 in result. The reason is that the initial bit pattern is all ones, i.e. 32 bits all set to one, and so shifting one place to the right shifts in another 1 as the high bit. That is, -1 is the same as 0xFFFFFFFF and the sign bit is 1 so a shift right moves a one into the high-order bit giving -1 again.

Compare this to:

unsigned int data=-1;
int result=data >>1;

In this case a zero is shifted into the high bit and the value stored in result gives zero followed by 31 ones, which is a positive value equal to 2147483647.

Notice that the -1 is stored in data as 0xFFFFFFFF but this is interpreted as a positive value when stored in an unsigned int. The result of the shift is 0x7FFFFFFF which is a positive number when assigned to a signed int.

What this means is that you can use either right and left shifts or multiplication and division by two to do almost the same job with a little care over negative values. Shifts are much faster than multiplication and division because the hardware generally supports a direct shift operation in a register.

If you want a logical right shift on a signed value then the simplest way of implementing it is to use a cast:

int data=-1;
int result=(unsigned) data >>1;

Also notice that you can write <<= and >>= to shift the value of a variable "in place". For example:

int data=-1;
data<<= 1

shifts the bit pattern in data one place to the left and stores the result in data, i.e. it shifts data one place to the left.