Tuesday, October 18, 2011

Bitwise Shifts and Rotations in C

In the examples below, I shall use the uint8_t datatype (8 bits integer) from the stdint.h library. If you never used it before or if you have difficulties with the "basic" bitwise operations you should read this first.

1.Shift left operation
Description
Shifting bits left with n positions means moving every bit from its position n positions to the left starting with the leftmost bit. The bits who are added right will have the value 0.
Example:

Bits
7th
6th
5th
4th
3th
2nd
1st
0th

a
0
1
1
0
1
0
1
1
107
a<<3
0
1
0
1
1
0
0
0
88  
In the first row, the bits who will be lost have a red background, and the bits who will be shifted have a green background. In the second row the bits who were added have a red background and the bits who were shifted have a green background.
Syntax
#include<stdio.h>
#include<stdint.h>

int main(void)
{
   uint8_t a = 107U;
   uint8_t ashiftleft3 = a<<3;
   printf("a<<3 %u",ashiftleft3);
   return 0;
}
/*Output
a<<3 88
*/
2.Shift right operation
Description
Shifting bits right with n positions means moving every bit from its position n positions to the right starting with the rightmost bit. The bits who are added left will have the value 0. 
Example:

Bits
7th
6th
5th
4th
3th
2nd
1st
0th

a
0
1
1
0
1
0
1
1
107
a<<3
0
0
0
0
1
1
0
1
13
In the first row, the bits who will be lost have a red background, and the bits who will be shifted have a green background. In the second row the bits who were added have a red background and the bits who were shifted have a green background.
Syntax:
#include<stdio.h>
#include<stdint.h>

int main(void)
{
   uint8_t a = 107U;
   uint8_t ashiftrightt3 = a>>3;
   printf("a>>3 %u",ashiftrightt3);
   return 0;
}
/*Output
a<<3 88
*/
3.Rotate left operation
Description
Rotating left with n positions means moving the first n leftmost bits from their position to the right of the rightmost bit.

Some compilers have the function unsigned int _rotl(unsigned int number, unsigned int bits) which performs a left rotation, but the function is not considered ANSI. Also, the function uses 32 bits instead of 8. The _rotl function can be found in the stdlib.h library.

If you do not have this function for your compiler (or you want its 8 bit version), you can easily implement it as:
uint8_t _rotl(uint8_t value, uint8_t shift)
{
   if ((shift &= 7) == 0)
   {
      return value;
   }
   else
   {
      return ((value << shift) | (value >> (8 - shift)));
   }
}
Example 
Bits
7th
6th
5th
4th
3th
2nd
1st
0th

a
0
1
1
0
1
0
1
1
107
Bits
4th
3th
2nd
1st
0th
7th
6th
5th

_rotl(a,3)
0
1
0
1
1
0
1
1
91
Syntax:
#include<stdio.h>
#include<stdint.h>

uint8_t _rotl(uint8_t value, uint8_t shift);

int main(void)
{
   uint8_t a = 107U;
   uint8_t arotl3 = _rotl(a,3);
   printf("arotl3 %u",arotl3);
   return 0;
}
/*Output
arotl3 91
*/
4.Rotate right operation
Description
Rotating right with n positions means moving the first n rightmost bits from their position to the left of the leftmost bit.

Some compilers have the function unsigned int _rotr(unsigned int number, unsigned int bits) which performs a right rotation, but the function is not considered ANSI. Also, the function uses 32 bits instead of 8. The _rotl function can be found in the stdlib.h library.

If you do not have this function for your compiler (or you want its 8 bit version), you can easily implement it as:
uint8_t _rotr(const uint8_t value, uint8_t shift)
{
    if( (shift &= 7) == 0)
    {
        return value;
    }
    else
    {
        return ( (value >> shift) | (value << (8 - shift)) );
    }
}
Example 
Bits
7th
6th
5th
4th
3th
2nd
1st
0th

a
0
1
1
0
1
0
1
1
107
Bits
2nd
1st
0th
7th
6th
5th
4th
3th

_rotr(a,3)
0
1
1
0
1
1
0
1
109
Syntax
#include<stdio.h>
#include<stdint.h>

uint8_t _rotr(uint8_t value, uint8_t shift);

int main(void)
{
   uint8_t a = 107U;
   uint8_t arotr3 = _rotr(a,3);
   printf("arotl3 %u",arotr3);
   return 0;
}
/*Output
arotl3 109
*/

Question: In which context do you use shifts and rotations?

References:
http://en.wikipedia.org/wiki/Bitwise_operations_in_C

No comments:

Post a Comment

Got a question regarding something in the article? Leave me a comment and I will get back at you as soon as I can!

Related Posts Plugin for WordPress, Blogger...
Recommended Post Slide Out For Blogger