Есть ли более эффективный способ разбить число на цифры?

Question

Я должен разделить число на цифры, чтобы отобразить его на ЖК-дисплее.Прямо сейчас я использую следующий метод:

pos = 7;

do
{
    LCD_Display(pos, val % 10);
    val /= 10;
    pos--;
} while (pos >= 0 && val);

Проблема этого метода заключается в том, что операции деления и по модулю выполняются чрезвычайно медленно на микроконтроллере MSP430.Есть ли какая-либо альтернатива этому методу, что-либо, что не связано с делением или уменьшает количество операций?

Примечание: я не могу использовать какие-либо библиотечные функции, такие как itoaБиблиотеки большие, а сами функции довольно ресурсоемки (как по количеству циклов, так и по использованию ОЗУ).

Answer 1

Вы можете делать вычитания в цикле с предопределенными значениями базы 10.

Мой C немного ржавый, но что-то вроде этого:

int num[] = { 10000000,1000000,100000,10000,1000,100,10,1 };

for (pos = 0; pos < 8; pos++) {
  int cnt = 0;
  while (val >= num[pos]) {
    cnt++;
    val -= num[pos];
  }
  LCD_Display(pos, cnt);
}

Answer 2

Да, есть другой способ , первоначально изобретенный (по крайней мере AFAIK) Терье Матизеном.Вместо того, чтобы делить на 10, вы (вроде) умножаете на обратную величину.Хитрость, конечно, заключается в том, что в целых числах вы не можете представлять обратную величину напрямую.Чтобы восполнить это, вы работаете с масштабированными целыми числами.Если бы у нас была плавающая точка, мы могли бы извлечь цифры с помощью чего-то вроде:

input = 123

first digit = integer(10 * (fraction(input * .1))
second digit = integer(100 * (fraction(input * .01))

... и т. Д. Столько раз, сколько необходимо.Чтобы сделать это с целыми числами, мы просто масштабируем их на 2 ³² (и округляем каждое вверх, так как будем использовать усеченную математику).В Си алгоритм выглядит так:

#include <stdio.h>

// here are our scaled factors
static const unsigned long long factors[] = { 
    3435973837,  // ceil((0.1 * 2**32)<<3)
    2748779070,  // ceil((0.01 * 2**32)<<6)
    2199023256,  // etc.
    3518437209,
    2814749768,
    2251799814,
    3602879702,
    2882303762,
    2305843010
};

static const char shifts[] = {
    3, // the shift value used for each factor above
    6,
    9,
    13,
    16,
    19,
    23,
    26,
    29
};

int main() { 
    unsigned input = 13754;

    for (int i=8; i!=-1; i--) {
        unsigned long long inter = input * factors[i];
        inter >>= shifts[i];
        inter &= (unsigned)-1;
        inter *= 10;
        inter >>= 32;
        printf("%u", inter);
    }
    return 0;
}

Операции в цикле будут напрямую отображаться в инструкции на большинстве 32-битных процессоров.Ваша типичная инструкция умножения будет принимать 2 32-битных ввода и давать 64-битный результат, что нам здесь и нужно.Обычно это будет немного быстрее, чем инструкция деления.В типичном случае некоторые операции могут (или, по крайней мере, с некоторой тщательностью) исчезнуть на языке ассемблера.Например, там, где я сделал inter &= (unsigned)-1;, на языке ассемблера вы обычно сможете просто использовать нижний 32-битный регистр, в котором был сохранен результат, и просто игнорировать все, что содержит верхние 32 бита.Аналогично, inter >>= 32; означает, что мы используем значение в верхнем 32-битном регистре и игнорируем нижний 32-битный регистр.

Например, в языке ассемблера x86 это выглядит примерно так:

    mov ebx, 9 ; maximum digits we can deal with.
    mov esi, offset output_buffer
next_digit:
    mov eax, input
    mul factors[ebx*4]
    mov cl, shifts[ebx]
    shrd eax, edx, cl
    mov edx, 10 ; overwrite edx => inter &= (unsigned)-1
    mul edx 
    add dl, '0'
    mov [esi], dl ; effectively shift right 32 bits by ignoring 32 LSBs in eax
    inc esi
    dec ebx
    jnz next_digit
    mov [esi], bl ; zero terminate the string

На данный момент я чуть-чуть обманул и написал код, предполагающий дополнительный элемент в начале каждой таблицы (factors и shifts).Это не является строго необходимым, но упрощает код за счет потери 8 байтов данных.С этим тоже довольно легко покончить, но на данный момент я не беспокоился.

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

Answer 3

Еще один способ - использовать двойной балл .Это способ преобразования двоичного кода в BCD с добавлением и сдвигом битов, поэтому он очень подходит для микроконтроллеров.После разбиения на BCD вы можете легко распечатать каждое число

Answer 4

Это моя попытка полного решения. Надо отдать должное Guffa за предоставление общей идеи. Это должно работать для 32-битных целых чисел, со знаком или иначе и 0.

#include <stdlib.h>
#include <stdio.h>

#define MAX_WIDTH (10)

static unsigned int uiPosition[] = {
  1u,
  10u,
  100u,
  1000u,
  10000u,
  100000u,
  1000000u,
  10000000u,
  100000000u,
  1000000000u,
};

void uitostr(unsigned int uiSource, char* cTarget)
{
  int i, c=0;

  for( i=0; i!=MAX_WIDTH; ++i )
  {
    cTarget[i] = 0;
  }

  if( uiSource == 0 )
  {
    cTarget[0] = '0';
    cTarget[1] = '\0';
    return;
  }

  for( i=MAX_WIDTH -1; i>=0; --i )
  {
    while( uiSource >= uiPosition[i] )
    {
      cTarget[c] += 1;
      uiSource -= uiPosition[i];
    }

    if( c != 0 || cTarget[c] != 0 )
    {
      cTarget[c] += 0x30;
      c++;
    }
  }

  cTarget[c] = '\0';
}

void itostr(int iSource, char* cTarget)
{
  if( iSource < 0 )
  {
    cTarget[0] = '-';
    uitostr((unsigned int)(iSource * -1), cTarget + 1);
  }
  else
  {
    uitostr((unsigned int)iSource, cTarget);
  }
}

int main()
{
  char szStr[MAX_WIDTH +1] = { 0 };

  // signed integer
  printf("Signed integer\n");

  printf("int: %d\n", 100);
  itostr(100, szStr);
  printf("str: %s\n", szStr);

  printf("int: %d\n", -1);
  itostr(-1, szStr);
  printf("str: %s\n", szStr);

  printf("int: %d\n", 1000000000);
  itostr(1000000000, szStr);
  printf("str: %s\n", szStr);

  printf("int: %d\n", 0);
  itostr(0, szStr);
  printf("str: %s\n", szStr);

  return 0;
}

Answer 5

Я бы использовал временную строку, например:

char buffer[8];
itoa(yourValue, buffer, 10);
int pos;

for(pos=0; pos<8; ++pos)
    LCD_Display(pos, buffer[pos]); /* maybe you'll need a cast here */

edit: поскольку вы не можете использовать библиотеку itoa, тогда Я думаю, что ваше решение уже является лучшим , если вы компилируете с включенной максимальной оптимизацией.

Вы можете взглянуть на это: Наиболее оптимизированный способ расчета модуля в C