有没有更有效的方法将一个数字分解为它的各个位数?

15

我必须将一个数字拆分为其各个位数,以便在LCD上显示。目前我使用以下方法:

pos = 7;

do
{
    LCD_Display(pos, val % 10);
    val /= 10;
    pos--;
} while (pos >= 0 && val);
这种方法的问题在于,在MSP430微控制器上,除法和取模运算非常慢。是否有任何替代方法,可以不涉及除法或减少操作次数?
注:我不能使用任何库函数,如itoa。这些库很大,函数本身也相当耗资源(无论是在循环次数还是RAM使用方面)。

这可能看起来像是微小的优化,但我编写的示例代码大约需要2.5毫秒,如果你在电池供电下运行,那就是一个漫长的时间。 - alex
3
有些编译器可以将除法和取模操作优化为乘法和位移操作。您使用的是哪个编译器和哪些优化? - Basile Starynkevitch
我现在正在使用IAR,优化设置为低(尽管它对代码的这部分没有影响)。除法需要很长时间,特别是当val是uint32_t类型时。每个操作大约需要450个周期。 - alex
还可以参考这个链接:https://dev59.com/6m035IYBdhLWcg3wNdLg - dbrank0
谷歌二进制到BCD转换。有一些巧妙的方法可以实现它。 Atmel有一个应用笔记,专门针对优化过的特定转换。 - Mark Lakata
显示剩余3条评论
5个回答

13

你可以使用预定义的十进制值,在循环中执行减法操作。

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

有趣的想法。我会研究一下,看看执行时间是否有差异。谢谢! - alex
2
你应该将num声明为const,因为它是一个常量查找表。除了"const-correctness"的好处外,在某些平台上它还可以使代码更加高效。 - Lundin
@Lundin 当然可以!num 数组应该在使用它的文件中是一个 static const - alex
@alex 使用static关键字和const一起使用是一个可以争论的实践。由于在文件作用域中声明const表变量最有意义,它们将默认获得静态存储期。此外,这完全取决于const是否应该从多个文件中访问,还是仅由当前文件使用。 const变量是C中少数几种可以拥有全局变量的情况之一,因为没有外部调用者可以更改其内容以实现意大利面条代码。 - Lundin
很高兴看到它能正常工作。 :) 你也可以尝试将数组的值复制到while循环外的本地变量中。这可能会再节省一些微秒。 - Guffa
显示剩余3条评论

6

是的,还有另一种方法,最初由Terje Mathiesen发明(至少我所知道的)。它不是通过除以10来实现的,而是通过(某种程度上)乘以倒数。当然,诀窍在于,在整数中无法直接表示倒数。为了弥补这一点,我们使用缩放整数进行计算。如果我们有浮点数,我们可以使用类似以下的方式提取数字:

input = 123

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

对于需要的位数,我们可以使用整数来实现,基本上只需将其乘以232(并向上取整,因为我们将使用截断数学)。在C语言中,该算法如下:

#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

目前,我有点作弊,编写代码时假设每个表格(factorsshifts)的开头都有一个额外的项目。这并非绝对必要,但简化了代码,代价是浪费了8字节的数据。消除这种情况也很容易,但我暂时没有费心去做。
无论如何,消除除法使得许多缺乏专用除法硬件的低中档处理器速度明显加快。

它能够工作,虽然我没有机会在实际的开发板上尝试它,看看它的表现如何。谢谢! - alex
1
@alex:经过一番搜索,我对它在这种情况下的工作效果不太确定。MSP 430显然缺乏乘法指令,这可能会对其造成一定影响。 - Jerry Coffin

1
另一种方法是使用double dabble。这是一种只使用加法和位移将二进制转换为BCD的方法,非常适合微控制器。在拆分为BCD后,您可以轻松打印出每个数字。

0
我会使用一个临时字符串,例如:
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 */

编辑:由于您不能使用库函数itoa,我认为您的解决方案已经是最好的,只要您打开了最大优化编译选项。

您可以看一下这个链接:在C语言中计算模数的最优方式


我不能使用任何库函数,它们占用大量代码空间并且通常非常耗费资源。 - alex

0

这是我尝试的完整解决方案。应该感谢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;
}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接