Каков самый быстрый способ подсчитать все установленные биты?
Как быстрее всего подсчитать все установленные биты?
Число, от которого я считаю биты, от 1<=n<2^63, только положительные значения.
На данный момент я использую набор битов из библиотеки, и это довольно быстро, но если есть более быстрый вариант, я хотел бы знать.
В худшем случае у меня будет более 1 миллиарда итераций, поэтому я ищу способ ускорить его.
Это часть моего цикла, где я подсчитываю установленные биты:
if (std::bitset<64>(currentNumber).count() == numofOnes)
++counter;
Если у вас нет std::popcount() из C++20, см. stackoverflow.com/questions/109023/…
Отвечает ли это на ваш вопрос? Как посчитать количество установленных битов в 32-битном целом? - там указан 64-битный ответ, хотя в заголовке указано 32 бита.
Честно говоря, этот вопрос устарел. В настоящее время все компиляторы так или иначе поддерживают встроенные функции popcnt, уродливый битхак, который является первым ответом, больше не полезен и может быть даже медленнее. — так что, если вы идете по этой ссылке, прокрутите ее.
Я не фанат "быстрых" вопросов. Чтобы проиллюстрировать, почему и что этот вопрос можно улучшить, позвольте мне предложить для обсуждения следующий ответ: самый быстрый способ — это либо таблица поиска (не для всего диапазона, но иерархически сбалансированная), либо механизм подсчета битов с аппаратной поддержкой. Теперь, пожалуйста, объясните, почему эти два варианта не являются для вас ответом.
Мне очень нравится идея справочной таблицы. Трудно превзойти его по скорости. Займите немного места для хранения.
Вариант __builtin_popcount медленнее, чем битсет stackoverflow.com/questions/60165922/… Мне придется использовать таблицу поиска, спасибо.
Таблица поиска решила мой вопрос, спасибо за совет.
@user4581301 user4581301 Размер таблицы поиска можно масштабировать или можно «сбалансировать».
@Yunnosch Да, но они медленнее, чем полная таблица поиска. Аскер хотел самый быстрый, а не самый быстрый с разумной реализацией.
@MrRobot: Если вы видите комментарии к ответу, на который вы ссылаетесь, «более медленный» результат, вероятно, является артефактом теста, поскольку фактический код сборки одинаков для обоих.
Hamming Weight не требует большого объема памяти и работает довольно быстро.
@user4581301 user4581301 На самом деле я хотел спровоцировать, упомянув полноразмерную таблицу поиска (очевидно, это не ответ), а затем не смог устоять перед мудрецом о возможности масштабировать ее и сбалансировать скорость и размер. А, ну получился достойный ответ.
Ответы 1
Вот демонстрация того, что я имею в виду под сбалансированной таблицей поиска.
Этот сильно экономит размер.
Вы можете адаптировать концепцию к таблицам поиска размера, например. 64 или 256, значительно ускоряясь.
#include <iostream>
using namespace std;
int main()
{
unsigned long long int input=679043ULL; // just a big number, for demo
unsigned char lookup[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
unsigned char result=0;
while (input>0)
{
cout << (unsigned int) result << " " << (input&15) << " " << input << endl;
result+=lookup[input&15];
input>>=4;
}
cout << (unsigned int)result << endl;
return 0;
}
Выход:
0 3 679043
2 8 42440
3 12 2652
5 5 165
7 10 10
9
Выходные данные демо показывают, что цикл накапливается
2 бита в "3",
1 бит в "8",
2 бита в "12",
2 бита в "5",
два бита в "10";
всего 9.
Может быть, std::popcount()? (Нужны эксперименты)