#ifdef __GNUC__, используйте __builtin_ctz(unsigned). ( GCC manual ). GCC, clang и ICC поддерживают его на всех целевых ISA. (На ISA, где нет собственной инструкции, она вызовет вспомогательную функцию GCC.)
Для 64-разрядных целых чисел используйте __builtin_ctzll(unsigned long long). К сожалению, встроенные битовые сканы GNU C не принимают типы фиксированной ширины (особенно конечные нули), но unsigned всегда 32-битный в GNU C для x86 (хотя не для AVR или MSP430). unsigned long long всегда uint64_t для всех известных мне целей GNU C.
На x86 он компилируется в bsf или tzcnt в зависимости от настройки + целевые параметры. tzcnt - это один моп с задержкой в 3 цикла на современном Intel, и только 2 моп с задержкой в 2 цикла на AMD (возможно, с обратной скоростью для подачиa lzcnt uop?) https://agner.org/optimize/. В любом случае он напрямую поддерживается быстрым оборудованием и намного быстрее, чем все, что вы можете сделать в чистом C ++ .
Встроенное поведение имеет неопределенное поведениедля входов без установленных битов, что позволяет избежать каких-либо дополнительных проверок, если он может работать как bsf.
В других компиляторах (в частности, MSVC), вы можете захотеть встроенную функцию для TZCNT, например _mm_tzcnt_32 от immintrin.h. ( Руководство по встроенным функциям Intel ). Или вам может потребоваться включить intrin.h (MSVC) или x86intrin.h для встроенных функций без SIMD.
TZCNT декодировать как BSF на процессорах без BMI1, потому что его машинный кодкодировка rep bsf. Они дают идентичные результаты для ненулевых входных данных, поэтому компиляторы всегда могут использовать tzcnt, потому что это намного быстрее для AMD. (Они одинаковы для Intel, поэтому у них нет недостатков. А на Skylake и более поздних версиях tzcnt не имеет ложной зависимости вывода. BSF делает, потому что оставляет свой вывод неизмененным для input = 0).
(Ситуацияменее удобно для bsr по сравнению с lzcnt: bsr возвращает битовый индекс, lzcnt возвращает счетчик начальных нулей, поэтому для лучшей производительности на AMD вы должны знать, что ваш код будет работать только на процессорах, поддерживающих BMI1 / TBMпоэтому компилятор может использовать lzcnt)
Обратите внимание, что при установленном ровно 1 бите сканирование в любом направлении обнаружит один и тот же бит . Итак 31 - lzcnt = bsr = bsf = tzcnt. Возможно, это полезно, если портировать на другой ISA, который имеет только счетчик начального нуля и не имеет инструкции обратного бита.
Связанный:
- https://en.wikipedia.org/wiki/Find_first_set больше оБитскан работает через ISA. Включая POSIX
ffs(), который возвращает индекс на основе 1 и должен выполнять дополнительную работу, чтобы учесть возможность ввода равным 0.
Компиляторы распознают ffs() и вставляют его как встроенный(как они делают для memcpy или sqrt), но не всегда удается оптимизировать всю работу, которую выполняет их постоянная последовательность, чтобы реализовать ее, когда вам действительно нужен индекс на основе 0. Особенно сложно сказать компилятору, что установлен только 1 бит.