Я согласен с тем, что сказал Клиффорд, что вам не нужно беспокоиться об оптимизации, если вам это не нужно, и что вы можете перенести очистку журнала на свою платформу анализа, а не беспокоиться о форматировании во встроенном приложении.
Как говорится, вот статья, которая может быть вам полезна. Он использует цикл, сдвиги, добавления и ответвления, с линейной / постоянной сложностью: http://www.johnloomis.org/ece314/notes/devices/binary_to_BCD/bin_to_bcd.html
Кроме того, я подумал, что было бы интересно создать некоторый код, который не выполняет деления, умножения или ответвления, но все же дает правильный ответ [0 - 1024). Не обещает, что это будет быстрее, чем другие варианты. Этот код просто вариант для изучения.
Хотелось бы посмотреть, могут ли кто-нибудь придумать какие-нибудь хитрости, чтобы сделать код меньше, потребовать меньше памяти или меньше операций, при этом оставляя равными остальные значения или уменьшая их:)
Статистика:
- 224 байта в константах (без представления о размере кода)
- 5 бит-прав смещения
- 3 вычитания
- 5 поразрядно
- 4 бит-ор
- 1 больше, чем сравнение
Перф:
Используя сравнения perf и процедуры itoa в ответе Джонатана Леффлера, вот статистика, которую я получил:
- Деление 2,15
- Вычитание 4.87
- Мое решение 1.56
- Поиск грубой силы 0.36
Я увеличил количество итераций до 200000, чтобы у меня не было проблем с разрешением синхронизации, и мне пришлось добавить volatile к сигнатурам функций, чтобы компилятор не оптимизировал цикл. Я использовал VS2010 express с ванильными настройками «выпуска» на двухъядерной 64-битной Windows 7-машине с тактовой частотой 3 ГГц (хотя она была скомпилирована в 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
};
/* Compiler should optimize out appX constants, % operations, and + operations */
/* If not, use this:
static const char ones_digit_append_map[16] =
{
0, 6, 2, 8, 4, 10, 6, 12, 8, 14, 10, 16, 12, 18, 14, 20,
};
*/
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)");
/* n &= 0x3ff; can use this instead of the assert */
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);
}
}