|
|
  |
Показать число с leading zeros. |
|
|
|
Jan 21 2015, 12:16
|

Местный
  
Группа: Участник
Сообщений: 329
Регистрация: 23-04-14
Пользователь №: 81 502

|
Цитата(Jenya7 @ Jan 21 2015, 12:03)  так нету библиотечных функций в том то и дело. и более лучшей генерик функции я не нашел. Зато есть такая штука, называется интернет, а в ней есть гугль. А если в гугле ввети запрос "c itoa implementation", то он вывалит кучу ссылок. а примерно третьей ссылкой можно воспользоваться, чтобы оценить масштабы бедствий: http://www.jb.man.ac.uk/~slowe/cpp/itoa.html
|
|
|
|
|
Jan 21 2015, 12:37
|
Гуру
     
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881

|
Цитата(Jenya7 @ Jan 21 2015, 15:03)  так нету библиотечных функций в том то и дело. и более лучшей генерик функции я не нашел. То, что я дал код, переделывается на работу без нулей введением одного флага, который сначала запрещен, и разрешается при первом ненулевом символе. И управляет занесением символов в выходной буфер. Все равно шустрее, чем использовать % и /, и, даже шустрее, чем c div_t div(int numer, int denom); (сразу % и / в одном флаконе). char str[9]; int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0}; int p=0; char *str_p = str; int i; int flag=0; while (num_table[p]) { i=0; while ( (number-=num_table[p]) >= 0) i++; number += num_table[p++]; flag |= i; if (flag) *str_p++='0' + i; } Еще можно дооптимизировать, чтобы условное занесение в буфер убрать из цикла, разделив цикл на две части, ну и убрать флаг. char str[9]; int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0}; int p=0; char *str_p = str; int i; int flag=0; int tmp; if (!num) { *str_p++='0'; return; } while ((tmp=num_table[p++]) && (number < tmp)) ; do { i='0'; while ( (number-=tmp) >= 0) i++; number += tmp; *str_p++=i; } while (tmp = num_table[p++]);
|
|
|
|
|
Jan 21 2015, 12:39
|

Местный
  
Группа: Участник
Сообщений: 329
Регистрация: 23-04-14
Пользователь №: 81 502

|
Цитата(SM @ Jan 21 2015, 12:17)  То, что я дал код, переделывается на работу без нулей введением одного флага, который сначала запрещен, и разрешается при первом ненулевом символе. И управляет занесением символов в выходной буфер. Все равно шустрее, чем использовать % и /, и, даже шустрее, чем c div_t div(int numer, int denom); (сразу % и / в одном флаконе). <зевая> int у нас какой разрядности ? Я практически отошел от использования "просто int". Гораздо спокойнее писать "uint32_t", "uint16_t", "uint8_t" и не беспокоиться о портабельности кода на машину с другой архитектурой ЦПУ. А еще я ненавижу знаковый int, и использую int32_t только там, где знак нужет в явном виде.
|
|
|
|
|
Jan 21 2015, 12:45
|
Профессионал
    
Группа: Участник
Сообщений: 1 778
Регистрация: 29-03-12
Пользователь №: 71 075

|
Цитата(SM @ Jan 21 2015, 14:45)  Еще, если Ваш CPU умеет быстро вычислять экспоненту числа, то можно сразу вычислить смещение, куда и делать itoa. Но, это уже вне стандартного С, тут придется работать с интринсиками, и забыть о кроссплатформенности.
Еще, думаю, самый быстрый способ, сделать свой itoa:
char str[9]; int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0}; int p=0; char *str_p = str; int i;
while (num_table[p]) { i=0; while ( (number-=num_table[p]) >= 0) i++; number += num_table[p++]; *str_p++='0' + i; }
Извиняюсь, если где ошибся, писал прямо сюда, ни откуда не копировал. И никаких itoa с собой не притащит из либы. И, добавлю, это быстро, если в процессоре нет аппаратного деления. while ( (number-=num_table[p]) >= 0) всегда true.
|
|
|
|
|
Jan 21 2015, 12:47
|
Гуру
     
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881

|
Цитата(CrimsonPig @ Jan 21 2015, 15:39)  <зевая> int у нас какой разрядности ? Это пусть автор разбирается. Я предпочитаю соблюдать старые добрые стандарты, где еще нет int32_t. Цитата(Jenya7 @ Jan 21 2015, 15:45)  while ( (number-=num_table[p]) >= 0) всегда true. Это с какого перепуга? Тип не unsigned. А если нужен полный диапазон unsigned, то тут, к сожалению, С не покатит, так как нужно условие по флагу переноса после математической операции, что реализуемо только на ассемблере. Оптимизация, штука тонкая....
|
|
|
|
|
Jan 21 2015, 12:54
|

Местный
  
Группа: Участник
Сообщений: 329
Регистрация: 23-04-14
Пользователь №: 81 502

|
Цитата(SM @ Jan 21 2015, 12:47)  А если нужен полный диапазон unsigned, то тут, к сожалению, С не покатит, так как нужно условие по флагу переноса после математической операции, что реализуемо только на ассемблере. Оптимизация, штука тонкая.... если почитать книжку "Hacker's delight" (она есть и в русском переводе) или опять же погуглить, то можно нарыть методов проверки операций над целыми числами на переполнение на чистом Ц. там битхаки, завязанные на конкретную разрядность...
|
|
|
|
|
Jan 21 2015, 13:02
|

Местный
  
Группа: Участник
Сообщений: 329
Регистрация: 23-04-14
Пользователь №: 81 502

|
Цитата(SM @ Jan 21 2015, 12:57)  Но это не оптимально. Разве что, только ради того, чтобы сделать это хоть как-то, но на С. Поэтому я не предлагаю таких решений в теме про оптимизацию алгоритма на скорость. для этого существуют debug asserts, тесты и метрики code coverage ... вон, без проверок на переполнение Ариан (или кто там) долетался... и истребитель потом кверху лапками переворачивался при полете на высоте ниже уровня моря.
|
|
|
|
|
Jan 21 2015, 13:05
|
Гуру
     
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881

|
Цитата(Jenya7 @ Jan 21 2015, 16:00)  надо добавить проверку что число "закончилось". Это и есть проверка на это - если число стало отрицательным, значит конец цикла. Для работы с unsigned это бы показал флаг переноса (carry), к сожалению, средствами С не доступный. Если же Вам хватит положительной части диапазона int32_t на все Ваши случаи, то ничего допиливать не надо, а использовать int32_t, на который рассчитан алгоритм. Если нужен полный диапазон unsigned int - то придется либо написать на ассемблере цикл, либо: while (number>=num_table[p]) {i++; number-=num_table[p]}; и прибавление number += num_table[p убить. Но это не оптимально, так как сравнение и вычитание, по своей сути, одна и та же операция, то есть, тут операций вдвое больше становится. Цитата(CrimsonPig @ Jan 21 2015, 16:02)  для этого существуют debug asserts, тесты и метрики code coverage для чего? Чтобы оптимально написать алгоритм на С, который на нем оптимально написать невозможно по причине недоступности флага переноса ?
|
|
|
|
|
Jan 21 2015, 13:28
|
Гуру
     
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881

|
Цитата(Jenya7 @ Jan 21 2015, 16:24)  и с int32_t не работает  Чего там не работает? Сейчас в MSVC 6.0 собрал для теста, все работает. Только не надо ему давать чисел, имеющих больше десятичных разрядов, чем максимальное в таблице. CODE #include "stdio.h"
void ItoA(char * str, int number) { int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0}; int p=0; char *str_p = str; int i; while (num_table[p]) { i='0'; while ( (number-=num_table[p]) >= 0) i++; number += num_table[p++]; *str_p++=i; } *str_p++=0; }
void ItoA1(char * str, int number) { int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0}; int p=0; char *str_p = str; int i; int flag=0; int tmp; if (!number) { *str_p++='0'; *str_p++=0; return; } while ((tmp=num_table[p++]) && (number < tmp)) ; do { i='0'; while ( (number-=tmp) >= 0) i++; number += tmp; *str_p++=i; } while (tmp = num_table[p++]); *str_p++=0; }
int main(int argc, char* argv[]) { int i=123456; char str[16]; char str1[16]; ItoA(str, i); ItoA1(str1, i); printf("%s %s\n", str, str1); return 0; }
|
|
|
|
|
Jan 21 2015, 14:18
|
Профессионал
    
Группа: Участник
Сообщений: 1 778
Регистрация: 29-03-12
Пользователь №: 71 075

|
Цитата(SM @ Jan 21 2015, 19:28)  Чего там не работает? Сейчас в MSVC 6.0 собрал для теста, все работает. Только не надо ему давать чисел, имеющих больше десятичных разрядов, чем максимальное в таблице. CODE #include "stdio.h"
void ItoA(char * str, int number) { int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0}; int p=0; char *str_p = str; int i; while (num_table[p]) { i='0'; while ( (number-=num_table[p]) >= 0) i++; number += num_table[p++]; *str_p++=i; } *str_p++=0; }
void ItoA1(char * str, int number) { int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0}; int p=0; char *str_p = str; int i; int flag=0; int tmp; if (!number) { *str_p++='0'; *str_p++=0; return; } while ((tmp=num_table[p++]) && (number < tmp)) ; do { i='0'; while ( (number-=tmp) >= 0) i++; number += tmp; *str_p++=i; } while (tmp = num_table[p++]); *str_p++=0; }
int main(int argc, char* argv[]) { int i=123456; char str[16]; char str1[16]; ItoA(str, i); ItoA1(str1, i); printf("%s %s\n", str, str1); return 0; }
офигеть! таки работает!  а вот листинг двух функций Код void itoa_with_leading_zeroes(int32_t number, char * str) { f64: b4b0 push {r4, r5, r7} f66: b08f sub sp, #60; 0x3c f68: af00 add r7, sp, #0 f6a: 6078 str r0, [r7, #4] f6c: 6039 str r1, [r7, #0] int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0}; f6e: f647 530c movw r3, #32012; 0x7d0c f72: f2c0 0300 movt r3, #0 f76: f107 0408 add.w r4, r7, #8 f7a: 461d mov r5, r3 f7c: cd0f ldmia r5!, {r0, r1, r2, r3} f7e: c40f stmia r4!, {r0, r1, r2, r3} f80: cd0f ldmia r5!, {r0, r1, r2, r3} f82: c40f stmia r4!, {r0, r1, r2, r3} f84: 682b ldr r3, [r5, #0] f86: 6023 str r3, [r4, #0] int p=0; f88: f04f 0300 mov.w r3, #0 f8c: 637b str r3, [r7, #52]; 0x34 char *str_p = str; f8e: 683b ldr r3, [r7, #0] f90: 633b str r3, [r7, #48]; 0x30 int i;
while (num_table[p]) f92: e02c b.n fee <itoa_with_leading_zeroes+0x8a> { i='0'; f94: f04f 0330 mov.w r3, #48; 0x30 f98: 62fb str r3, [r7, #44]; 0x2c while ( (number-=num_table[p]) >= 0) i++; f9a: e003 b.n fa4 <itoa_with_leading_zeroes+0x40> f9c: 6afb ldr r3, [r7, #44]; 0x2c f9e: f103 0301 add.w r3, r3, #1 fa2: 62fb str r3, [r7, #44]; 0x2c fa4: 6b7b ldr r3, [r7, #52]; 0x34 fa6: ea4f 0383 mov.w r3, r3, lsl #2 faa: f107 0238 add.w r2, r7, #56; 0x38 fae: 18d3 adds r3, r2, r3 fb0: f853 3c30 ldr.w r3, [r3, #-48] fb4: 687a ldr r2, [r7, #4] fb6: 1ad3 subs r3, r2, r3 fb8: 607b str r3, [r7, #4] fba: 687b ldr r3, [r7, #4] fbc: 2b00 cmp r3, #0 fbe: daed bge.n f9c <itoa_with_leading_zeroes+0x38> number += num_table[p++]; fc0: 6b7b ldr r3, [r7, #52]; 0x34 fc2: ea4f 0383 mov.w r3, r3, lsl #2 fc6: f107 0238 add.w r2, r7, #56; 0x38 fca: 18d3 adds r3, r2, r3 fcc: f853 3c30 ldr.w r3, [r3, #-48] fd0: 687a ldr r2, [r7, #4] fd2: 18d3 adds r3, r2, r3 fd4: 607b str r3, [r7, #4] fd6: 6b7b ldr r3, [r7, #52]; 0x34 fd8: f103 0301 add.w r3, r3, #1 fdc: 637b str r3, [r7, #52]; 0x34 *str_p++=i; fde: 6afb ldr r3, [r7, #44]; 0x2c fe0: b2da uxtb r2, r3 fe2: 6b3b ldr r3, [r7, #48]; 0x30 fe4: 701a strb r2, [r3, #0] fe6: 6b3b ldr r3, [r7, #48]; 0x30 fe8: f103 0301 add.w r3, r3, #1 fec: 633b str r3, [r7, #48]; 0x30 int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0}; int p=0; char *str_p = str; int i;
while (num_table[p]) fee: 6b7b ldr r3, [r7, #52]; 0x34 ff0: ea4f 0383 mov.w r3, r3, lsl #2 ff4: f107 0238 add.w r2, r7, #56; 0x38 ff8: 18d3 adds r3, r2, r3 ffa: f853 3c30 ldr.w r3, [r3, #-48] ffe: 2b00 cmp r3, #0 1000: d1c8 bne.n f94 <itoa_with_leading_zeroes+0x30> while ( (number-=num_table[p]) >= 0) i++; number += num_table[p++]; *str_p++=i; }
*str_p++=0; 1002: 6b3b ldr r3, [r7, #48]; 0x30 1004: f04f 0200 mov.w r2, #0 1008: 701a strb r2, [r3, #0] 100a: 6b3b ldr r3, [r7, #48]; 0x30 100c: f103 0301 add.w r3, r3, #1 1010: 633b str r3, [r7, #48]; 0x30 } 68 инструкций. и мой старый метод Код void ItoA(uint32_t n , char s[]) { ef4: b580 push {r7, lr} ef6: b084 sub sp, #16 ef8: af00 add r7, sp, #0 efa: 6078 str r0, [r7, #4] efc: 6039 str r1, [r7, #0] int i = 0; efe: f04f 0300 mov.w r3, #0 f02: 60fb str r3, [r7, #12] do { s[i++] = n % 10 + '0'; f04: 68fb ldr r3, [r7, #12] f06: 683a ldr r2, [r7, #0] f08: 18d0 adds r0, r2, r3 f0a: 6879 ldr r1, [r7, #4] f0c: f64c 43cd movw r3, #52429; 0xcccd f10: f6cc 43cc movt r3, #52428; 0xcccc f14: fba3 2301 umull r2, r3, r3, r1 f18: ea4f 02d3 mov.w r2, r3, lsr #3 f1c: 4613 mov r3, r2 f1e: ea4f 0383 mov.w r3, r3, lsl #2 f22: 189b adds r3, r3, r2 f24: ea4f 0343 mov.w r3, r3, lsl #1 f28: 1aca subs r2, r1, r3 f2a: b2d3 uxtb r3, r2 f2c: f103 0330 add.w r3, r3, #48; 0x30 f30: b2db uxtb r3, r3 f32: 7003 strb r3, [r0, #0] f34: 68fb ldr r3, [r7, #12] f36: f103 0301 add.w r3, r3, #1 f3a: 60fb str r3, [r7, #12] } while ((n /= 10) >= 1); f3c: 687a ldr r2, [r7, #4] f3e: f64c 43cd movw r3, #52429; 0xcccd f42: f6cc 43cc movt r3, #52428; 0xcccc f46: fba3 1302 umull r1, r3, r3, r2 f4a: ea4f 03d3 mov.w r3, r3, lsr #3 f4e: 607b str r3, [r7, #4] f50: 687b ldr r3, [r7, #4] f52: 2b00 cmp r3, #0 f54: d1d6 bne.n f04 <ItoA+0x10> //s[i] = '\0'; Reverse(s); f56: 6838 ldr r0, [r7, #0] f58: f7ff ff9a bl e90 <Reverse> }
void Reverse(char s[]) { int c, i, j;
for (i = 0, j = strlen(s)-1; i < j; i++ , j--) ed4: 697b ldr r3, [r7, #20] ed6: f103 0301 add.w r3, r3, #1 eda: 617b str r3, [r7, #20] edc: 693b ldr r3, [r7, #16] ede: f103 33ff add.w r3, r3, #4294967295 ee2: 613b str r3, [r7, #16] ee4: 697a ldr r2, [r7, #20] ee6: 693b ldr r3, [r7, #16] ee8: 429a cmp r2, r3 eea: dbe0 blt.n eae <Reverse+0x1e> c = s[i]; s[i] = s[j]; s[j] = c; } //s[i] = '\0'; } 38+10 = 48 инструкций.  Цитата(AHTOXA @ Jan 21 2015, 19:43)  Выбирайте!--- Упс, уже дали эту ссылку  да. CrimsonPig давал уже эту ссылку. есть интересное решение. надо проверить. в принципе int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0}; можно вынести из тела функции...
Сообщение отредактировал Jenya7 - Jan 21 2015, 14:23
|
|
|
|
|
  |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|