| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Как? |
| Автор: creation 4.6.2008, 17:46 |
| Нужно создать быстрый алгоритм для подсчета числа 1 и 0 в десятичном числе... Т. е. есть число, например, 8 - в двоичном виде это 1000 И надо определить число 1 и 0 в двоичном виде... Т. е. одна единица три нуля. Самый первый, который пришел в голову - это в цикле делать смещение бита на первое место (правое), обнулять остальные биты и проверять что получили 1 или 0 и считать... Но алгоритм медленный - проход в цикле... Есть еще какие более простые? |
| Автор: mes 4.6.2008, 18:01 | ||||
для 8битного числа возврашает кол-во единиц.
Добавлено через 57 секунд за сегодня третий вопрос по битовым операциям.. )) Добавлено через 2 минуты и 28 секунд название у темы крутое..такое понятное и ясное.. аж на душе приятно Добавлено через 3 минуты и 14 секунд а вообше попробуй пользоваться поиском - найдешь много чего интересного |
| Автор: Fazil6 4.6.2008, 18:09 | ||
самый простой и быстрфй способ - задать массив нужной величины и занести в него подсчитанное значение для каждого числа, используя число как индекс. Потом просто по индексу доставать нужный результат |
| Автор: Alek86 4.6.2008, 18:11 | ||
| http://forum.vingrad.ru/forum/topic-210832/view-all.html с помощью одного из тех вариантов решения, думаю, можно ускорить решение mes'а Добавлено @ 18:12
для инта жесткий массив будет лучше уж по байтам разбивать число и массив из 256 элементов Добавлено @ 18:13  представил, как программер вводит значения для массива на 4 мильярда элементов  |
| Автор: creation 4.6.2008, 18:13 |
| Спасибо mes! Но это тот же алгоритм, что и мой...  У тебя цикла нет, просто... Насчет занести в массив числа с нужным количеством 1 и 0 хорошая идея, но ресурсоемкая, так как массивы будут очень большие... Нужен быстрый способ, расчета на лету... В целом понимаю, что скорее всего придеться использовать то, что в голову самому и пришло и что тоже самое немного по другому оформил mes... Я думал есть какая нибудь одна формула, которая сможет выдать число единиц... |
| Автор: Alek86 4.6.2008, 18:14 | ||
если по байтам разбить, то в самый раз |
| Автор: vinter 4.6.2008, 18:17 |
| bitset, vector<bool> |
| Автор: ama_kid 4.6.2008, 18:20 | ||
 |
| Автор: creation 4.6.2008, 18:43 | ||||
Уже прочитал, уже реализовал... Всем спасибо! |
| Автор: mes 4.6.2008, 18:45 | ||
вот противопример : size_t func (int16 source ) { static size_t bits4count[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3, 4 }; return bits4count[bits4count[ ( source) & 0xff ] ) +bits4count[bits4count[ ( source >>4) & 0xff ] ) +bits4count[bits4count[ ( source >> 8) & 0xff ] ) +bits4count[bits4count[ ( source >>12) & 0xff ] ); } Добавлено через 6 минут и 56 секунд но решение приведенное в книжке более эффективное - тка как не обрашается к памяти .. |
