Также рассмотрите встроенные функции ваших компиляторов.
В компиляторе GNU, например, вы можете просто использовать:
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);
В худшем случае компилятор будет генерировать вызов функции. В лучшем случае компилятор будет генерировать инструкцию cpu для выполнения той же самой работы быстрее.
Внутренние возможности GCC даже работают на нескольких платформах. Popcount станет основной темой в архитектуре x86, поэтому имеет смысл начать использовать внутреннее значение.
На x86 вы можете сказать компилятору, что он может считать поддержку команды popcnt
с -mpopcnt
или -msse4.2
, чтобы также включить векторные инструкции которые были добавлены в том же поколении. См. Параметры GCC x86 . -march=nehalem
(или -march=
независимо от того, какой процессор вы хотите, чтобы ваш код принимал и настраивал) мог бы быть хорошим выбором. Запуск результирующего двоичного файла на более старом процессоре приведет к ошибке с неправильной инструкцией.
Чтобы сделать бинарные файлы оптимизированными для машины, на которой вы их построили, используйте -march=native
(с gcc, clang или ICC).
MSVC обеспечивает встроенную команду x86 popcnt
, но в отличие от gcc она действительно является неотъемлемой частью аппаратной инструкции и требует аппаратной поддержки.
Использование std::bitset<>::count()
вместо встроенного
Теоретически любой компилятор, который умеет эффективно собирать данные для целевого ЦП, должен раскрывать эту функциональность через ISO C ++ std::bitset<>
. На практике вам может быть лучше с бит-взломом AND / shift / ADD в некоторых случаях для некоторых целевых ЦП.
Для целевых архитектур, где аппаратный popcount является дополнительным расширением (например, x86), не все у компиляторов есть std::bitset
, который использует его, когда он доступен. Например, MSVC не имеет возможности включить поддержку popcnt
во время компиляции и всегда использует поиск в таблице , даже с /Ox /arch:AVX
(что подразумевает SSE4.2, хотя технически существует отдельная функция бит для popcnt
.)
Но по крайней мере вы получаете что-то портативное, которое работает повсюду, и с помощью gcc / clang с правильными целевыми параметрами вы получаете аппаратный popcount для архитектур, которые его поддерживают.
#include
#include
#include
template
//static inline // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if::value, unsigned >::type
popcount(T x)
{
static_assert(std::numeric_limits::radix == 2, "non-binary type");
// sizeof(x)*CHAR_BIT
constexpr int bitwidth = std::numeric_limits::digits + std::numeric_limits::is_signed;
// std::bitset constructor was only unsigned long before C++11. Beware if porting to C++03
static_assert(bitwidth <= std::numeric_limits::digits, "arg too wide for std::bitset() constructor");
typedef typename std::make_unsigned::type UT; // probably not needed, bitset width chops after sign-extension
std::bitset bs( static_cast(x) );
return bs.count();
}
См. asm из gcc, clang, icc и MSVC в проводнике компилятора Godbolt.
x86-64 gcc -O3 -std=gnu++11 -mpopcnt
испускает это:
unsigned test_short(short a) { return popcount(a); }
movzx eax, di # note zero-extension, not sign-extension
popcnt rax, rax
ret
unsigned test_int(int a) { return popcount(a); }
mov eax, edi
popcnt rax, rax
ret
unsigned test_u64(unsigned long long a) { return popcount(a); }
xor eax, eax # gcc avoids false dependencies for Intel CPUs
popcnt rax, rdi
ret
PowerPC64 gcc -O3 -std=gnu++11
испускает (для версии int
arg]:
rldicl 3,3,0,32 # zero-extend from 32 to 64-bit
popcntd 3,3 # popcount
blr
Этот источник не является специфичным для x86 или вообще GNU, но только хорошо компилируется для x86 с gcc / clang / icc.
Также обратите внимание, что резервное копирование gcc для архитектур без однопользовательского popcount представляет собой поиск по байтам по времени. Это не удивительно для ARM, например .