В компьютерном программном и аппаратном обеспечении поиск первого набора ( ffs ) или поиск первого — это битовая операция , которая для беззнакового машинного слова [nb 1] обозначает индекс или позицию младшего бита, установленного в единицу в слове, отсчитывающемся от позиция наименее значимого бита. Почти эквивалентная операция — подсчет конечных нулей ( ctz ) или количества конечных нулей ( ntz ), которая подсчитывает количество нулевых битов, следующих за младшим значащим битом. Дополнительная операция, которая находит индекс или позицию старшего бита набора, — это log base 2 , названная так потому, что она вычисляет двоичный логарифм ⌊log 2 (x)⌋ . [1] Это тесно связано с подсчетом ведущих нулей ( clz ) или количеством ведущих нулей ( nlz ), который подсчитывает количество нулевых битов, предшествующих самому старшему биту. [nb 2] Существует два распространенных варианта поиска первого набора: определение POSIX , которое начинает индексацию битов с 1, [2] здесь обозначено как ffs, и вариант, который начинает индексацию битов с нуля, что эквивалентно ctz и т. д. будет называться этим именем.
Большинство современных архитектур набора команд ЦП предоставляют один или несколько из них в качестве аппаратных операторов; программная эмуляция обычно предоставляется для всех недоступных функций либо в виде встроенных функций компилятора , либо в системных библиотеках .
Учитывая следующее 32-битное слово:
Операция подсчета конечных нулей вернет 3, а операция подсчета ведущих нулей возвращает 16. Операция подсчета ведущих нулей зависит от размера слова: если это 32-битное слово было усечено до 16-битного слова, подсчет ведущих нулей вернет ноль. . Операция поиска первого набора вернет 4, что указывает на четвертую позицию справа. База усеченного журнала 2 равна 15.
Аналогично, учитывая следующее 32-битное слово, побитовое отрицание вышеуказанного слова:
Операция подсчета конечных единиц вернет 3, операция подсчета ведущих единиц вернет 16, а операция поиска первого нуля ffz вернет 4.
Если слово равно нулю (биты не установлены), подсчет начальных нулей и подсчет конечных нулей возвращают количество битов в слове, а ffs возвращает ноль. Как логарифмическая реализация с основанием 2, так и реализация find first set с отсчетом от нуля обычно возвращают неопределенный результат для нулевого слова.
Многие архитектуры включают инструкции для быстрого выполнения поиска первого набора и/или связанных с ним операций, перечисленных ниже. Наиболее распространенной операцией является подсчет начальных нулей (clz), вероятно, потому, что все остальные операции могут быть эффективно реализованы с ее помощью (см. Свойства и отношения).
На некоторых платформах Alpha CTLZ и CTTZ эмулируются программно.
Ряд поставщиков компиляторов и библиотек предоставляют встроенные функции компилятора или библиотечные функции для выполнения поиска первого набора и/или связанных с ним операций, которые часто реализуются с помощью аппаратных инструкций, приведенных выше:
Если биты помечены начиная с 1 (это соглашение, используемое в этой статье), то операции подсчета конечных нулей и поиска первого набора связаны соотношением ctz( x ) = ffs( x ) − 1 (кроме случаев, когда входное значение равно нулю). Если биты помечены начиная с 0 , то подсчет конечных нулей и поиск первого набора являются точно эквивалентными операциями. Учитывая w бит в слове, log 2 легко вычисляется из clz и наоборот по формуле log 2 ( x ) = w - 1 - clz( x ) .
Как показано в приведенном выше примере, операции поиска первого нуля, подсчета ведущих и подсчета конечных нулей могут быть реализованы путем инвертирования входных данных и использования поиска первого набора, подсчета ведущих нулей и подсчета конечных нулей. Обратное также верно.
На платформах с эффективной операцией log 2 , таких как M68000, ctz можно вычислить следующим образом:
где & обозначает побитовое И, а -x обозначает дополнение до двух чисел x . Выражение x & -x очищает все, кроме одного младшего бита, так что самый старший и самый последний бит совпадают.
На платформах с эффективным подсчетом ведущих нулей, таких как ARM и PowerPC, ffs можно вычислить следующим образом:
И наоборот, на машинах без операторов log 2 или clz , clz можно вычислить с помощью ctz , хотя и неэффективно:
На платформах с эффективной операцией взвешивания Хэмминга ( подсчета населения) , таких как SPARC POPC[35] [36] или BlackfinONES , [37] происходит:
где ^ обозначает побитовое исключающее ИЛИ, | обозначает побитовое ИЛИ, а ~ обозначает побитовое отрицание.
Обратная задача (при заданном 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 ⌈log 2 (x)⌉ (округление до ближайшей степени двойки) с использованием сдвигов и побитовых операций ИЛИ [40] неэффективна для вычисления, как в этом 32-битном примере, и еще более неэффективна, если у нас есть 64-битный пример. битовый или 128-битный операнд:
функция pow2(x): если x = 0, возврат недействителен // недопустима определена реализация (не в [0,63]) х ← х - 1 для каждого y в {1, 2, 4, 8, 16}: x ← x | (x >> y) вернуть x + 1Поскольку ffs = ctz + 1 (POSIX) или ffs = ctz (другие реализации), можно использовать применимые алгоритмы для ctz с возможным последним шагом добавления 1 к результату и возвратом 0 вместо длины операнда для ввода все нулевые биты.
Канонический алгоритм представляет собой цикл, подсчитывающий нули, начиная с младшего разряда до тех пор, пока не встретится 1 бит:
функция ctz1 (x) , если x = 0, возвращает w т ← 1 г ← 0 в то время как (x и t) = 0 т ← т << 1 г ← г + 1 вернуть р
Этот алгоритм выполняет время и операции O ( n ) и на практике непрактичен из-за большого количества условных ветвей.
Таблица поиска может исключить большинство ветвей:
table[0..2 n -1] = ctz(i) для i в 0..2 n -1 функция ctz2 (x) , если x = 0, возвращает w г ← 0 цикл if (x & (2 n -1)) ≠ 0 return r + table[x & (2 n -1)] х ← х >> п г ← г + п
Параметр n фиксирован (обычно 8) и представляет собой компромисс между временем и пространством . Петля также может быть полностью развернута . Но при линейном поиске этот подход по-прежнему равен O(n) по числу битов в операнде.
Реализация двоичного поиска требует логарифмического числа операций и ветвей, как в этой 32-битной версии: [41] [42] Этот алгоритм также может быть дополнен таблицей, заменяющей три нижних оператора «if» записью 256. таблица поиска с использованием первого ненулевого байта, встреченного в качестве индекса.
функция ctz3 (x), если x = 0, возвращает 32 п ← 0 если (x & 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16, если (x & 0x000000FF) = 0: n ← n + 8, x ← x >> 8, если (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 вернуть n
Если в аппаратном обеспечении имеется оператор clz, наиболее эффективный подход к вычислению ctz выглядит следующим образом:
функция ctz4 (x) х &= -х вернуть w - (clz(x) + 1)
Алгоритм для 32-битного ctz использует последовательности де Брейна для построения минимальной идеальной хеш-функции , исключающей все ветвления. [43] [44] Этот алгоритм предполагает, что результат умножения усекается до 32 бит.
для i от 0 до 31: table[ ( 0x077CB531 * ( 1 << i ) ) >> 27 ] ← i // таблица [0..31] инициализированная функция ctz5 (x) return table[((x & -x) * 0x077CB531) >> 27]
Выражение (x & -x) снова изолирует один наименее значимый бит. Тогда есть только 32 возможных слова, которые можно умножить без знака и сдвинуть хэш на правильную позицию в таблице. (Этот алгоритм не обрабатывает нулевой ввод.)
Канонический алгоритм проверяет по одному биту, начиная со старшего бита, пока не будет найден ненулевой бит, как показано в этом примере. Он выполняется за время O(n), где n — длина операнда в битах, и не является практическим алгоритмом общего использования.
функция clz1 (x) , если x = 0, возвращает w т ← 1 << (ш - 1) г ← 0 в то время как (x и t) = 0 т ← т >> 1 г ← г + 1 вернуть р
Усовершенствование предыдущего подхода к циклированию проверяет восемь бит за раз, а затем использует таблицу поиска записей из 256 (2 8 ) для первого ненулевого байта. Однако этот подход по-прежнему требует O(n) во время выполнения.
функция clz2 (x) , если x = 0, возвращает w т ← 0xff << (w - 8) г ← 0 в то время как (x и t) = 0 т ← т >> 8 г ← г + 8 вернуть r + table[x >> (w - 8 - r)]
Двоичный поиск может сократить время выполнения до O(log 2 n):
функция clz3 (x), если x = 0, возвращает 32 п ← 0 если (x & 0xFFFF0000) = 0: n ← n + 16, x ← x << 16, если (x & 0xFF000000) = 0: n ← n + 8, x ← x << 8, если (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 вернуть n
Самый быстрый портативный подход к моделированию clz — это комбинация двоичного поиска и поиска по таблице: поиск по 8-битной таблице (2 8 = 256 1-байтовых записей) может заменить нижние 3 ветви в двоичном поиске. 64-битные операнды требуют дополнительной ветки. Можно использовать поиск большей ширины, но максимальный практический размер таблицы ограничен размером кэша данных L1 на современных процессорах, который для многих составляет 32 КБ. Сохранение ветки более чем компенсируется задержкой из-за промаха в кэше L1 .
Алгоритм, аналогичный умножению де Брюйна для CTZ, работает для CLZ, но вместо того, чтобы изолировать самый старший бит, он округляет до ближайшего целого числа формы 2 n -1, используя сдвиги и побитовые операции ИЛИ: [45]
таблица[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}функция clz4 (x) для каждого y в {1, 2, 4, 8, 16}: x ← x | (x >> y) return table[((x * 0x07C4ACDD) >> 27) % 32]Для процессоров с глубокими конвейерами, таких как Prescott и более поздние процессоры Intel, возможно, будет быстрее заменить ветки побитовыми операторами И и ИЛИ (даже несмотря на то, что требуется гораздо больше инструкций), чтобы избежать очистки конвейера для неправильно предсказанных ветвей (и эти типы ветвей по своей сути являются непредсказуемо):
функция clz5 (x) г = (х > 0xFFFF) << 4; х >>= г; q = (x > 0xFF) << 3; х >>= q; р |= q; q = (x > 0xF) << 2; х >>= q; р |= q; q = (x > 0x3) << 1; х >>= q; р |= q; г |= (х >> 1); вернуть р;
На платформах, которые обеспечивают аппаратное преобразование целых чисел в числа с плавающей запятой, поле экспоненты можно извлечь и вычесть из константы для вычисления количества ведущих нулей. Исправления необходимы для учета ошибок округления. [41] [46] Преобразование с плавающей запятой может иметь значительную задержку. Этот метод крайне непереносим и обычно не рекомендуется.
интервал х ; интервал р ; объединение { беззнаковое int u [ 2 ]; двойной д ; } т ; т . ты [ LE ] знак равно 0x43300000 ; // LE равен 1 для t с прямым порядком байтов . ты [ ! ЛЕ ] знак равно Икс ; т . д -= 4503599627370496.0 ; р = ( т . ты [ LE ] >> 20 ) - 0x3FF ; // log2 r ++ ; // КЛЗ Операцию подсчета начальных нулей (clz) можно использовать для эффективной реализации нормализации , которая кодирует целое число как m × 2 e , где m имеет свой старший бит в известной позиции (например, в самой высокой позиции). Это, в свою очередь, можно использовать для реализации деления Ньютона-Рафсона , преобразования целых чисел в числа с плавающей запятой в программном обеспечении и других приложениях. [41] [47]
Ведущие нули счетчика (clz) можно использовать для вычисления 32-битного предиката «x = y» (ноль, если истинно, единица, если ложно) с помощью тождества clz(x − y) >> 5 , где «>>» без знака. правая смена. [48] Его можно использовать для выполнения более сложных битовых операций, таких как поиск первой строки из n 1 бит. [49] Выражение clz(x − y)1 << (16 − clz(x − 1)/2) является эффективным начальным предположением для вычисления квадратного корня из 32-битного целого числа с использованием метода Ньютона . [50] CLZ может эффективно реализовать подавление нулей — метод быстрого сжатия данных , который кодирует целое число как количество начальных нулевых байтов вместе с ненулевыми байтами. [51] Он также может эффективно генерировать экспоненциально распределенные целые числа, взяв clz равномерно случайных целых чисел. [41]
Логарифмическую базу 2 можно использовать, чтобы предвидеть, произойдет ли переполнение умножения, поскольку ⌈log 2 (xy)⌉ ≤ ⌈log 2 (x)⌉ + ⌈log 2 (y)⌉ . [52]
Подсчет начальных нулей и подсчет конечных нулей можно использовать вместе для реализации алгоритма обнаружения петель Госпера [53] , который может найти период функции конечного диапазона, используя ограниченные ресурсы. [42]
Алгоритм двоичного НОД тратит много циклов на удаление конечных нулей; это можно заменить счетчиком конечных нулей (ctz), за которым следует сдвиг. Аналогичная петля возникает при вычислении последовательности градин .
Битовый массив может использоваться для реализации приоритетной очереди . В этом контексте поиск первого набора (ffs) полезен для эффективной реализации операции «извлечение» или «извлечение элемента с наивысшим приоритетом». Для этой цели используется внутренний планировщик реального времени ядра Linux . [54]sched_find_first_bit()
Операция подсчета конечных нулей дает простое оптимальное решение проблемы Ханойской башни : диски нумеруются с нуля, и при движении k диск с номером ctz( k ) перемещается на минимально возможное расстояние вправо (оборачиваясь назад к оставлял по необходимости). Он также может генерировать код Грея , взяв произвольное слово и перевернув бит ctz( k ) на шаге k . [42]
Clang поддерживает ряд встроенных библиотечных функций с тем же синтаксисом, что и GCC.