реклама на сайте
подробности

 
 
3 страниц V  < 1 2 3 >  
Reply to this topicStart new topic
> Показать число с leading zeros.
CrimsonPig
сообщение Jan 21 2015, 12:16
Сообщение #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
Go to the top of the page
 
+Quote Post
SM
сообщение Jan 21 2015, 12:37
Сообщение #17


Гуру
******

Группа: Свой
Сообщений: 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++]);
Go to the top of the page
 
+Quote Post
CrimsonPig
сообщение Jan 21 2015, 12:39
Сообщение #18


Местный
***

Группа: Участник
Сообщений: 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 только там, где знак нужет в явном виде.
Go to the top of the page
 
+Quote Post
Jenya7
сообщение Jan 21 2015, 12:45
Сообщение #19


Профессионал
*****

Группа: Участник
Сообщений: 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.
Go to the top of the page
 
+Quote Post
SM
сообщение Jan 21 2015, 12:47
Сообщение #20


Гуру
******

Группа: Свой
Сообщений: 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, то тут, к сожалению, С не покатит, так как нужно условие по флагу переноса после математической операции, что реализуемо только на ассемблере. Оптимизация, штука тонкая....
Go to the top of the page
 
+Quote Post
CrimsonPig
сообщение Jan 21 2015, 12:54
Сообщение #21


Местный
***

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



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


если почитать книжку "Hacker's delight" (она есть и в русском переводе) или опять же погуглить, то можно нарыть методов проверки операций над целыми числами на переполнение на чистом Ц.
там битхаки, завязанные на конкретную разрядность...
Go to the top of the page
 
+Quote Post
SM
сообщение Jan 21 2015, 12:57
Сообщение #22


Гуру
******

Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881



Цитата(CrimsonPig @ Jan 21 2015, 15:54) *
там битхаки, завязанные на конкретную разрядность...

Но это не оптимально. Разве что, только ради того, чтобы сделать это хоть как-то, но на С. Поэтому я не предлагаю таких решений в теме про оптимизацию алгоритма на скорость.
Go to the top of the page
 
+Quote Post
Jenya7
сообщение Jan 21 2015, 13:00
Сообщение #23


Профессионал
*****

Группа: Участник
Сообщений: 1 778
Регистрация: 29-03-12
Пользователь №: 71 075



Цитата(SM @ Jan 21 2015, 18:47) *
Это пусть автор разбирается. Я предпочитаю соблюдать старые добрые стандарты, где еще нет int32_t.


Это с какого перепуга? Тип не unsigned.
А если нужен полный диапазон unsigned, то тут, к сожалению, С не покатит, так как нужно условие по флагу переноса после математической операции, что реализуемо только на ассемблере. Оптимизация, штука тонкая....

неа. надо допиливать функцию. с uint32_t как раз работает просто надо добавить проверку что число "закончилось".
Go to the top of the page
 
+Quote Post
CrimsonPig
сообщение Jan 21 2015, 13:02
Сообщение #24


Местный
***

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



Цитата(SM @ Jan 21 2015, 12:57) *
Но это не оптимально. Разве что, только ради того, чтобы сделать это хоть как-то, но на С. Поэтому я не предлагаю таких решений в теме про оптимизацию алгоритма на скорость.


для этого существуют debug asserts, тесты и метрики code coverage
... вон, без проверок на переполнение Ариан (или кто там) долетался... и истребитель потом кверху лапками переворачивался при полете на высоте ниже уровня моря.
Go to the top of the page
 
+Quote Post
SM
сообщение Jan 21 2015, 13:05
Сообщение #25


Гуру
******

Группа: Свой
Сообщений: 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

для чего? Чтобы оптимально написать алгоритм на С, который на нем оптимально написать невозможно по причине недоступности флага переноса ? sm.gif sm.gif
Go to the top of the page
 
+Quote Post
Jenya7
сообщение Jan 21 2015, 13:24
Сообщение #26


Профессионал
*****

Группа: Участник
Сообщений: 1 778
Регистрация: 29-03-12
Пользователь №: 71 075



Цитата(SM @ Jan 21 2015, 19:05) *
Если же Вам хватит положительной части диапазона int32_t на все Ваши случаи, то ничего допиливать не надо, а использовать int32_t, на который рассчитан алгоритм.


и с int32_t не работает sm.gif
Go to the top of the page
 
+Quote Post
SM
сообщение Jan 21 2015, 13:28
Сообщение #27


Гуру
******

Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881



Цитата(Jenya7 @ Jan 21 2015, 16:24) *
и с int32_t не работает sm.gif

Чего там не работает? Сейчас в 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;
}


Go to the top of the page
 
+Quote Post
andrew_b
сообщение Jan 21 2015, 13:39
Сообщение #28


Профессионал
*****

Группа: Свой
Сообщений: 1 975
Регистрация: 30-12-04
Из: Воронеж
Пользователь №: 1 757



Цитата(CrimsonPig @ Jan 21 2015, 14:37) *
2. В цикле for (i = 0, j = strlen(s)-1; i < j; i++ , j--) есть наивное предположение, что компилятор вынесет strlen(s) за цикл как инвариант. В общем случае неверно. s передается как параметр в функцию и компилятор имеет право решить, что данные строки могут изменяться извне в другом треде, например. Поэтому с чистой совестью может оставить вызов strlen в каждой итерации цикла.
С какой стати? Это вычисляется один раз до входа в цикл. В противном случае это противоречит стандарту Си (ISO/IEC 9899, пункт 6.8.5.3), и такой компилятор надо выбросить.
Go to the top of the page
 
+Quote Post
AHTOXA
сообщение Jan 21 2015, 13:43
Сообщение #29


фанат дивана
******

Группа: Свой
Сообщений: 3 387
Регистрация: 9-08-07
Из: Уфа
Пользователь №: 29 684



Цитата(Jenya7 @ Jan 21 2015, 17:03) *
так нету библиотечных функций в том то и дело. и более лучшей генерик функции я не нашел.

Выбирайте!
---
Упс, уже дали эту ссылку sm.gif


--------------------
Если бы я знал, что такое электричество...
Go to the top of the page
 
+Quote Post
Jenya7
сообщение Jan 21 2015, 14:18
Сообщение #30


Профессионал
*****

Группа: Участник
Сообщений: 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;
}




офигеть! таки работает! sm.gif

а вот листинг двух функций
Код
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 инструкций.
sm.gif

Цитата(AHTOXA @ Jan 21 2015, 19:43) *
Выбирайте!
---
Упс, уже дали эту ссылку sm.gif


да. CrimsonPig давал уже эту ссылку. есть интересное решение. надо проверить.

в принципе int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0}; можно вынести из тела функции...

Сообщение отредактировал Jenya7 - Jan 21 2015, 14:23
Go to the top of the page
 
+Quote Post

3 страниц V  < 1 2 3 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 23rd July 2025 - 15:59
Рейтинг@Mail.ru


Страница сгенерированна за 0.01573 секунд с 7
ELECTRONIX ©2004-2016