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

В компьютерном программном и аппаратном обеспечении поиск первого набора ( ffs ) или поиск первого набора — это битовая операция , которая, учитывая беззнаковое машинное слово , обозначает индекс или позицию младшего бита, установленного на единицу в слове, отсчитывающемся от позиции младшего бита. Почти эквивалентная операция — подсчет конечных нулей ( ctz ) или количества конечных нулей ( ntz ), которая подсчитывает количество нулевых битов, следующих за младшим значащим битом. Дополнительная операция, которая находит индекс или позицию старшего бита набора, — это log base 2 , названная так потому, что она вычисляет двоичный логарифм ⌊log ₂ (x)⌋ . Это тесно связано с подсчетом ведущих нулей ( clz ) или количеством ведущих нулей ( nlz ), который подсчитывает количество нулевых битов, предшествующих самому старшему биту. Существует два распространенных варианта поиска первого набора: определение POSIX , которое начинает индексацию битов с 1, здесь обозначен ffs, а вариант, который начинает индексацию битов с нуля, что эквивалентно ctz и поэтому будет называться этим именем.

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

Примеры

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

0000 0000 0000 0000 1000 0000 0000 1000

Операция подсчета конечных нулей вернет 3, а операция подсчета ведущих нулей возвращает 16. Операция подсчета ведущих нулей зависит от размера слова: если это 32-битное слово было усечено до 16-битного слова, подсчет ведущих нулей вернет ноль. . Операция поиска первого набора вернет 4, что указывает на четвертую позицию справа. База усеченного журнала 2 равна 15.

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

1111 1111 1111 1111 0111 1111 1111 0111

Операция подсчета конечных единиц вернет 3, операция подсчета ведущих единиц вернет 16, а операция поиска первого нуля ffz вернет 4.

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

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

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

Платформа	Мнемоника	Имя	Ширина операнда	Описание	По заявке на 0
ARM ( архитектура ARMv5T и более поздние версии ) кроме Cortex-M0/M0+/M1/M23	клз	Подсчитайте ведущие нули	32	клз	32
ARM ( архитектура ARMv8-A )	клз	Подсчитайте ведущие нули	32, 64	клз	Ширина операнда
АВР32	клз	Подсчитайте ведущие нули	32	клз	32
ДЕК Альфа	ctlz	Подсчитайте ведущие нули	64	клз	64
	cttz	Подсчитайте конечные нули	64	КТЗ	64
Intel 80386 и более поздние версии	BSF	Битовое сканирование вперед	16, 32, 64	КТЗ	Неопределенный; устанавливает нулевой флаг
	бср	Битовое сканирование, обратное	16, 32, 64	База журналов 2	Неопределенный; устанавливает нулевой флаг
x86 с поддержкой BMI1 или ABM	lzcnt	Подсчитайте ведущие нули	16, 32, 64	клз	Ширина операнда; наборы с флагом
x86 с поддержкой ИМТ1	tcnt	Подсчитайте конечные нули	16, 32, 64	КТЗ	Ширина операнда; наборы с флагом
Итаний	клз	Подсчитайте ведущие нули	64	клз	64
МИПС32/МИПС64	клз	Посчитать ведущие нули в Word	32, 64	клз	Ширина операнда
	Кло	Посчитайте ведущие в Word	32, 64	Кло	Ширина операнда
Моторола 68020 и новее	лучший друг	Найдите первый в битовом поле	Произвольный	База журналов 2	Смещение поля + ширина поля
ПДП-10	см.	Прыгай, если найдешь первого	36	клз	0; нет операции
ПИТАНИЕ / PowerPC / Питание ISA	cntlz/cntlzw/cntlzd	Подсчитайте ведущие нули	32, 64	клз	Ширина операнда
Питание ISA 3.0 и более поздних версий	cnttzw/cnttzd	Подсчитайте конечные нули	32, 64	КТЗ	Ширина операнда
RISC-V (расширение «B»)	клз	Подсчитайте ведущие нули	32, 64	клз	Ширина операнда
	КТЗ	Подсчитайте конечные нули	32, 64	КТЗ	Ширина операнда
SPARC Oracle Architecture 2011 и более поздние версии	лзкнт (синоним: лзд)	Ведущий нулевой счет	64	клз	64
ВАКС	ффс	Найти первый набор	0–32	КТЗ	Ширина операнда; устанавливает нулевой флаг
IBM z/Архитектура	флогр	Найдите самый левый	64	клз	64
	вклз	Ведущие нули векторного подсчета	8, 16, 32, 64	клз	Ширина операнда
	вкц	Векторный счетчик с конечными нулями	8, 16, 32, 64	КТЗ	Ширина операнда

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

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

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

Инструмент/библиотека	Имя	Тип	Тип(ы) входа	Примечания	По заявке на 0
POSIX .1-совместимая библиотека libc 4.3BSD libc ОС Х 10.3 libc	ffs	Библиотечная функция	интервал	Включает glibc . POSIX не предоставляет дополнительную базу журналов 2 / clz.	0
FreeBSD 5.3 libc. ОС Х 10.4 libc	ffsl fls flsl	Библиотечная функция	интервал, длинный	fls("найти последний набор") вычисляет (логарифм по базе 2) + 1.	0
FreeBSD 7.1 libc.	ffsll flsll	Библиотечная функция	долго долго		0
GCC 3.4.0 Кланг 5.x	__builtin_ffs[l,ll,imax] __builtin_clz[l,ll,imax] __builtin_ctz[l,ll,imax]	Встроенные функции	беззнаковое целое число, беззнаковый длинный, беззнаковый длинный длинный, uintmax_t	Документация GCC считает результат неопределенным clz и ctz равным 0.	0 (ффс)
Визуальная Студия 2005	_BitScanForward _BitScanReverse	Внутренние функции компилятора	беззнаковый длинный, беззнаковый __int64	Отдельное возвращаемое значение для указания нулевого ввода.	Неопределенный
Визуальная Студия 2008	__lzcnt	Встроенный компилятор	беззнаковое короткое, беззнаковое целое число, беззнаковый __int64	Полагается на аппаратную поддержку инструкции lzcnt, представленной в BMI1 или ABM .	Ширина операнда
Визуальная Студия 2012	_arm_clz	Встроенный компилятор	беззнаковое целое число	Опирается на аппаратную поддержку инструкции clz, представленной в архитектуре ARMv5T и более поздних версиях .	?
Intel C++-компилятор	_bit_scan_forward _bit_scan_reverse	Внутренние функции компилятора	интервал		Неопределенный
Нвидиа КУДА	__clz	Функции	32-bit, 64-bit	Компилируется с меньшим количеством инструкций серии GeForce 400.	32
	__ffs				0
ЛЛВМ	llvm.ctlz.* llvm.cttz.*	Внутренний	8, 16, 32, 64, 256	язык ассемблера LLVM	Ширина операнда, если второй аргумент равен 0; не определено в противном случае
GHC 7.10 (база 4.8), в Data.Bits	countLeadingZeros countTrailingZeros	Библиотечная функция	FiniteBits b => b	Язык программирования Хаскелл	Ширина операнда
C++20 , в заголовке Стандартная библиотека <bit>	bit_ceil bit_floor bit_width countl_zero countl_one countr_zero countr_one	Библиотечная функция	беззнаковый символ, беззнаковое короткое, беззнаковое целое число, беззнаковый длинный, беззнаковый длинный длинный

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

Если биты помечены начиная с 1 (это соглашение, используемое в этой статье), то операции подсчета конечных нулей и поиска первого набора связаны соотношением ctz( x ) = ffs( x ) − 1 (за исключением случаев, когда входное значение равно нулю). Если биты помечены начиная с 0 , то подсчет конечных нулей и поиск первого набора являются точно эквивалентными операциями. Учитывая w бит на слово, log ₂ легко вычисляется из clz и наоборот по формуле log ₂ ( x ) = w - 1 - clz( x ) .

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

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

ctz( x ) = журнал ₂ ( x & -x )

где & обозначает побитовое И, а -x обозначает двух дополнение до x . Выражение x & -x младшего очищает все, кроме одного бита, так что самый старший и самый последний бит совпадают.

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

ffs( Икс ) знак равно ш - clz( Икс & -х ) .

И наоборот, на машинах без log ₂ или clz операторов , clz можно вычислить с помощью ctz , хотя и неэффективно:

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

На платформах с эффективной операцией взвешивания Хэмминга (подсчета населения), таких как SPARC . POPC или Блэкфин ​ ONES, есть:

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

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

clz = 32 - popcount(2 ^{⌈лог ₂ ( х )⌉} − 1)

где ^ обозначает побитовое исключающее ИЛИ, | обозначает побитовое ИЛИ, а ~ обозначает побитовое отрицание.

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

Операции поиска первого набора и связанные с ними операции могут быть расширены до произвольно больших битовых массивов простым способом, начиная с одного конца и продолжая до тех пор, пока слово не будет не нулевым (для ffs , ctz , clz ) или не все единицей (для ffz , clo , cto ) встречается. Древовидная структура данных, которая рекурсивно использует растровые изображения для отслеживания того, какие слова ненулевые, может ускорить этот процесс.

Программная эмуляция

Большинство процессоров, выпущенных с конца 1980-х годов, имеют битовые операторы для ffs или эквивалентные, но некоторые современные процессоры, такие как некоторые из серии ARM-Mx, не имеют. Вместо аппаратных операторов для ffs, clz и ctz программное обеспечение может эмулировать их с помощью сдвигов, целочисленной арифметики и побитовых операторов. Существует несколько подходов в зависимости от архитектуры ЦП и, в меньшей степени, семантики языка программирования и качества генерации кода компилятора. Подходы можно условно описать как линейный поиск , двоичный поиск , поиск + поиск по таблице, умножение де Брёйна, преобразование с плавающей запятой/извлечение показателя степени и методы битового оператора (без ветвей). Существует компромисс между временем выполнения и объемом памяти, а также портативностью и эффективностью.

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

Если у вас есть аппаратный clz или его эквивалент, ctz можно эффективно вычислить с помощью битовых операций, но обратное неверно: вычисление clz неэффективно в отсутствие аппаратного оператора.

2 ^н

Функция 2 ^{⌈лог ₂ (х)⌉} (округляем до ближайшей степени двойки) с использованием сдвигов и побитовых операций ИЛИ неэффективно вычислять, как в этом 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 = ctz + 1 (POSIX) или ffs = ctz (другие реализации), можно использовать применимые алгоритмы для ctz с возможным последним шагом добавления 1 к результату и возвратом 0 вместо длины операнда для ввода все нулевые биты.

ЧТЗ

Канонический алгоритм представляет собой цикл, подсчитывающий нули, начиная с младшего разряда до тех пор, пока не встретится 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-битной версии: Этому алгоритму также может помочь таблица, заменяющая три нижних оператора «if» таблицей поиска из 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 использует последовательности де Брейна для построения минимальной идеальной хэш-функции , исключающей все ветвления. Этот алгоритм предполагает, что результат умножения усекается до 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) снова изолирует один наименее значимый бит. Тогда есть только 32 возможных слова, которые можно умножить без знака и сдвинуть хэш на правильную позицию в таблице. (Этот алгоритм не обрабатывает нулевой ввод.)

КЛЗ

Канонический алгоритм проверяет по одному биту, начиная со старшего бита, пока не будет найден ненулевой бит, как показано в этом примере. Он выполняется за время 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-байтовых записей) могут заменить три нижние ветви при двоичном поиске. 64-битные операнды требуют дополнительной ветки. Можно использовать поиск большей ширины, но максимальный практический размер таблицы ограничен размером кэша данных L1 на современных процессорах, который для многих составляет 32 КБ. Сохранение ветки более чем компенсируется задержкой из-за промаха в кэше L1 .

Алгоритм, аналогичный умножению де Брейна для 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-битного предиката «x = y» (ноль, если истинно, единица, если ложно) через тождество clz(x − y) >> 5 , где «>>» — беззнаковый сдвиг вправо. Его можно использовать для выполнения более сложных битовых операций, таких как поиск первой строки из n 1 бит. Выражение clz(x − y)1 << (16 − clz(x − 1)/2) — эффективное начальное предположение для вычисления квадратного корня из 32-битного целого числа с использованием метода Ньютона . CLZ может эффективно реализовать подавление нулей — метод быстрого сжатия данных , который кодирует целое число как количество начальных нулевых байтов вместе с ненулевыми байтами. Он также может эффективно генерировать экспоненциально распределенные целые числа, взяв clz равномерно случайных целых чисел.

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

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

Алгоритм двоичного НОД тратит много циклов на удаление конечных нулей; это можно заменить счетчиком конечных нулей (ctz), за которым следует сдвиг. Аналогичная петля возникает при вычислении последовательности градин .

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

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

См. также

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

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

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

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

• Руководство по внутренним компонентам Intel
• Wiki по шахматному программированию: BitScan : подробное объяснение ряда методов реализации для ffs (называемого LS1B) и базы журнала 2 (называемого MS1B).