Bit shifting in BCD

Question

I am shifting the bits of a BCD number either left or right to quickly multiply or divide by 2. Here is a quick example of shifting left:

void LShift(unsigned char *arg)
{
   int i, carry=0, temp;
   for(i=2;i>=0;i--)
   {
      temp=(arg[i]<<1)+carry;
      if (temp>9) temp+=6;
      carry=temp>>4;
      arg[i]=temp&0xF;
   }
}

This works fine and if you give it an array like {4,5,6} it will return {9,1,2}. The problem is that if I want to shift by more than one bit, I have to call the function over and over. Is there any clever way to shift by more than one bit at a time without converting the BCD number to decimal first?

Answer 1

See below, N being the number of bits to shift, assuming N<=3, if you shift by more than 3 (N>3), you'll need to handle more than one digit of carry (e.g. 9*(2^4) = 144):

void LShift(unsigned char *arg)
{
   int i, carry=0, temp;
   for(i=2;i>=0;i--)
   {
      temp=(arg[i]<<N)+carry; 
      arg[i]=temp%10;
      temp -= arg[i];
      carry = temp/10;
   }
}

Or if you want something closer to the original:

void LShift(unsigned char *arg)
{
   int i, carry=0, temp;
   for(i=2;i>=0;i--)
   {
      temp=(arg[i]<<N)+carry;
      temp+=6 * (temp/10);
      carry=temp>>4;
      arg[i]=temp&0xF;
   }
}

Also note that (in all versions, including the original) you may be left with carry which is a new digit.

Answer 2

You have to redesign the function to include the number of bits to shift as an argument.And use that argument to shift the bcd byte a number of places .

void LShift(unsigned char *arg) can be modified to void LShift(unsigned char *arg,int n)

and do

temp=(arg[i]<<n)+carry;

Answer 3

Coding up the shift logic is a little complicated, as the carry manipulation is a little hairy. It turns into code that looks very much like a shift and add multiplication implementation.

void LeftShiftN_1 (unsigned char arg[BCD_DIGITS], unsigned N) {
    int i, j;
    unsigned x, carry;
    unsigned char accum[BCD_DIGITS];
    memset(accum, '\0', sizeof(carry));
    for (i=BCD_DIGITS; i>0; --i) {
        x = arg[i-1];
        x <<= N;
        carry = 0;
        for (j=i; j>=0; --j) {
            carry += accum[j-1] + x % 10;
            x /= 10;
            accum[j-1] = carry % 10;
            carry /= 10;
        }
    }
    memcpy(arg, accum, sizeof(accum));
}

I think it is much simpler and efficient to convert from BCD and back again to do the shift. I implemented in a straightforward way, I am sure the conversion operations could be optimized.

void LeftShiftN_2 (unsigned char arg[BCD_DIGITS], unsigned N) {
    int i;
    unsigned accum;
    accum = 0;
    for (i=0; i<BCD_DIGITS; ++i) {
        accum = 10*accum + arg[i];
    }
    accum <<= N;
    for (i=BCD_DIGITS; i>0; --i) {
        arg[i-1] = accum % 10;
        accum /= 10;
    }
}