Найти первый набор

В компьютерном программном обеспечении и аппаратном обеспечении найдите первый набор ( FFS ) или найдите первым, что является битой , которая, с учетом слова без знака , Определяет индекс или положение наименее значимого бита, установленного в одном из слов, подсчитывающего из наименее значимой битовой позиции. Почти эквивалентная операция - это подсчет, следящий за нулями ( CTZ ) или количество зацепленных нулей ( NTZ ), которое подсчитывает количество нулевых битов после наименьшего значительного бита. Дополнительная операция, которая находит индекс или положение наиболее значимого настройки, является базой журнала 2 , так называемой, поскольку она вычисляет двоичный логарифм ⌊log ₂ (x) ⌋ . Это тесно связано с ведущим количеством нулей ( CLZ ) или количеством ведущих нулей ( NLZ ), которое подсчитывает количество нулевых битов, предшествующих наиболее значимому биту. Существует два общих варианта Find First Set, определение POSIX , которое начинает индексировать биты в 1, Здесь помечено FFS, и вариант, который начинает индексировать биты в нуле, что эквивалентно CTZ и, таким образом, будет вызвано этим именем.

Большинство современных архитектур набора инструкций процессора предоставляют один или несколько из них в качестве операторов оборудования; Эмуляция программного обеспечения обычно предоставляется для любого, что недоступно, либо в качестве внутренней компилятора , либо в системных библиотеках .

Примеры

Учитывая следующее 32-битное слово:

0000 0000 0000 0000 1000 0000 0000 1000

Операция с подсчетом Zeros вернется 3, в то время как операция, ведущая в лидировании Zeros. Полем Операция Find First Set вернет 4, указывающая на 4 -ю позицию справа. Усеченное базовое логарифмическое основание 2 составляет 15.

Точно так же, учитывая следующее 32-битное слово, бить отрицание приведенного выше слова:

1111 1111 1111 1111 0111 1111 1111 0111

Операция по графу следов вернется 3, операция ведущих графов вернет 16, а первая ноль -операция FFZ вернет 4.

Если слово равна нулю (не установленные биты), графы, ведущие нули и граф, следуя нули, оба возвращают количество битов в слово, в то время как FFS возвращает ноль. Оба логических базовых и нулевых реализации Find First Set обычно возвращают неопределенный результат для нулевого слова.

Аппаратная поддержка

Многие архитектуры включают в себя инструкции по быстрому выполнению первого набора и/или связанных с ним операций, перечисленных ниже. Наиболее распространенной работой является ведущий подсчет нулей (CLZ), вероятно, потому что все другие операции могут быть выполнены эффективно с точки зрения ИТ (см. Свойства и отношения ).

Платформа	Мнемоник	Имя	Ширина операнда	Описание	При применении на 0
ARM ( ARMV5T Architecture, а затем ) За исключением Cortex-M0/M0+/M1/M23	CLZ	Граф ведущих нулей	32	CLZ	32
ARM ( ARMV8-A Architecture )	CLZ	Граф ведущих нулей	32, 64	CLZ	Ширина операнда
AVR32	CLZ	Граф ведущих нулей	32	CLZ	32
Dec Alpha	ctlz	Граф ведущих нулей	64	CLZ	64
	Cttz	Граф следы за нули	64	CTZ	64
Intel 80386 , а затем	BSF	Бит сканировать вперед	16, 32, 64	CTZ	Неопределенный; Устанавливает нулевой флаг
	BSR	Бит сканировать обратное	16, 32, 64	Bog Base 2	Неопределенный; Устанавливает нулевой флаг
x86 поддерживает BMI1 или ABM	lzcnt	Граф ведущих нулей	16, 32, 64	CLZ	Ширина операнда; Наборы несут флаг
x86 Поддерживаю BMI1	tzcnt	Граф следы за нули	16, 32, 64	CTZ	Ширина операнда; Наборы несут флаг
Итания	CLZ	Граф ведущих нулей	64	CLZ	64
MIPS32/MIPS64	CLZ	Считайте лидирующие нули в словах	32, 64	CLZ	Ширина операнда
	Clo	Считайте ведущие слова	32, 64	Clo	Ширина операнда
Motorola 68020 , а затем	BFFFO	Найдите первое в поле бит	Произвольный	Bog Base 2	Смещение поля + ширина поля
PDP-10	Jffo	Прыгай, если найти первым	36	CLZ	0; Нет операции
Power / PowerPC / Power ISA	cntlz/cntlzw/cntlzd	Граф ведущих нулей	32, 64	CLZ	Ширина операнда
Power ISA 3.0, а затем	cnttzw/cnttzd	Граф следы за нули	32, 64	CTZ	Ширина операнда
RISC-V ("B" расширение)	CLZ	Граф ведущих нулей	32, 64	CLZ	Ширина операнда
	CTZ	Граф следы за нули	32, 64	CTZ	Ширина операнда
Sparc Oracle Architecture 2011 и позже	LZCNT (синоним: LZD)	Ведущий нулевой счет	64	CLZ	64
Вакс	FFS	Найти первый набор	0–32	CTZ	Ширина операнда; Устанавливает нулевой флаг
IBM Z/Architecture	флогр	Найдите самый левый	64	CLZ	64
	vclz	Vector count ведущий нули	8, 16, 32, 64	CLZ	Ширина операнда
	VCTZ	Vector count rating Zeroes	8, 16, 32, 64	CTZ	Ширина операнда

На некоторых альфа -платформах CTLZ и CTTZ эмулируются в программном обеспечении.

Поддержка инструмента и библиотеки

Ряд компиляторов и поставщиков библиотеки поставки компилятора или библиотечных функций для выполнения первого набора и/или связанных операций, которые часто реализуются с точки зрения приведенных выше инструкций по аппаратным обеспечениям:

Инструмент/библиотека	Имя	Тип	Тип ввода (ы)	Примечания	При применении на 0
Posix .1 Libc, соответствующий Libc 4.3BSD Libc OS X 10.3 Libc	ffs	Библиотечная функция	инт	Включает GLIBC . POSIX не предоставляет дополнительную базу журнала 2 / CLZ.	0
FreeBSD 5.3 Libc OS X 10.4 Libc	ffsl fls flsl	Библиотечная функция	int, длинный	FLS («Найти последний набор») вычисляет (база журнала 2) + 1.	0
FreeBSD 7.1 Libc	ffsll flsll	Библиотечная функция	долго		0
GCC 3.4.0 Clang 5.x	__builtin_ffs[l,ll,imax] __builtin_clz[l,ll,imax] __builtin_ctz[l,ll,imax]	Встроенные функции	без подписи Int, без подписи долго, без подписи долго, uintmax_t	В документации GCC рассматривается результат неопределенного CLZ и CTZ на 0.	0 (FFS)
Visual Studio 2005	_BitScanForward _BitScanReverse	Компилятор Внутренняя	без подписи долго, Unsigned __int64	Отдельное возвратное значение, чтобы указать нулевой вход	Неопределенный
Visual Studio 2008	__lzcnt	Компилятор внутренний	без подписи короткой, без подписи Int, Unsigned __int64	Полагается на аппаратную поддержку для инструкции LZCNT, представленной в BMI1 или ABM .	Ширина операнда
Visual Studio 2012	_arm_clz	Компилятор внутренний	без знака инт	Полагается на аппаратную поддержку инструкции CLZ, представленной в архитектуре ARMV5T, а затем .	?
Компилятор Intel C ++	_bit_scan_forward _bit_scan_reverse	Компилятор Внутренняя	инт		Неопределенный
Nvidia cuda	__clz	Функции	32-bit, 64-bit	Компилируется меньше инструкций в серии GeForce 400	32
	__ffs				0
LLVM	llvm.ctlz.* llvm.cttz.*	Внутренний	8, 16, 32, 64, 256	LLVM Ассамблея	Ширина операнда, если 2 -й аргумент равен 0; неопределенное иначе
GHC 7.10 (база 4.8), в Data.Bits	countLeadingZeros countTrailingZeros	Библиотечная функция	FiniteBits b => b	Язык программирования Haskell	Ширина операнда
C ++ 20 Стандартная библиотека, в заголовке <bit>	bit_ceil bit_floor bit_width countl_zero countl_one countr_zero countr_one	Библиотечная функция	без подписи Чар, без подписи короткой, без подписи Int, без подписи долго, без подписи долго

Свойства и отношения

Если биты помечены, начиная с 1 (которая является соглашением, используемой в этой статье), то счета следов за первыми нулями и обнаруживают, что операции первого набора связаны с помощью CTZ ( x ) = FFS ( x ) - 1 (за исключением случаев, когда вход равен нулю). Если биты маркируются, начиная с 0 , то Count Trainling Zeros и First Set - это точно эквивалентные операции. Учитывая w биты на слово, log ₂ легко вычисляется из CLZ и наоборот по log ₂ ( x ) = w - 1 - Clz ( x ) .

Как показано в приведенном выше примере, находки первой ноль, ведущих графов и графы, сцепляющие операции, могут быть реализованы путем отрицания ввода и использования Find First Set, Count Leader Zeros и Count Trailing Zeros. Обратное также верно.

На платформах с эффективной операцией Log _2, такими как M68000, CTZ может быть вычислен с помощью:

ctz ( x ) = log ₂ ( x & −x )

где и обозначает кусочек и −x обозначает два дополнение x . Выражение x & −x очищает все, кроме наименее, 1 бит, так что наиболее и наименее знаковые 1 бит одинаковы.

На платформах с эффективной операцией ведущей Zeros, такой как ARM и PowerPC, FFS может быть рассчитана с помощью:

ffs ( x ) = w - clz ( x & −x ) .

И наоборот, на машинах без Log ₂ или CLZ операторов CLZ можно рассчитать с использованием CTZ , хотя и неэффективно:

clz = w - ctz (2 ^{⌈Log ₂ ( x ) ⌉} ) (что зависит от CTZ возврата ) для нулевого входа

На платформах с эффективной операцией веса (подсчет населения), такой как Sparc 's POPC или черные ​ ONES, есть:

ctz ( x ) = popcount (( x & −x ) - 1) , или ctz ( x ) = popcount (~ ( x | −x )) ,

ffs ( x ) = popcount ( x ^ ~ - x )

CLZ = 32 - POPCOUNT (2 ^{⌈Log ₂ ( x ) ⌉} − 1)

где ^ обозначает кусочек эксклюзивного-или, | обозначает кусочек или ~ обозначает кусочку отрицания.

Обратная проблема (с учетом i создает x, такой, что CTZ ( x ) = i ) может быть рассчитана с помощью левой сдвига ( 1 << i ).

Найдите первые установки и связанные с ними операции могут быть проведены на произвольно большие битовые массивы прямо, начиная с одного конца и выполняя до тех пор, пока не станет все-нулевое (для FFS , CTZ , CLZ ) или нет все-одно (для FFZ , CLO , CTO ) встречается. Структура данных дерева, которая рекурсивно использует растровые карты для отслеживания того, какие слова ненулевые, может ускорить это.

Эмуляция программного обеспечения

Большинство процессоров, датируемых концом 1980-х годов, имеют битовые операторы для FFS или эквивалентные, но некоторые современные, такие как некоторые из серии Arm-MX, нет. Вместо аппаратных операторов для FFS, CLZ и CTZ программное обеспечение может эмулировать их с помощью сдвигов, целочисленного арифметического и бить. Существует несколько подходов в зависимости от архитектуры процессора и в меньшей степени, семантики языка программирования и качества генерации кода компилятора. Подходы могут быть свободно описаны как линейный поиск , бинарный поиск , поиск+поиск таблицы, умножение De Bruijn, преобразование/извлечение с плавающей запятой и методы оператора битов (без ветвления). Существуют компромисс между временем выполнения и пространством для хранения, а также переносимостью и эффективностью.

Программные эмуляции обычно детерминированные. Они возвращают определенный результат для всех входных значений; В частности, результат для ввода всех нулевых битов обычно 0 для FFS, а длина битов операнда для других операций.

Если у кого есть аппаратный CLZ или эквивалент, CTZ может быть эффективно вычислен с помощью операций BIT, но обратное не так: CLZ не эффективен для вычисления в отсутствие аппаратного оператора.

2 ^не

Функция 2 ^{⌈Log ₂ (x) ⌉} (Собрание до ближайшей мощности двух), используя смены и бить не эффективен для вычисления, как в этом 32-разрядном примере и еще более неэффективно, если у нас есть 64-битный или 128-битный операнд:

function pow2(x):
    if x = 0 return invalid  // invalid is implementation defined (not in [0,63])
    x ← x - 1
    for each y in {1, 2, 4, 8, 16}: x ← x | (x >> y)
    return x + 1

FFS

Поскольку ffs = ctz + 1 (posix) или ffs = ctz (другие реализации), можно использовать применимые алгоритмы для CTZ, с возможным окончательным этапом добавления 1 к результату и возвращением 0 вместо длины оперина для ввода Все ноль битов.

CTZ

Канонический алгоритм представляет собой петли, подсчитывающий нули, начиная с LSB, пока не столкнется 1-битная:

function ctz1 (x)
    if x = 0 return w
    t ← 1
    r ← 0
    while (x & t) = 0
        t ← t << 1
        r ← r + 1
    return r

Этот алгоритм выполняет время и операции O ( n ) и на практике является непрактичным из -за большого количества условных ветвей.

Таблица поиска может устранить большинство ветвей:

table[0..2n-1] = ctz(i) for i in 0..2n-1
function ctz2 (x)
    if x = 0 return w
    r ← 0
    loop
        if (x & (2n-1)) ≠ 0
            return r + table[x & (2n-1)]
        x ← x >> n
        r ← r + n

Параметр n фиксирован (обычно 8) и представляет собой компромисс времени - пространство . Цикл также может быть полностью развернут . Но как линейный поиск, этот подход по -прежнему является O (n) в количестве битов в операнде.

Реализация бинарного поиска принимает логарифмическое количество операций и филиалов, как в этой 32-разрядной версии: Этот алгоритм также может помочь в таблице, заменив три нижних операторов «если» с таблицей поиска 256 с использованием первого ненулевого байта, встречающегося в качестве индекса.

function ctz3 (x)
    if x = 0 return 32
    n ← 0
    if (x & 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16
    if (x & 0x000000FF) = 0: n ← n +  8, x ← x >>  8
    if (x & 0x0000000F) = 0: n ← n +  4, x ← x >>  4
    if (x & 0x00000003) = 0: n ← n +  2, x ← x >>  2
    if (x & 0x00000001) = 0: n ← n +  1
    return n

Если у аппаратного обеспечения есть оператор CLZ, наиболее эффективный подход к вычислению CTZ является:

function ctz4 (x)
    x &= -x
    return w - (clz(x) + 1)

Алгоритм для 32-битного CTZ использует последовательности De Bruijn для построения минимальной идеальной хэш-функции, которая устраняет все ветви. Этот алгоритм предполагает, что результат умножения усекается до 32 бит.

for i from 0 to 31: table[ ( 0x077CB531 * ( 1 << i ) ) >> 27 ] ← i  // table [0..31] initialized
function ctz5 (x)
    return table[((x & -x) * 0x077CB531) >> 27]

Выражение (x & -x) снова изолирует наименее знаменитый 1 бит. Тогда существует только 32 возможных слова, которые не знаковое умножение и хэш сдвига в правильное положение в таблице. (Этот алгоритм не обрабатывает нулевой вход.)

CLZ

Канонический алгоритм исследует один бит за раз, начиная с MSB, пока не будет найден ненулевой бит, как показано в этом примере. Он выполняется во время O (n), где n-битовая длина операнда, и это не является практическим алгоритмом для общего использования.

function clz1 (x)
    if x = 0 return w
    t ← 1 << (w - 1)
    r ← 0
    while (x & t) = 0
        t ← t >> 1
        r ← r + 1
    return r

Улучшение на предыдущем подходе по циклу изучает восемь битов за раз, а затем использует 256 (2 ⁸ ) таблица поиска входа для первого ненулевого байта. Этот подход, однако, все еще остается O (n) во время исполнения.

function clz2 (x)
    if x = 0 return w
    t ← 0xff << (w - 8)
    r ← 0
    while (x & t) = 0
        t ← t >> 8
        r ← r + 8
    return r + table[x >> (w - 8 - r)]

Бинарный поиск может сократить время выполнения до O (log ₂ n):

function clz3 (x)
    if x = 0 return 32
    n ← 0
    if (x & 0xFFFF0000) = 0: n ← n + 16, x ← x << 16
    if (x & 0xFF000000) = 0: n ← n +  8, x ← x <<  8
    if (x & 0xF0000000) = 0: n ← n +  4, x ← x <<  4
    if (x & 0xC0000000) = 0: n ← n +  2, x ← x <<  2
    if (x & 0x80000000) = 0: n ← n +  1
    return n

Самые быстрые переносные подходы к моделированию CLZ-это комбинация бинарного поиска и поиска таблиц: 8-битный поиск таблицы (2 ⁸ = 256 1-байтовые записи) могут заменить нижние 3 ветви в бинарном поиске. 64-битные операнды требуют дополнительной ветви. Можно использовать больший поиск ширины, но максимальный практический размер таблицы ограничен размером кэша данных L1 на современных процессорах, который составляет 32 КБ для многих. Сохранение ветви более чем компенсируется задержкой промаха кэша L1 .

Алгоритм, аналогичный умножению De Bruijn для CTZ, работает для CLZ, но вместо того, чтобы выделять наиболее значимый бит, он окружает до ближайшего целого числа формы 2 ^не −1 Используя сдвиги и бить или

table[0..31] = {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
                8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31}
function clz4 (x)
    for each y in {1, 2, 4, 8, 16}: x ← x | (x >> y)
    return table[((x * 0x07C4ACDD) >> 27) % 32]

Для процессоров с глубокими трубопроводами, такими как Prescott и более поздние процессоры Intel, может быть быстрее заменить ветви на бить и или операторы (даже если требуется еще много инструкций), чтобы избежать промывок трубопроводов для недоторенных ветвей (и эти типы ветвей по -разному по -разному по -разному по -разному непредсказуемо):

function clz5 (x)
    r = (x > 0xFFFF) << 4; x >>= r;
    q = (x > 0xFF  ) << 3; x >>= q; r |= q;
    q = (x > 0xF   ) << 2; x >>= q; r |= q;
    q = (x > 0x3   ) << 1; x >>= q; r |= q;
                                    r |= (x >> 1);
    return r;

На платформах, которые обеспечивают аппаратное преобразование целых чисел в плавающую запятую, поле показания может быть извлечено и вычтено с постоянной для вычисления подсчета ведущих нулей. Исправления необходимы для учета ошибок округления. Преобразование с плавающей запятой может иметь существенную задержку. Этот метод очень невозможен и обычно не рекомендуется.

int x; 
int r;
union { unsigned int u[2]; double d; } t;

t.u[LE] = 0x43300000;  // LE is 1 for little-endian
t.u[!LE] = x;
t.d -= 4503599627370496.0;
r = (t.u[LE] >> 20) - 0x3FF;  // log2
r++;  // CLZ

Приложения

Операция ведущих нулей (CLZ) может использоваться для эффективной реализации нормализации , которая кодирует целое число как m × 2 ^и , где m имеет наиболее значимый бит в известной позиции (например, самая высокая позиция). Это, в свою очередь, может быть использовано для реализации подразделения Ньютона -Рафсона , выполнения целочисленного преобразования плавающей запятой в программном обеспечении и других приложениях.

Количество ведущих нулей (CLZ) можно использовать для вычисления 32-разрядного предиката Clz (x - y) >> 5 , где «>>» - это правый сдвиг без знака. Его можно использовать для выполнения более сложных битовых операций, таких как поиск первой строки n 1 битов. Выражение Clz (x-y) 1 << (16-Clz (x-1)/2) является эффективным начальным предположением для вычисления квадратного корня из 32-разрядного целого числа с использованием метода Ньютона . CLZ может эффективно реализовать подавление нулевого , метод быстрого сжатия данных , которая кодирует целое число в качестве числа ведущих нулевых байтов вместе с ненулевыми байтами. Он также может эффективно генерировать экспоненциально распределенные целые числа, принимая CLZ равномерно случайных целых чисел.

Основа Log 2 может использоваться, чтобы предвидеть, будет ли переполнение умножения, поскольку ⌈log ₂ (xy) ⌉ ≤ ⌈log ₂ (x) ⌉ + ⌈log ₂ (y) ⌉ .

Граф ведущих нулей и графства, сцепляющих нулей, можно использовать вместе для реализации алгоритма определения петли Госпера , который может найти период функции конечного диапазона, используя ограниченные ресурсы.

Бинарный алгоритм GCD тратит много циклов, удаляя следы за нольки; Это может быть заменено графом, следящим за нули (CTZ) с последующим сдвигом. Подобный цикл появляется в вычислениях последовательности града .

Немного массива может быть использован для реализации очереди приоритета . В этом контексте First Set (FFS) полезен при эффективной реализации операции «POP» или «Вытянуть наивысший приоритетный элемент». Планировщик ядра Linux в реальном времени использует внутреннее использование sched_find_first_bit() Для этого.

Работа с подсчетом нулей дает простое оптимальное решение задачи башни Ханои : диски пронумерованы от нуля, а при движении k номер диска CTZ ( K ) перемещается минимально возможное расстояние вправо (кружет обратно к оставленный по мере необходимости). Он также может генерировать серый код взяв произвольное слово и перевернув бит CTZ ( k ) на шаге K. ,

Смотрите также

• Наборы инструкций по манипуляциям в битах (ИМТ) для процессоров Intel и AMD x86
• Тропинг ноль
• Ведущий ноль
• Тяжелая цифра
• Ведущая цифра

Дальнейшее чтение

• Уоррен -младший, Генри С. (2013) [2002]. Хакерский восторг (2 изд.). Addison Wesley - Pearson Education, Inc. ISBN  978-0-321-84268-8 . 0-321-84268-5.
• Андерсон, Шон Эрон (2005) [1997]. «Несколько взломов» . Стэнфордский университет . Архивировано из оригинала 2020-01-08 . Получено 2012-01-03 . (Nb. Перечисляется несколько эффективных реализаций общественного домена C для Count Laking Zeros и Bog Base 2. )

Внешние ссылки

• Intel Insinsics Guide
• Шахматное программирование Wiki: Bitscan : подробное объяснение ряда методов реализации для FFS (называется LS1B) и логарифмической базы 2 (называется MS1B).