Можно создать дубликат:
Best algorithm to count the number of set bits in a 32-bit integer?не Выяснить не установлены биты в переменной быстрее образом
Выяснить нет. битов в переменной легче. Но как мы можем выполнить ту же операцию в самом быстром методе?
Эта страница на Bit Twiddling Hacks охватывает несколько методов для подсчета количества установленных битов и обсуждает производительность каждого из них.
На странице bit twiddling hacks есть множество предложений.
int i, size, set;
for (i = 1, size = sizeof(int) * 8; i <= size; i++)
{
if (value & (0 << 2 * i)) set++;
}
Это наивный метод, на который, по-видимому, ссылался плакат, и попросил более быструю версию. – McPherrinM
Почему именно это «наивное»? – ChaosPandion
Наивный не означает оскорбление; это простой и очевидный способ, и есть умные быстрые клавиши, которые быстрее (см. бит Twiddling Hacks в других ответах). –
Если переменная представляет собой целое число, вы можете рассчитывать биты с помощью
public static int BitCount(int x)
{ return ((x == 0) ? 0 : ((x < 0) ? 1 : 0) + BitCount(x <<= 1)); }
Объяснение: Рекурсивный, если число равно нулю, биты не установлены, и функция возвращает ноль еще, он проверяет знаковый бит, и если набор содержит 1, то сохраняет 0, , затем сдвигает весь номер один бит влево , устраняя только что проверенный бит знака, и ставит нуль в самый правый бит, и снова вызывает себя с новым значением сдвига влево.
Общий результат состоит в том, чтобы исследовать каждый бит с самого левого на правый, и для каждого из них хранится в стеке, был ли установлен этот бит (как 1/0), left-Shits следующий бит в позицию бита значка и resurses. Когда он, наконец, дойдет до последнего установленного бита, значение будет равно нулю, и рекурсия остановится. Затем функция возвращает стек вызовов, добавляя все значения темпа, которые он хранил на пути вниз. Возврат всего
Это излишне тупое и будет медленнее, чем наивная реализация с циклом. – McPherrinM
Почему медленнее молиться? Операция сдвига влево означает, что она вернет AT MOST только количество бит в переменной, исследуя каждый бит один раз и только один раз. Это, как мне кажется, будет так же быстро или быстрее, чем любой другой алгоритм. –
Вызов процедуры вызовет еще около дюжины инструкций по настройке и разрыву кадра стека в зависимости от настроек компилятора. –
Если вы задаете вопрос, тогда шансы __builtin_popcount на gcc по крайней мере так же быстро, как и то, что вы сейчас делаете. __builtin_popcount обычно может быть избит на x86, поэтому, предположительно, на других процессорах, но вы не говорите, что ваш процессор отличается от «встроенного». Это влияет на ответ.
Если вы не используете gcc, вам нужно посмотреть, как сделать быстрый popcount на вашем реальном компиляторе и/или процессоре. По понятным причинам нет такой вещи, как «самый быстрый способ подсчета бит в C».
Подсчитывание множества бит в переменной называется «подсчет количества населения», сокращенный до «popcount».
Очень хороший микро-тест различных программных алгоритмов приведен в: http://www.dalkescientific.com/writings/diary/archive/2008/07/05/bitslice_and_popcount.html
AMD «Барселона» процессоры, начиная иметь быструю инструкцию фиксированной стоимости, которая в GCC вы можете получить с помощью __builtin_popcount
На Intel я обнаружил, что __builtin_ffs в цикле лучше всего работает для разреженных наборов бит.
Его то, на что вы не можете положиться; вы должны выполнить микро-тест, если это важно для вас.
Я настоятельно рекомендую прочитать Hacker's Delight по всем вопросам, касающимся различных форм бит-скручивания. Для подсчета битов, в частности, он анализирует несколько алгоритмов в зависимости от инструкций, которые могут вам быть доступны.
Найдено дубликатов: http: // stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer – McPherrinM
Какой метод вы используете? Если вы разместили код, который используете в настоящее время, мы можем оказать вам дополнительную помощь. – jkndrkn