Это одна из известных задачек, которую задают на собеседованиях: дано беззнаковое целое число, надо подсчитать количество бит, установленных в единицу. Как это сделать как можно быстрее?
Самый простой вариант - тупо пройтись по числу и проверить каждый бит. О скорости тут речь не идет. Несколько быстрее будет проверять последний бит, затем использовать операцию сдвига и после каждого сдвига проверять исходное число на 0.
Дела пойдут гораздо быстрее, если предподсчитать количество единиц. Это можно сделать для 8-битовых и 16-битовых целых, дальше уже сложнее...
На страничке Counting Number of On Bits in an Integer есть эти и другие, более мудрёные варианты решения этой задачи, все с примерами кода и с сравнением по скорости. Предподсчет быстрее всех.
воскресенье, июля 02, 2006
Подсчет количества установленных битов в беззнаковом целом
Подписаться на:
Комментарии к сообщению (Atom)
Atom feed
12 коммент.:
Эх. Где же Вы раньше были? =) Пару месяцев назад ломал голову, как быстрее биты считать =)
Теперь задача хоть и осталась актуальна, но не срочна...
А ссылочка ушла в del.icio.us
Благодарю премного =)
Есть замечательная книжка Уоррена -- "Алгоритмические трюки для программистов". Там описывается про подобные битовые действия, как их быстро совершить: напр., подсчет числа битов, поиск левого единичного бита, переворот битов и т. п.
(на Озоне)
dragula, знаю, была у меня такая. Но куда я её задевал ума не приложу. Видимо как обычно, дал кому-то почитать и...
+1 (вроде такого способа на страничке той нет - тоже очень быстр)
int zzCTPop(unsigned int Map)
{
const static unsigned int SK5=0x55555555,SK3=0x33333333;
const static unsigned int SKF0=0xF0F0F0F,SKFF=0xFF00FF;
Map-=((Map>>1)&SK5);
Map=(Map&SK3)+((Map>>2)&SK3);
Map=(Map&SKF0)+((Map>>4)&SKF0);
Map+=Map>>8;
return (Map+(Map>>16))&0x3F;
}
Эта задача встречается в шифровании, часто для того, что бы сранить два текста и посчитать сколько процентов битов изменено
Не перестаю удивлятся программистам Коллеги!!! кого в нашу эпоху волнует вопрос скорости? Это к стате касается и контэйнеров. С таким требованием пора переходить или возвращатся к ассемблеру.
Не устраивает скорость купите еще один процессор.
Не перестаю удивлятся программистам Коллеги!!! кого в нашу эпоху волнует вопрос скорости?
В играх, например, это проявляется в виде низкого FPS, что волнует и игроков, и разработчиков.
Не устраивает скорость купите еще один процессор.
Такой подход с большой вероятностью приведет к потере пользователя.
А что весь программный продукт - это игры???? Они расчитаны на локального пользователя и не могут быть аргументом даже если и являются сложными системами. Другое дело мощные приложения для промышленных структур, которое состоит из 20 тисяч строк кода. Вот пример - мы разрабатываем приложения для банка, вы работаете три месяца и оптимизируете продукт по скорости и требованиям системы, я работаю тоже время и создаю сверх надежное но более медленное приложение. Вопрос - кого бросит пользователь, то есть банкир? Быстрое или надежное приложение? Думаю ответ очевиден. Поднимать вопрос скорости означает откат на 20 лет назад. Само понятие ООП отвергает проблему малой скорости, а поддерживает надежность и еще кучу всего...вы наверно знаете это лучше меня...
Здесь лежат вариации решений типичных задач, связанных с побитовыми операциями: Bit Twiddling Hacks. Довольно интересно...
Вот бесспорно самый быстрый вариант - POPCNT ( http://ru.wikipedia.org/wiki/SSE4#.D0.9F.D0.BE.D0.B4.D1.81.D1.87.D0.B5.D1.82_.D0.BF.D0.BE.D0.BF.D1.83.D0.BB.D1.8F.D1.86.D0.B8.D0.B8_.D0.B5.D0.B4.D0.B8.D0.BD.D0.B8.D1.87.D0.BD.D1.8B.D1.85_.D0.B1.D0.B8.D1.82 )
Эх((( Мой процессор поддерживает вплоть до SSE4.1 . . .
Скептик комментирует...
А что весь программный продукт - это игры????
Вот как раз поэтому так "любят" банковских программеров и именно поэтому сейчас, для того чтоб тянуло интернет приложения, нужен "процессор";) более мощный, чем для самых требовательных игр.
Скептик, задам ответный вопрос. По Вашему что, все программные продукты – это банковские приложения? Нет? Нет!
Так что не болтайте пожалуйста о том, о чем имеете слабое представление. Оптимизация и выжимание 100% мощи используется далеко не только в играх. Браузеры, кодеки, видеоплееры, машинное зрение, робототехника, embedded, САПР, ГИС, криптография, крупнокалиберное сетевое оборудование.
А вот благодаря таким как Вы, а–ля "банковский соооофт! все что иначе – это прыжок на 20 лет назад", телефоны и банкоматы начинают работать все задумчивее с каждым годом, несмотря на рост вычислительной мощи.
Отправить комментарий