понедельник, 17 октября 2011 г.

[prog] Склерозник: подсчет числа единичных битов в N-битовой последовательности

Никогда раньше не приходилось с такой задачкой сталкиваться, поэтому при встрече соответствующих материалов просто пропускал их. А теперь потребовалось и пришлось делать поиск по Интернету. В результате поверхностного поиска нашлось вот что:

Hamming weight из Wikipedia.

Fast Bit Counting (форматирование в примерах кода “поплыло”, но при желании разобраться можно).

Bit Twiddling Hacks (пожалуй, самое внушающее собрание).

PS. Поскольку мне эффективность в данном случае не сильно нужна, то я, пожалуй, обойдусь простым использованием std::bitset::count(), хоть стандарт и не оговаривает требований по эффективности ее реализации.

3 комментария:

jazzer комментирует...

В SSE4 есть соответствующая инструкция.

имя комментирует...

как всегда http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer

в т.ч. и про инструкцию SSE4

eao197 комментирует...

@имя:

Ну, собственно, отправными точками стали Google, Wikipedia и StackOverflow. Просто решил оставить те ссылки, которые мне показались наиболее информативными и практически полезными.