Thursday, May 10, 2012

Binary Shift operation

Binary manipulation is one of the vital part in programming. We can do some manipulation through this in very efficient way. Bitwise operations are necessary for much low-level programming.
It will be frequently used in device driver development ,protocol developemnt and low-level graphics.

There are three types of shift operations present in the binary world
1)  Arithmetic (Signed Shift) or >> / <<
2)  Logical  ( Unsigned Shift) or >>> / <<<
3)  Rotational

The general logic behind shifting is

·        Shifting left by n bits on a signed or unsigned binary number "Y" has the effect of multiplying it by 2n.

                  result = (Y x 2n )

For example
Consider a binary number 139   ( 1000 1011)
139 << 1 =  278 (1 0001 0110) : Here 1 is overflow.
If you get any confusion here check the same with the value 8( 0000 1000)
8 << 1 =  8 x 21 =  16 ( 0001 0000)
·    Shifting right by n bits on a signed or unsigned binary number has the effect of dividing it by  2n.

                  result = (Y / 2n )

For example
Consider a binary number 139   ( 1000 1011)
139 >> 1 =  69

Apply the formula
result  = ( 139 / 21) =  69.5

(which rounds towards 0 for arithmetic shift and towards negative infinity for Logical shift This is one of the main different between  arithmetic and logical shift)
    
Logical shift (Un signed):
·        It always rounds down (towards negative infinity). Refer the above written example for the sample Logical shift.

Arithmetic shift (Signed):
·    It is similar to Logical shift except that left most bits will be filled with the sign bit of the original number instead of  0's
·    Consider a binary number 139   ( 1000 1011). In arithmetic shift this 1st bit represent the sign of the number. 
      1 -- represent negative
      0 -- represent positive .

      139 >> 1 =  69


     ·    It always rounds towards 0
   Arithmetic shifts can be useful as efficient ways of performing multiplication or division of signed integers

Example 1:
Calculate the result of  -16 divide by 4
      -16 / 2  = - 8
(Divide a number by 2 is equivalent to right shift a number by 1)

Binary equivalent of  16 = ( 0001 0000).


To represent the negative number we need to calculate the 2's complement of the original number
 16                         ----->   0001 0000
1's Complement      ----->   1110 1111
2's Complement      ----->   1111 0000
-16                         ----->   1111 0000

now -16 >> 1 =  1111 1000 ( This is equivalent to -8)


Rotational/ Circular  Shift :
·     Rotation shift is a circular shift. Instead of pushing  "0" it will push discarded bit.

For example if we do normal right shift operation , LSB at the right end will be discarded and a '0' will be pushed into the MSB from the left end.

But in rotational shift LSB at the right end will be removed and it will be pushed as the  MSB from the left end.
Here we need do convert a integer number into binary. Then we are going to break the binary number into smaller pieces to get the certain range of values

Sample program in C :
Consider a  integer 92 .Binary equivalent of 91 is "0101 1100"

In this binary number bits from 0 to 2 representing a particular value. And 4 to 6 representing some other value.
Bits from 0 to 2 is - "100"  Bits from 4 to 6 is - "101" .So here the requirement is break the binary number into above mentioned  range. And return the result.

#include<Stdio.h>
#include<math.h>

const int BIT_LENGTH = 31; //(0 to 31)bits
int aBArray[32];
void toBinary(long,int);
void print();

long getSensor() {
    return 2543133;
}

int getRainfall(long sensorReading) {
    int RAINFALL_START = 7;
    int RAINFALL_END = 0;
    toBinary(sensorReading, BIT_LENGTH);
    print();
    return getResult(RAINFALL_START, RAINFALL_END);
}

int getHumidity(long sensorReading) {
    int HUMIDITY_START = 15;
    int HUMIDITY_END = 11;
    return getResult(HUMIDITY_START, HUMIDITY_END);
}

int getTemperature(long sensorReading) {
    int TEMP_START = 23;
    int TEMP_END = 18;
    return getResult(RAINFALL_START, RAINFALL_END);
}
void print( ){
    int i;
    printf("\n******************RESULT: BINARY************************\n");
   
    for(i = 0; i <= BIT_LENGTH; i++) {
        printf( " %d",aBArray[i]);
        if((i + 1) % 4 ==0){
            printf(" ")
        }
     }
    printf("\n**************************************************************\n");
}

int getResult(long aStart, int aEnd) {

     int initPower = (aStart - aEnd), bit, result = 0;
     printf("\n");
    for(bit = (BIT_LENGTH - aStart);bit <= (BIT_LENGTH - aEnd); bit++) {
            result = result + (aBArray[bit] * pow(2,initPower--) );
    }
    return result;
}
void toBinary(long number, int index) {

      int remainder;
      if(number <= 1) {

           aBArray[index] = number;
          return;
      }
       remainder = number % 2;
       aBArray[index] = remainder;
       toBinary(number >> 1, --index);  
}

int main() {
   long sensorReading = getSensor();
   clrscr();
   printf("\nRainfall : %d\n", getRainfall(sensorReading));
   printf("\nHumidity : %d\n", getHumidity(sensorReading));
   printf("\nTemperature : %d\n", getTemperature(sensorReading));
   return 0;
}






No comments:

Post a Comment