我同意 Clifford 的观点,如果不需要的话,你不必担心优化,而且你可以将日志清理推到分析平台上,而不必担心在嵌入式应用程序中格式化。
话虽如此,这里有一篇文章可能对你有用。它使用了循环、移位、加法和分支,具有线性/常数复杂度:
http://www.johnloomis.org/ece314/notes/devices/binary_to_BCD/bin_to_bcd.html
另外,我认为制作一些不执行除法、乘法或分支操作,但仍然给出正确答案(0-1024)的代码会很有趣。不能保证这比其他选项更快。这种代码只是一个探索的选择。
我很想看看是否有人能提供一些技巧,使代码更小、需要更少的内存或更少的操作,同时保持其余计数相等或缩小它们:)
统计数据:
- 224字节的常量(不知道代码大小)
- 5位移位右
- 3个减法
- 5个按位与
- 4个按位或
- 1个大于比较
性能:
使用 Jonathan Leffler 的答案中的 perf 比较和 itoa 例程,这里是我得到的统计数据:
- 除法 2.15
- 减法 4.87
- 我的解决方案 1.56
- 暴力查找 0.36
我将迭代次数增加到 200000,以确保没有时间分辨率问题,并且必须在函数签名中添加 volatile,以使编译器不优化循环。我使用 VS2010 express w/ vanilla "release" 设置,在一个 3ghz 双核 64 位 Windows 7 机器上运行(尽管它编译成 32 位)。
代码:
#include "stdlib.h"
#include "stdio.h"
#include "assert.h"
void itoa_ten_bits(int n, char s[])
{
static const short thousands_digit_subtract_map[2] =
{
0, 1000,
};
static const char hundreds_digit_map[128] =
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
0, 0, 0,
};
static const short hundreds_digit_subtract_map[10] =
{
0, 100, 200, 300, 400, 500, 600, 700, 800, 900,
};
static const char tens_digit_map[12] =
{
0, 1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 9,
};
static const char ones_digit_map[44] =
{
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 1, 2, 3
};
static const char a1 = 0x10 % 10, a2 = 0x20 % 10, a3 = 0x40 % 10, a4 = 0x80 % 10;
static const char ones_digit_append_map[16] =
{
0, a1, a2, a1 + a2,
a3, a1 + a3, a2 + a3, a1 + a2 + a3,
a4, a1 + a4, a2 + a4, a1 + a2 + a4,
a3 + a4, a1 + a3 + a4, a2 + a3 + a4, a1 + a2 + a3 + a4,
};
char thousands_digit, hundreds_digit, tens_digit, ones_digit;
assert(n >= 0 && n < 1024 && "n must be between [0, 1024)");
thousands_digit = (n >> 3 & 0x7f) > 0x7c;
n -= thousands_digit_subtract_map[thousands_digit];
ones_digit = ones_digit_map[
(n & 0xf)
+ ones_digit_append_map[n >> 4 & 0xf]
+ ones_digit_append_map[n >> 8 & 0x3]
];
n -= ones_digit;
hundreds_digit = hundreds_digit_map[n >> 3 & 0x7f];
n -= hundreds_digit_subtract_map[hundreds_digit];
tens_digit = tens_digit_map[n >> 3];
s[0] = '0' | thousands_digit;
s[1] = '0' | hundreds_digit;
s[2] = '0' | tens_digit;
s[3] = '0' | ones_digit;
s[4] = '\0';
}
int main(int argc, char* argv)
{
int i;
for(i = 0; i < 1024; ++i)
{
char blah[5];
itoa_ten_bits(i, blah);
if(atoi(blah) != i)
printf("failed %d %s\n", i, blah);
}
}
temp
数组反转吗?个位数放在 temp[0],十位数放在 temp[1],以此类推。例如:42 ==> temp[0] = '2'; temp[1] = '4'; temp[2] = '0'; temp[3] = '0'; - pmg