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

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

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

Hamming weight из Wikipedia.

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

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

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

Отправить комментарий