Никогда раньше не приходилось с такой задачкой сталкиваться, поэтому при встрече соответствующих материалов просто пропускал их. А теперь потребовалось и пришлось делать поиск по Интернету. В результате поверхностного поиска нашлось вот что:
Hamming weight из Wikipedia.
Fast Bit Counting (форматирование в примерах кода “поплыло”, но при желании разобраться можно).
Bit Twiddling Hacks (пожалуй, самое внушающее собрание).
PS. Поскольку мне эффективность в данном случае не сильно нужна, то я, пожалуй, обойдусь простым использованием std::bitset::count(), хоть стандарт и не оговаривает требований по эффективности ее реализации.
3 комментария:
В SSE4 есть соответствующая инструкция.
как всегда http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer
в т.ч. и про инструкцию SSE4
@имя:
Ну, собственно, отправными точками стали Google, Wikipedia и StackOverflow. Просто решил оставить те ссылки, которые мне показались наиболее информативными и практически полезными.
Отправить комментарий