В программном и аппаратном обеспечении компьютера find first set ( ffs ) или find first one — это битовая операция , которая, учитывая беззнаковое машинное слово , [nb 1] обозначает индекс или позицию младшего значащего бита, установленного на единицу в слове, считая от позиции младшего значащего бита. Почти эквивалентная операция — подсчет конечных нулей ( ctz ) или количество конечных нулей ( ntz ), которая подсчитывает количество нулевых битов, следующих за младшим единичным битом. Дополнительная операция, которая находит индекс или позицию старшего значащего бита набора, — это log base 2 , так называемый потому, что он вычисляет двоичный логарифм ⌊log 2 (x)⌋ . [1] Это тесно связано с подсчетом ведущих нулей ( clz ) или количеством ведущих нулей ( nlz ), которая подсчитывает количество нулевых битов, предшествующих старшему единичному биту. [nb 2] Существует два распространенных варианта find first set: определение POSIX , которое начинает индексацию битов с 1, [2] здесь обозначенное как ffs, и вариант, который начинает индексацию битов с нуля, что эквивалентно ctz и поэтому будет называться этим именем.
Большинство современных архитектур наборов инструкций ЦП предоставляют один или несколько из них в качестве аппаратных операторов; для тех, которые недоступны, обычно предоставляется программная эмуляция либо в виде встроенных функций компилятора , либо в системных библиотеках .
Дано следующее 32-битное слово:
Операция подсчета конечных нулей вернет 3, а операция подсчета ведущих нулей вернет 16. Операция подсчета ведущих нулей зависит от размера слова: если это 32-битное слово усечь до 16-битного слова, операция подсчета ведущих нулей вернет ноль. Операция поиска первого множества вернет 4, что указывает на 4-ю позицию справа. Усеченный логарифм по основанию 2 равен 15.
Аналогично, если задано следующее 32-битное слово, побитовое отрицание приведенного выше слова:
Операция подсчета конечных единиц вернет 3, операция подсчета начальных единиц вернет 16, а операция поиска первых нулей ffz вернет 4.
Если слово равно нулю (биты не установлены), подсчет ведущих нулей и подсчет конечных нулей возвращают количество бит в слове, тогда как ffs возвращает ноль. Реализации find first set как с основанием log 2, так и с основанием log 0 обычно возвращают неопределенный результат для нулевого слова.
Многие архитектуры включают инструкции для быстрого выполнения find first set и/или связанных операций, перечисленных ниже. Наиболее распространенной операцией является count leading zeros (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 очищает все, кроме младшего значащего бита 1 , так что старший и младший значащие биты 1 одинаковы.
На платформах с эффективной операцией подсчета ведущих нулей, таких как ARM и PowerPC, ffs можно вычислить следующим образом:
Наоборот, на машинах без операторов log 2 или clz , clz можно вычислить с помощью ctz , хотя и неэффективно:
На платформах с эффективной операцией веса Хэмминга (подсчета населения), таких как SPARC POPC[35] [ 36] или Blackfin [37] , ONESсуществует :
где ^ обозначает побитовое исключающее ИЛИ, | обозначает побитовое ИЛИ, а ~ обозначает побитовое отрицание.
Обратную задачу (при заданном i получить x , такой что ctz( x ) = i ) можно вычислить с помощью сдвига влево ( 1 << i ).
Find first set и связанные с ним операции можно расширить до произвольно больших битовых массивов простым способом, начав с одного конца и продолжая до тех пор, пока не встретится слово, которое не является полностью нулевым (для 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 вместо длины операнда для ввода всех нулевых битов.
Канонический алгоритм представляет собой цикл, подсчитывающий нули, начиная с младшего бита, пока не встретится единичный бит:
функция ctz1 (x) если x = 0 вернуть w т ← 1 г ← 0 пока (x & t) = 0 т ← т << 1 г ← г + 1 возврат г
Этот алгоритм выполняется за O ( n ) времени и операций и на практике нецелесообразен из-за большого количества условных ветвлений.
Таблица поиска может исключить большинство ветвей:
таблица[0..2 n -1] = ctz(i) для i в диапазоне 0..2 n -1 функция ctz2 (x) если x = 0 вернуть w г ← 0 цикл если (x & (2 n -1)) ≠ 0 вернуть 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 если (x & 0x00000003) = 0: n ← n + 2, x ← x >> 2 если (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 // table [0..31] инициализированная функция ctz5 (x) return table[((x & -x) * 0x077CB531) >> 27]
Выражение (x & -x) снова изолирует наименее значимый 1 бит. Тогда есть только 32 возможных слова, которые беззнаковое умножение и сдвиг хэша в правильную позицию в таблице. (Этот алгоритм не обрабатывает нулевой ввод.)
Канонический алгоритм проверяет один бит за раз, начиная с MSB, пока не будет найден ненулевой бит, как показано в этом примере. Он выполняется за время 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 << (ж - 8) г ← 0 пока (x & t) = 0 т ← т >> 8 г ← г + 8 вернуть r + таблица[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 если (x & 0xC0000000) = 0: n ← n + 2, x ← x << 2 если (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, может быть быстрее заменить переходы побитовыми операторами AND и OR (даже если для этого потребуется гораздо больше инструкций), чтобы избежать сброса конвейера для неправильно предсказанных переходов (а эти типы переходов по своей сути непредсказуемы):
функция clz5 (x) г = (х > 0xFFFF) << 4; х >>= г; q = (x > 0xFF ) << 3; x >>= q; r |= q; q = (x > 0xF ) << 2; x >>= q; r |= q; q = (x > 0x3 ) << 1; x >>= q; r |= q; г |= (х >> 1); вернуть г;
На платформах, которые обеспечивают аппаратное преобразование целых чисел в числа с плавающей точкой, поле экспоненты может быть извлечено и вычтено из константы для вычисления количества ведущих нулей. Исправления необходимы для учета ошибок округления. [41] [46] Преобразование чисел с плавающей точкой может иметь существенную задержку. Этот метод крайне непереносим и обычно не рекомендуется.
int x ; int r ; union { unsigned int u [ 2 ]; double d ; } t ; t . u [ LE ] = 0x43300000 ; // LE равен 1 для little-endian t . u [ ! LE ] = x ; t . d -= 4503599627370496.0 ; r = ( t . u [ LE ] >> 20 ) - 0x3FF ; // log2 r ++ ; // CLZ Операция подсчета ведущих нулей (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]
Двоичный алгоритм GCD тратит много циклов на удаление конечных нулей; это можно заменить подсчетом конечных нулей (ctz) с последующим сдвигом. Похожий цикл появляется в вычислениях последовательности градин .
Битовый массив может быть использован для реализации очереди приоритетов . В этом контексте find first set (ffs) полезен для эффективной реализации операции "pop" или "pull highest priority element". Планировщик реального времени ядра Linuxsched_find_first_bit() внутренне использует для этой цели. [54]
Операция подсчета конечных нулей дает простое оптимальное решение задачи Ханойской башни : диски нумеруются с нуля, и на шаге k номер диска ctz( k ) перемещается на минимально возможное расстояние вправо (при необходимости возвращаясь налево). Она также может генерировать код Грея , беря произвольное слово и переворачивая бит ctz( k ) на шаге k . [42]
Clang поддерживает ряд встроенных библиотечных функций с тем же синтаксисом, что и GCC