Битовый сдвиг в BCD

Я сдвигаю биты числа BCD влево или вправо, чтобы быстро умножить или разделить на 2. Вот быстрый пример сдвига влево:

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;
   }
}

Это прекрасно работает, и если вы дадите ему массив типа {4,5,6}, он вернет {9,1,2}. Проблема в том, что если я хочу сдвинуться более чем на один бит, мне придется вызывать функцию снова и снова. Есть ли какой-нибудь умный способ сдвига более чем на один бит за раз без предварительного преобразования числа BCD в десятичное?


c bit-shift bcd
person Joey Shepard    schedule 23.07.2013    source источник
comment
Если это не C, отредактируйте свой вопрос, указав правильный языковой тег. Никогда не забывайте тег языка, он самый важный.   -  person Mat    schedule 23.07.2013
comment
arg[i]‹‹n, где n — количество битов, которые нужно сдвинуть   -  person nj-ath    schedule 23.07.2013
comment
Как функция обрабатывает {9,1,2} в качестве входных данных? Вам нужна дополнительная цифра (байт) вывода? Обобщая, вам, возможно, потребуется много дополнительных байтов для выходного значения для сдвигов больше 1. Вы можете обобщить интерфейс: size_t BCD_LShift(unsigned char *value, size_t vallen, size_t lshift, unsigned char *result, size_t reslen); где возвращаемое значение — это количество цифр BCD в результате. Интересно, где находится точка останова между повторным вызовом функции и «преобразовать в двоичное целое, сдвинуть, преобразовать в BCD»?   -  person Jonathan Leffler    schedule 23.07.2013
comment
Одна цифра 4 ‹‹ 2 в BCD дает 10, что явно неверно, так как должно быть (0x)16. Это достижимо только по логике, где регулировка производится на каждом этапе: 4‹‹ 1 = 8, 8‹‹1 = (8 + 3) ‹‹ 1 = 16.   -  person Aki Suihkonen    schedule 23.07.2013
comment
Спасибо за ваши комментарии, ребята. @AkiSuihkonen, именно этого я и боялся. Похоже, решения может и не быть.   -  person Joey Shepard    schedule 23.07.2013

Ответы (3)


arrow_upward
3
arrow_downward

См. ниже, N — количество битов для сдвига, предполагая, что N‹=3, если вы сдвинете более чем на 3 (N>3), вам потребуется обрабатывать более одной цифры переноса (например, 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;
   }
}

Или, если вы хотите что-то ближе к оригиналу:

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;
   }
}

Также обратите внимание, что (во всех версиях, включая оригинальную) у вас может остаться перенос, который является новой цифрой.

person Ofir    schedule 23.07.2013
comment
Это не работает. В двоично-десятичном коде на каждой ступени нужно корректировать цифры › 4 (на 3). - person Aki Suihkonen; 23.07.2013
comment
Проблема не в смещении, а в двоично-десятичном исправлении (строка if (temp>9) temp += 6;, которая работает только для 1-битных сдвигов) - person Chris Dodd; 23.07.2013
comment
Правильно, упустил тот факт, что программа зависит от переноса, никогда не превышающего 1, исправлено - person Ofir; 23.07.2013
comment
@Офир Спасибо. Это похоже на то, что я искал. Неужели нельзя обойти дивизию? Я работаю с микроконтроллером без аппаратной поддержки умножения или деления, поэтому я переключаюсь в первую очередь. Тем не менее, даже с таким делением это, вероятно, быстрее, чем вызов функции три раза, как это делал я. - person Joey Shepard; 23.07.2013
comment
Можно обойти деление с помощью таблицы поиска (я не уверен, что это лучше для вашей цели) - person Ofir; 23.07.2013

arrow_upward
1
arrow_downward

Вы должны перепроектировать функцию, чтобы включить количество битов для сдвига в качестве аргумента. И использовать этот аргумент для сдвига байта bcd на несколько позиций.

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

и делай

temp=(arg[i]<<n)+carry;
person Santhosh Pai    schedule 23.07.2013

arrow_upward
0
arrow_downward

Кодирование логики сдвига немного сложно, так как манипуляция с переносом немного запутана. Это превращается в код, очень похожий на реализацию сдвига и добавления умножения.

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));
}

Я думаю, что гораздо проще и эффективнее конвертировать из BCD и обратно, чтобы сделать сдвиг. Я реализовал простым способом, я уверен, что операции преобразования можно было бы оптимизировать.

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;
    }
}
person jxh    schedule 23.07.2013
comment
Да, может быть, в этом случае лучше просто преобразовать в десятичную форму. Выполнение любого вида умножения или деления может затормозить код, поскольку они будут преобразованы в повторяющиеся сложения. Я использую сдвиг битов для выполнения подпрограмм CORDIC, поэтому мне нужно, чтобы они были как можно быстрее. Однако кажется, что умножение и деление будут необходимы. - person Joey Shepard; 23.07.2013
comment
Если у вас действительно есть только 3 цифры BCD, то вам нужны только 3 справочные таблицы 10x10 для умножения, деления и мода. Я не знаю, будет ли индексация таблиц намного быстрее, чем ALU, но может быть. - person jxh; 23.07.2013