Здравствуйте, bin-tm, Вы писали:
BT>Не подскажет кто как можно в С быстренько определить сколько нужных символов (char), чтобы хранить целое число.
BT>Например, есть число 12. Результат должен быть 2. Для 4 — результат 1. И т.д.
BT>Ничего кроме десятичного логарифма в голову не приходит! Че-то туплю. Почти уверен, что можно как-то совсем просто!!!
BT>itoa и прочие извраты типа strlen не предлагать
BT>Спасибо!
Легкий оффтоп, но афайк у числа "12" char длиной 3, а не два.. ибо в конце \0. Хотя я могу ошибаться
BT>Не подскажет кто как можно в С быстренько определить сколько нужных символов (char), чтобы хранить целое число. BT>Например, есть число 12. Результат должен быть 2. Для 4 — результат 1. И т.д. BT>Ничего кроме десятичного логарифма в голову не приходит! Че-то туплю. Почти уверен, что можно как-то совсем просто!!!
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, bin-tm, Вы писали:
BT>>Ничего кроме десятичного логарифма в голову не приходит!
А>А что может быть проще десятичного логарифма?
А>Ну можешь еще сам цикл сделать и в нем на 10 делить.
Это и есть простейшая реализация целочисленного десятичного логарифма. Хотя чаще используют умножение на 10 — возводят десять поледовательно в степени 1, 2, 3, т.д., и проверяют на больше. Умножение быстрее просто.
Здравствуйте, bin-tm, Вы писали:
BT>Не подскажет кто как можно в С быстренько определить сколько нужных символов (char), чтобы хранить целое число. BT>itoa и прочие извраты типа strlen не предлагать
А нафик вообще считать, сколько char нужно? И почему не TCHAR, например? И кто знает, может вы число прописью хотите, тогда попутно возникает вопрос: на каком языке пропись выводить и в какой кодировке, скажем.
По теме же: для четырехбайтового числа имхо char[11] хватит, учитывая завершающий нуль. Это навскидку, мог ошибиться, но не сильно.
Re[2]: количество чисел в представлении целого числа
Здравствуйте, Flamer, Вы писали:
F>А нафик вообще считать, сколько char нужно? И почему не TCHAR, например? И кто знает, может вы число прописью хотите, тогда попутно возникает вопрос: на каком языке пропись выводить и в какой кодировке, скажем.
Пусть сам решает.
F>По теме же: для четырехбайтового числа имхо char[11] хватит, учитывая завершающий нуль. Это навскидку, мог ошибиться, но не сильно.
ИМХО. Самый рациональный путь. Т.е. всё равно в строку переводить придётся. А уж потом можно выделить ровно столько сколько надо и туда скопировать.
Вообще было обсуждение подобного вопроса на просторах КЫВТа, найдите, кто помнит.
Сам думал о BSR, но эта сабака сама по себе тормознутая.
Только не надо умножений, и, тем более, делений...
Можно забабахать массивчик степеней 10-ки и по нему двоичным поиском. Хотя всё зависит от распределения чисел.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[2]: количество чисел в представлении целого числа
F>>По теме же: для четырехбайтового числа имхо char[11] хватит, учитывая завершающий нуль. Это навскидку, мог ошибиться, но не сильно.
I>для отрицательного не хватит. -2^31
Я ж говорил, что навскидку Знак забыл.
<< Не присоединяйся к нашему миру наркоманов: нас много, а наркоты мало. >>
Re[3]: количество чисел в представлении целого числа
VEA>Можно забабахать массивчик степеней 10-ки и по нему двоичным поиском. Хотя всё зависит от распределения чисел.
int f(int i)
{
int l = 0;
if (i < 0)
{
++l;
i *= -1;
}
if ( i < 10*10*10*10*10*10 )
if ( i < 10*10*10 )
if ( i < 10*10 )
if ( i < 10 )
l += 1;
else
l += 2;
else
l += 3;
else
if ( i < 10*10*10*10*10 )
if ( i < 10*10*10*10 )
l += 4;
else
l += 5;
else
l += 6;
else
if ( i < 10*10*10*10*10*10*10*10 )
if ( i < 10*10*10*10*10*10*10 )
l += 7;
else
l += 8;
else
if ( i < 10*10*10*10*10*10*10*10*10*10 )
if ( i < 10*10*10*10*10*10*10*10*10 )
l += 9;
else
l += 10;
else
l += 11;
return l;
}
надеюсь отсутствие скобок не помешает правильной работе , вроде как все по правилам
Re[4]: количество чисел в представлении целого числа
Здравствуйте, Flamer, Вы писали:
F>Здравствуйте, ilnar, Вы писали:
F>>>По теме же: для четырехбайтового числа имхо char[11] хватит, учитывая завершающий нуль. Это навскидку, мог ошибиться, но не сильно.
I>>для отрицательного не хватит. -2^31
F>Я ж говорил, что навскидку Знак забыл.
Re[4]: количество чисел в представлении целого числа
I>int f(int i)
...
I> if ( i < 10*10*10*10*10*10 )
...
I>
Может, не очень изящно, но зато шустро — быстрее, наверное, получится только при использовании здоровых Lookup-таблиц, да и то не факт.
Кстати, ИМХО лучше перебалансировать дерево, взяв первое сравнение не 10^6, а 10^4 — всё-таки, по жизни небольшие числа встречаются гораздо чаще.
Re[5]: количество чисел в представлении целого числа
I>>int f(int i)
a18>...
I>> if ( i < 10*10*10*10*10*10 )
a18>...
I>>
a18>Может, не очень изящно, но зато шустро — быстрее, наверное, получится только при использовании здоровых Lookup-таблиц, да и то не факт.
имхо, точно не факт. тут максимум 4 сравнения, если предугадывание в среднем ошибется 2 раза, то результат получите за 2-3 длины конвейера процессора. даже если всегда ошибется, то за 4-5, пусть длина равна 20, результат в руках за 100 тактов.
за это время можно достучаться только до кеша (разных уровней, приблизительно), а там памяти маловато будет ((
смотря какие лукапы делать
a18>Кстати, ИМХО лучше перебалансировать дерево, взяв первое сравнение не 10^6, а 10^4 — всё-таки, по жизни небольшие числа встречаются гораздо чаще.
пока данные не увидешь, приходится считать их равномерно распределенными.
все зависит от цели.
пусть есть 2 лифта. всего 15 этажей. один лифт на 10 этаже. другой на 15. стоит ли последний спустить куда нибудь?
если цель в минимизации затрат, то не стоит. если цель скорости обслуживания, то стоит спустить на 4-й этаж.
Re[6]: количество чисел в представлении целого числа
Здравствуйте, ilnar, Вы писали:
I>пока данные не увидешь, приходится считать их равномерно распределенными.
Тогда и сравнивать лучше начинать с 10^9, там же 3/4 чисел
потом 10^8,7,6... Если цикл, то максимум 2 ошибки.
Кто может посмотреть на такты BSR, после неё одно сравнение остаётся...
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[6]: количество чисел в представлении целого числа
a18>>Может, не очень изящно, но зато шустро — быстрее, наверное, получится только при использовании здоровых Lookup-таблиц, да и то не факт.
I>имхо, точно не факт. тут максимум 4 сравнения, если предугадывание в среднем ошибется 2 раза, то результат получите за 2-3 длины конвейера процессора. даже если всегда ошибется, то за 4-5, пусть длина равна 20, результат в руках за 100 тактов. I>за это время можно достучаться только до кеша (разных уровней, приблизительно), а там памяти маловато будет (( I>смотря какие лукапы делать
Собственно, на мысль о лукапах натолкнул тот факт, что если взять 32-битное целое (для простоты — без знака), то по старшей половине (старшие два байта) из 65536 вариантов только в 6-ти случаях придётся анализировать ещё и младшую половину (hex: 0000, 0001, 000F, 0098, 05F5, 3B9A, если не ошибся), а во всех остальных 65530-ти случаях результат можно сразу вытащить из заранее подготовленной таблички.
Но вот насколько удачно это можно реализовать с учётом кешей — фиг знает.
Наверное, вряд ли это оправданно, ибо сама задача ИМХО довольно надуманная.
a18>>Кстати, ИМХО лучше перебалансировать дерево, взяв первое сравнение не 10^6, а 10^4 — всё-таки, по жизни небольшие числа встречаются гораздо чаще. I>пока данные не увидешь, приходится считать их равномерно распределенными.
Да, сорри, я почему-то решил взять медиану по выходу (1-10 цифр без знака), а не по входу (4 млрд. чисел).
Re[4]: количество чисел в представлении целого числа
если уж оптимизироваться, тогда в x86 процах есть команда получения первого установленного бита (слева и/или справа)
думаю, получив индексы первых двух единиц, можно сказать. подумать надо.
Здравствуйте, bin-tm, Вы писали:
BT>Не подскажет кто как можно в С быстренько определить сколько нужных символов (char), чтобы хранить целое число.
BT>Например, есть число 12. Результат должен быть 2. Для 4 — результат 1. И т.д.
BT>Ничего кроме десятичного логарифма в голову не приходит! Че-то туплю. Почти уверен, что можно как-то совсем просто!!!
BT>itoa и прочие извраты типа strlen не предлагать
BT>Спасибо!
Провел исследование.
Возьмем индекс самого старшего установленного бита, idx, отсчет от нуля
Переходы на следующий символ происходят при ((idx % 10) % 3)==0 -- это верно хотя бы до 64битных чисел. для больших может появится изменение начиная с некоторого бита будет условие (((idx-1) % 10) % 3)==0, это связано с 2^10=1024 (цифры 10 и 3 отсюда), тенденцию может поменять 24 на хвосте
При этом на переход влияют установленность битов idx-1 и idx-2 -- если любой из них установлен, то происходит переход
алгоритм для числа num:
1. получить idx для num
2. len = idx/10*3
3. if (((idx % 10) % 3)==0 && (num>>(idx-2))) ++len;
4. вернуть len
для Intel 80x86 есть команда процессора, котрый дает idx по num, называется bsr (bit scan reverse)
, вроде как все по правилам 
