В компьютерном программном и аппаратном обеспечении, найти первый набор ( ffs ) или найти первый - это битовая операция, которая, учитывая машинное слово без знака , [nb 1] обозначает индекс или позицию младшего значащего бита, установленного на единицу в слове, считая от младшая битовая позиция. Почти эквивалентная операция - это подсчет конечных нулей ( ctz ) или количества конечных нулей ( ntz ), который подсчитывает количество нулевых битов, следующих за младшим значащим битом. Дополнительная операция, которая находит индекс или позицию самого значимого бита набора, -логарифм с основанием 2 , так называемый, потому что он вычисляет двоичный логарифм ⌊log 2 (x) ⌋ . [1] Это тесно связано с подсчетом начальных нулей ( clz ) или количеством начальных нулей ( nlz ), которые подсчитывают количество нулевых битов, предшествующих старшему значащему биту. [nb 2] Существует два распространенных варианта поиска первого набора: определение POSIX, которое начинает индексирование битов с 1, [2] здесь обозначено как 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 возвращает ноль. Реализация функции find first set как с логической базой 2, так и с нулевой базой обычно возвращает неопределенный результат для нулевого слова.
Аппаратная поддержка
Многие архитектуры включают инструкции по быстрому выполнению поиска первого набора и / или связанных операций, перечисленных ниже. Наиболее распространенной операцией является подсчет ведущих нулей (clz), вероятно, потому, что все другие операции могут быть эффективно реализованы с ее помощью (см. Свойства и отношения ).
Платформа | Мнемонический | Имя | Ширина операнда | Описание | По заявке на 0 |
---|---|---|---|---|---|
ARM ( архитектура ARMv5T и более поздние версии ), кроме Cortex-M0 / M0 + / M1 / M23 | clz [3] | Считайте ведущие нули | 32 | clz | 32 |
ARM ( архитектура ARMv8-A ) | clz | Считайте ведущие нули | 32, 64 | clz | Ширина операнда |
AVR32 | clz [4] | Считайте ведущие нули | 32 | clz | 32 |
DEC Alpha | ctlz [5] | Считайте ведущие нули | 64 | clz | 64 |
cttz [5] | Считать конечные нули | 64 | ctz | 64 | |
Intel 80386 и выше | bsf [6] | Битовое сканирование вперед | 16, 32, 64 | ctz | Неопределенный; устанавливает нулевой флаг |
бср [6] | Битовое сканирование в обратном направлении | 16, 32, 64 | Бревенчатое основание 2 | Неопределенный; устанавливает нулевой флаг | |
x86 с поддержкой BMI1 или ABM | lzcnt [7] | Считайте ведущие нули | 16, 32, 64 | clz | Ширина операнда; устанавливает флаг переноса |
x86 с поддержкой BMI1 | tzcnt [8] | Считать конечные нули | 16, 32, 64 | ctz | Ширина операнда; устанавливает флаг переноса |
Itanium | clz [9] | Считайте ведущие нули | 64 | clz | 64 |
MIPS | clz [10] [11] | Подсчитать ведущие нули в Word | 32, 64 | clz | Ширина операнда |
clo [10] [11] | Подсчитайте лидеров в слове | 32, 64 | Clo | Ширина операнда | |
Motorola 68020 и новее | bfffo [12] | Найти первую в битовом поле | Произвольный | Бревенчатое основание 2 | Смещение поля + ширина поля |
PDP-10 | jffo | Прыгай, если найдешь первого | 36 | ctz | 0; нет операции |
ПИТАНИЕ / PowerPC / Power ISA | cntlz / cntlzw / cntlzd [13] | Считайте ведущие нули | 32, 64 | clz | Ширина операнда |
Power ISA 3.0 и новее | cnttzw / cnttzd [14] | Считать конечные нули | 32, 64 | ctz | Ширина операнда |
RISC-V (расширение "B") (черновик) | clz [15] | Считайте ведущие нули | 32, 64 | clz | Ширина операнда |
ctz [15] | Считать конечные нули | 32, 64 | ctz | Ширина операнда | |
SPARC Oracle Architecture 2011 и новее | lzcnt (синоним: lzd) [16] | Ведущий нулевой счет | 64 | clz | 64 |
VAX | ffs [17] | Найти первый набор | 0–32 | ctz | Ширина операнда; устанавливает нулевой флаг |
IBM z / Архитектура | Flogr [18] | Найдите крайний левый | 64 | clz | 64 |
vclz [18] | Векторный подсчет ведущих нулей | 8, 16, 32, 64 | clz | Ширина операнда | |
vctz [18] | Счетчик векторов в конце нулей | 8, 16, 32, 64 | ctz | Ширина операнда |
На некоторых платформах Alpha CTLZ и CTTZ эмулируются программно.
Поддержка инструментов и библиотек
Ряд поставщиков компиляторов и библиотек предоставляют встроенные функции компилятора или библиотечные функции для выполнения поиска первого набора и / или связанных операций, которые часто реализуются в терминах аппаратных инструкций выше:
Инструмент / библиотека | Имя | Тип | Тип (ы) ввода | Заметки | По заявке на 0 |
---|---|---|---|---|---|
Совместимость с POSIX .1 libc 4.3BSD libc OS X 10.3 libc [2] [19] | ffs | Библиотечная функция | int | Включает glibc . POSIX не предоставляет дополнительную базу журналов 2 / clz. | 0 |
FreeBSD 5.3 libc OS X 10.4 libc [19] | ffsl fls flsl | Библиотечная функция | int, long | fls ("найти последний набор") вычисляет (логарифм с основанием 2) + 1. | 0 |
FreeBSD 7.1 libc [20] | ffsll flsll | Библиотечная функция | долго долго | 0 | |
GCC 3.4.0 [21] [22] Clang 5.x [23] [24] | __builtin_ffs[l,ll,imax] __builtin_clz[l,ll,imax] __builtin_ctz[l,ll,imax] | Встроенные функции | беззнаковое int, беззнаковое длинное, беззнаковое длинное длинное, uintmax_t | Документация GCC рассматривает результат undefined clz и ctz на 0. | 0 (ffs) |
Visual Studio 2005 | _BitScanForward [25] _BitScanReverse [26] | Внутренние функции компилятора | беззнаковый длинный, беззнаковый __int64 | Отдельное возвращаемое значение для обозначения нулевого ввода | Неопределенный |
Visual Studio 2008 | __lzcnt [27] | Встроенный компилятор | беззнаковый короткий, беззнаковый int, беззнаковый __int64 | Полагается на аппаратную поддержку инструкции lzcnt, представленной в BMI1 или ABM . | Ширина операнда |
Компилятор Intel C ++ | _bit_scan_forward _bit_scan_reverse [28] [29] | Внутренние функции компилятора | int | Неопределенный | |
NVIDIA CUDA [30] | __clz | Функции | 32-бит, 64-бит | Компилируется с меньшим количеством инструкций на GeForce серии 400 | 32 |
__ffs | 0 | ||||
LLVM | llvm.ctlz.* llvm.cttz.* [31] | Внутренний | 8, 16, 32, 64, 256 | Язык ассемблера LLVM | Ширина операнда, если второй аргумент равен 0; не определено иначе |
GHC 7.10 (база 4.8), в Data.Bits [ необходима ссылка ] | countLeadingZeros countTrailingZeros | Библиотечная функция | FiniteBits b => b | Язык программирования Haskell | Ширина операнда |
Стандартная библиотека C ++ 20 , в заголовке [32] [33] | bit_ceil bit_floor bit_width countl_zero countl_one countr_zero countr_one | Библиотечная функция | беззнаковый символ, беззнаковый короткий, беззнаковый int, беззнаковый длинный, беззнаковый длинный длинный |
Свойства и отношения
Если биты помечены, начиная с 1 (это соглашение, используемое в этой статье), то операции подсчета конечных нулей и поиска первого набора связаны соотношением ctz ( x ) = ffs ( x ) - 1 (кроме случаев, когда входной сигнал равен нулю). Если биты помечены, начиная с 0 , то подсчет конечных нулей и поиск первого набора являются точно эквивалентными операциями. Учитывая w бит на слово, log 2 легко вычисляется из clz и наоборот: log 2 ( x ) = w - 1 - clz ( x ) .
Как показано в приведенном выше примере, операции поиска первого нуля, подсчета начальных единиц и подсчета конечных единиц могут быть реализованы путем отрицания ввода и использования поиска первого набора, подсчета начальных нулей и подсчета конечных нулей. Обратное также верно.
На платформах с эффективной операцией журнала 2 [ какая? ], например M68000, ctz можно вычислить следующим образом:
- ctz ( x ) = журнал 2 ( x & −x )
где & обозначает побитовое И и -x обозначает двоичное дополнение от х . Выражение x & −x очищает все, кроме младшего 1 бита, так что старший и младший 1 бит остаются одинаковыми.
На платформах с эффективным подсчетом начальных нулей, таких как ARM и PowerPC, ffs можно вычислить следующим образом:
- ffs ( x ) = w - clz ( x & −x ) .
И наоборот, на машинах без операторов log 2 или clz clz можно вычислить с помощью ctz , хотя и неэффективно:
- clz = w - ctz (2 ⌈log 2 ( x ) ⌉ ) (который зависит от ctz, возвращающего w для нулевого входа)
На платформах с эффективным весом Хемминга (количество населения) операции , такие как SPARC «с POPC
[34] [35] или Blackfin » ы ONES
, [36] есть:
- ctz ( x ) = popcount (( x & −x ) - 1) , [37] [38] или ctz ( x ) = popcount (~ ( x | −x )) ,
- ffs ( x ) = popcount ( x ^ ~ - x ) [34]
- clz = 32 - popcount (2 ⌈log 2 ( x ) ⌉ - 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 ⌈log 2 (x) ⌉ (округление до ближайшей степени двойки) с использованием сдвигов и поразрядных операций ИЛИ [39] неэффективна для вычислений, как в этом 32-битном примере, и даже более неэффективна, если у нас есть 64-разрядная функция. бит или 128-битный операнд:
функция pow2 (x): if x = 0 return invalid // недействительно , если реализация определена (не в [0,63]) х ← х - 1 для каждого y в {1, 2, 4, 8, 16}: x ← x | (x >> y) вернуть x + 1
FFS
Поскольку ffs = ctz + 1 (POSIX) или ffs = ctz (другие реализации), могут использоваться соответствующие алгоритмы для ctz с возможным последним шагом добавления 1 к результату и возврата 0 вместо длины операнда для ввода все нулевые биты.
CTZ
Канонический алгоритм - это цикл, в котором подсчитываются нули, начиная с младшего бита до тех пор, пока не встретится 1 бит:
функция ctz1 (x), если x = 0, вернуть w t ← 1 г ← 0 а (x & t) = 0 t ← t << 1 г ← г + 1 вернуть г
Этот алгоритм выполняет O (n) раз и операций и на практике непрактичен из-за большого количества условных переходов.
Таблица поиска может исключить большинство ветвей:
table [0..2 n -1] = ctz (i) for i in 0..2 n -1 function ctz2 (x) if x = 0 return w г ← 0 цикл if (x & (2 n -1)) ≠ 0 return r + table [x & (2 n -1)] х ← х >> п г ← г + п
Параметр n является фиксированным (обычно 8) и представляет собой компромисс между пространством и временем . Петля также может быть полностью развернута . Но как линейный поиск, этот подход по-прежнему составляет O (n) по количеству бит в операнде.
Бинарный поиск реализация занимает логарифмическое число операций и ветвей, так как в этом 32-битной версии: [40] [41] Этот алгоритм может быть оказана помощь в виде таблицы , а также, заменив нижнюю три «если» заявления с 256 записи таблица поиска, использующая первый ненулевой байт, встреченный в качестве индекса.
функция ctz3 (x), если x = 0, вернуть 32 п ← 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 будет таким:
функция ctz4 (x) х & = -х вернуть w - (clz (x) + 1)
Алгоритм для 32-битного ctz использует последовательности де Брейна для построения минимальной совершенной хеш-функции, которая исключает все ветвления. [42] [43] Этот алгоритм предполагает, что результат умножения усечен до 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 возможных слова, которые при беззнаковом умножении и смещении хэша в правильную позицию в таблице. (Этот алгоритм не обрабатывает нулевой вход.)
CLZ
Канонический алгоритм проверяет один бит за раз, начиная с MSB, пока не будет найден ненулевой бит, как показано в этом примере. Он выполняется за время O (n), где n - длина в битах операнда, и не является практическим алгоритмом для общего использования.
функция clz1 (x), если x = 0, вернуть w t ← 1 << (w - 1) г ← 0 а (x & t) = 0 t ← t >> 1 г ← г + 1 вернуть г
Усовершенствованный подход к предыдущему циклическому подходу проверяет восемь битов за раз, затем использует поисковую таблицу из 256 (2 8 ) записей для первого ненулевого байта. Однако этот подход по-прежнему занимает O (n) по времени выполнения.
функция clz2 (x), если x = 0, вернуть w t ← 0xff << (w - 8) г ← 0 а (x & t) = 0 t ← t >> 8 г ← г + 8 return r + table [x >> (w - 8 - r)]
Двоичный поиск может сократить время выполнения до O (log 2 n):
функция clz3 (x), если x = 0, вернуть 32 п ← 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 8 = 256 1-байтовых записей) может заменить нижние 3 ветви в двоичном поиске. Для 64-битных операндов требуется дополнительная ветвь. Можно использовать поиск большей ширины, но максимальный практический размер таблицы ограничен размером кэша данных L1 на современных процессорах, который для многих составляет 32 КБ. Сохранение ветки более чем компенсируется задержкой промаха кэша L1 .
Алгоритм, похожий на умножение де Брюйна для CTZ, работает для CLZ, но вместо того, чтобы выделять наиболее значимый бит, он округляет до ближайшего целого числа формы 2 n −1 с использованием сдвигов и побитового ИЛИ: [44]
таблица [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) таблица возврата [((x * 0x07C4ACDD) >> 27)% 32]
Для процессоров с глубокими конвейерами, таких как Prescott и более поздние процессоры Intel, может быть быстрее заменить ветки побитовыми операторами AND и OR (даже если требуется гораздо больше инструкций), чтобы избежать сброса конвейера для ошибочно предсказанных ветвей (и эти типы ветвей по своей природе непредсказуемо):
функция clz5 (x) г = (х> 0xFFFF) << 4; х >> = г; д = (х> 0xFF) << 3; х >> = q; г | = д; д = (х> 0xF) << 2; х >> = q; г | = д; д = (х> 0x3) << 1; х >> = q; г | = д; г | = (х >> 1); return r;
На платформах, которые обеспечивают аппаратное преобразование целых чисел в числа с плавающей запятой, поле экспоненты может быть извлечено и вычтено из константы для вычисления количества ведущих нулей. Исправления необходимы для учета ошибок округления. [40] [45] Преобразование с плавающей запятой может иметь значительную задержку. Этот метод крайне непереносим и обычно не рекомендуется.
int x ; int r ; объединение { unsigned int u [ 2 ]; двойной d ; } t ; т . u [ LE ] = 0x43300000 ; // LE равно 1 для little-endian t . ты [ ! LE ] = x ; т . d - = 4503599627370496,0 ; r = ( t . u [ LE ] >> 20 ) - 0x3FF ; // log2 r ++ ; // CLZ
Приложения
Операция подсчета начальных нулей (clz) может использоваться для эффективной реализации нормализации , которая кодирует целое число как m × 2 e , где m имеет свой самый старший бит в известной позиции (например, в самой высокой позиции). Это, в свою очередь, можно использовать для реализации деления Ньютона – Рафсона , выполнения преобразования целых чисел в числа с плавающей запятой в программном обеспечении и других приложениях. [40] [46]
Счетчик ведущих нулей (clz) может использоваться для вычисления 32-битного предиката «x = y» (ноль, если истина, один, если ложь) через тождество clz (x - y) >> 5 , где «>>» беззнаковый сдвиг вправо. [47] Его можно использовать для выполнения более сложных битовых операций, таких как поиск первой строки из n 1 битов. [48] Выражение clz (x - y) 1 << (16 - clz (x - 1) / 2) - эффективное начальное предположение для вычисления квадратного корня из 32-битного целого числа с использованием метода Ньютона . [49] CLZ может эффективно реализовать подавление нуля , метод быстрого сжатия данных , который кодирует целое число как количество начальных нулевых байтов вместе с ненулевыми байтами. [50] Он также может эффективно генерировать экспоненциально распределенные целые числа, взяв clz равномерно случайных целых чисел. [40]
Логическое основание 2 можно использовать, чтобы предвидеть, произойдет ли переполнение при умножении, поскольку ⌈log 2 (xy) ⌉ ≤ ⌈log 2 (x) ⌉ + ⌈log 2 (y) ⌉ . [51]
Граф ведущих нулей и считать конечными нули могут быть использованы вместе , чтобы реализовать алгоритм цикла обнаружения Госпера в , [52] , который может найти период функции конечного диапазона с использованием ограниченных ресурсов. [41]
Алгоритм двоичного НОДА тратит много циклов удаления завершающих нулей; это может быть заменено подсчетом конечных нулей (ctz) с последующим сдвигом. Похожая петля появляется в вычислениях последовательности градин .
Битовый массив может быть использован для реализации очереди приоритета . В этом контексте поиск первого набора (ffs) полезен для эффективной реализации операции «вытягивать» или «извлекать элемент с наивысшим приоритетом». Планировщик реального времени ядра Linux внутренне использует sched_find_first_bit()
для этой цели. [53]
Количество конечных нули операция дает простое оптимальное решение башне Ханой проблема: диски пронумерованы от нуля, а при перемещении к , номер диска CTZ ( к ) перемещаются минимально возможное расстояние вправо ( по кругу назад вокруг к оставил по мере надобности). Он также может сгенерировать код Грея , взяв произвольное слово и перевернув бит ctz ( k ) на шаге k . [41]
Смотрите также
- Наборы команд управления битами (BMI) для процессоров Intel и AMD на базе x86
- Конечный ноль
- Ведущий ноль
- Конечная цифра
- Ведущая цифра
Заметки
- ^ Использование битовых операций с машинным словом, отличным от беззнакового, может привести к неопределенным результатам.
- ^ Эти четыре операции также имеют (гораздо реже) инвертированные версии:
- найти первый ноль ( ffz ), который определяет индекс младшего значащего нулевого бита;
- подсчет конечных единиц , который считает количество единиц единицы , следующих за младшим значащим нулевым битом.
- подсчитывать ведущие единицы , который считает количество единиц единицы , предшествующих старшему значащему нулевому биту;
- найти индекс старшего значащего нулевого бита, который является инвертированной версией двоичного логарифма .
Рекомендации
- ^ Андерсон . Найдите логарифмическую базу 2 целого числа с набором MSB N за O (N) операций (очевидный способ) .
- ^ a b "FFS (3)" . Руководство программиста Linux . Архивы ядра Linux . Проверено 2 января 2012 .
- ^ "Справочник инструкций ARM> Общие инструкции обработки данных ARM> CLZ" . Руководство по сборщику ARM Developer Suite . ARM . Проверено 3 января 2012 .
- ^ «Документ архитектуры AVR32» (PDF) (редакция CORP072610). Корпорация Атмель . 2011. 32000D – 04/201. Архивировано из оригинального (PDF) 25 октября 2017 года . Проверено 22 октября 2016 .
- ^ а б Справочное руководство по альфа-архитектуре (PDF) . Compaq . 2002. С. 4-32, 4-34.
- ^ а б Руководство разработчика программного обеспечения для архитектур Intel 64 и IA-32 . Том 2А. Intel . С. 3-92–3-97.
|volume=
имеет дополнительный текст ( справка ) Номер заказа 325383. - ^ Руководство программиста по архитектуре AMD64 Том 3: Общие и системные инструкции (PDF) . 3 . Advanced Micro Devices (AMD). 2011. С. 204–205. Публикация № 24594.
- ^ «Руководство программиста по архитектуре AMD64, том 3: Общие и системные инструкции» (PDF) . Технология AMD64 (ред. Версии 3.28). Advanced Micro Devices (AMD). Сентябрь 2019 [2013]. Публикация № 24594. Архивировано (PDF) из оригинала 30.09.2019 . Проверено 2 января 2014 .
- ^ Руководство разработчика программного обеспечения для архитектуры Intel Itanium. Том 3: Набор инструкций Intel Itanium . 3 . Intel . 2010. С. 3:38. Архивировано 26 июня 2019 года.
- ^ а б Архитектура MIPS для программистов. Том II-A: Набор инструкций MIPS32 (редакция 3.02). MIPS Technologies . 2011. С. 101–102.
- ^ а б Архитектура MIPS для программистов. Том II-A: Набор инструкций MIPS64 (редакция 3.02). MIPS Technologies . 2011. С. 105, 107, 122, 123.
- ^ Справочное руководство программиста семейства M68000 (включая инструкции CPU32) (PDF) (редакция 1-го издания ). Motorola . 1992. С. 4-43–4-45. M68000PRM / AD. Архивировано из оригинального (PDF) на 2019-12-08.
- ^ Фрей, Брэд. «Глава 3.3.11 Логические инструкции для фиксированной точки». Книга по архитектуре PowerPC (ред. Версии 2.02). IBM . п. 70.
- ^ «Глава 3.3.13 Логические команды с фиксированной точкой - Глава 3.3.13.1 64-битные логические команды с фиксированной точкой». Power ISA версии 3.0B . IBM . С. 95, 98.
- ^ а б Вольф, Клиффорд (22 марта 2019 г.). "RISC-V" B "Расширение управления битами для RISC-V" (PDF) . Github (черновик) (ред. V0.37) . Проверено 9 января 2020 .
- ^ Oracle SPARC Architecture 2011 . Oracle . 2011 г.
- ^ Справочное руководство по архитектуре VAX (PDF) . Корпорация цифрового оборудования (DEC). 1987. С. 70–71. Архивировано (PDF) из оригинала 29.09.2019 . Проверено 9 января 2020 .
- ^ а б в «Глава 22. Векторные целочисленные команды». Принципы работы IBM z / Architecture (PDF) (Одиннадцатое изд.). IBM . Март 2015. С. 7-219–22-10. SA22-7832-10 . Проверено 10 января 2020 .
- ^ а б «ФФС (3)» . Mac OS X Developer Library . Apple, Inc. 1994-04-19 . Проверено 4 января 2012 .
- ^ «ФФС (3)» . Руководство по функциям библиотеки FreeBSD . Проект FreeBSD . Проверено 4 января 2012 .
- ^ «Другие встроенные функции, предоставляемые GCC» . Использование коллекции компиляторов GNU (GCC) . Фонд свободного программного обеспечения, Inc. Проверено 2015-11-14 .
- ^ "Журнал изменений GCC 3.4.0" . GCC 3.4.0 . Фонд свободного программного обеспечения, Inc. Проверено 2015-11-14 .
- ^ "Расширения языка Clang - глава" Встроенные функции " . Команда Clang . Проверено 9 апреля 2017 .
Clang поддерживает ряд встроенных библиотечных функций с тем же синтаксисом, что и GCC.
- ^ «Исходный код Clang» . Команда LLVM, Университет Иллинойса в Урбана-Шампейн . Проверено 9 апреля 2017 .
- ^ «_BitScanForward, _BitScanForward64» . Visual Studio 2008: Visual C ++: встроенные функции компилятора . Microsoft . Проверено 21 мая 2018 .
- ^ «_BitScanReverse, _BitScanReverse64» . Visual Studio 2008: Visual C ++: встроенные функции компилятора . Microsoft . Проверено 21 мая 2018 .
- ^ «__lzcnt16, __lzcnt, __lzcnt64» . Visual Studio 2008: Visual C ++: встроенные функции компилятора . Microsoft . Проверено 3 января 2012 .
- ^ «Intel Intrinsics Guide» . Intel . Проверено 3 апреля 2020 .
- ^ Справочник по компилятору Intel C ++ для встроенных функций Linux . Intel . 2006. с. 21.
- ^ Руководство по программированию NVIDIA CUDA (PDF) (ред. Версии 3.0). NVIDIA . 2010. с. 92.
- ^ " ' llvm.ctlz. *' Внутренний, 'llvm.cttz. *' Внутренний" . Справочное руководство по языку LLVM . Инфраструктура компилятора LLVM . Проверено 23 февраля 2016 .
- ^ Смит, Ричард (01.04.2020). N4861 Рабочий проект стандарта языка программирования C ++ (PDF) . ИСО / МЭК. С. 1150–1153 . Проверено 25 мая 2020 .
- ^ "Заголовок стандартной библиотеки <бит>" . cppreference.com . Проверено 25 мая 2020 .
- ^ а б SPARC International, Inc. (1992). «A.41: Подсчет населения. Примечание по программированию» (PDF) . Руководство по архитектуре SPARC: версия 8 (версия 8 - ред.). Энглвуд Клиффс, Нью-Джерси, США: Прентис Холл . С. 231 . ISBN 978-0-13-825001-0.
- ^ Уоррен младший, Генри С. (2013) [2002]. Восторг хакера (2-е изд.). Эддисон Уэсли - ISBN Pearson Education, Inc. 978-0-321-84268-8. 0-321-84268-5.
- ^ Справочник по набору команд Blackfin (предварительная редакция). Аналоговые устройства . 2001. С. 8–24. Каталожный номер 82-000410-14.
- ^ Диц, Генри Гордон . «Агрегированные магические алгоритмы» . Университет Кентукки . Архивировано 31 октября 2019 года.
- ^ Изенберг, Герд (2019-11-03) [2012]. «BitScanProtected» . Вики по шахматному программированию (CPW) . Архивировано 9 января 2020 года . Проверено 9 января 2020 .
- ^ Андерсон . Округлите до ближайшей степени 2 .
- ^ а б в г Уоррен . Глава 5-3: Подсчет ведущих нулей.
- ^ a b c Уоррен . Глава 5-4: Подсчет конечных нулей.
- ^ Лейзерсон, Чарльз Э .; Прокоп, Харальд ; Рэндалл, Кейт Х. (1998-07-07). «Использование последовательностей де Брейна для индексации 1 в компьютерном слове» (PDF) . Лаборатория компьютерных наук Массачусетского технологического института, Кембридж, Массачусетс, США. Архивировано (PDF) из оригинала 09.01.2020 . Проверено 9 января 2020 .
- ^ Буш, Филип (2009-03-01) [2009-02-21]. «HOWTO по вычислению конечных нулей» (PDF) . Архивировано (PDF) из оригинала на 2016-08-01 . Проверено 9 января 2020 .
- ^ Андерсон . Найдите логарифмическую базу 2 N-битного целого числа за O (lg (N)) операций с умножением и поиском .
- ^ Андерсон . Найдите целочисленное логическое основание 2 целого числа с 64-битным числом с плавающей запятой IEEE .
- ^ Слосс, Эндрю Н .; Саймс, Доминик; Райт, Крис (2004). Руководство разработчика системы ARM по проектированию и оптимизации системного программного обеспечения (1-е изд.). Сан-Франциско, Калифорния, США: Морган Кауфманн . С. 212–213. ISBN 978-1-55860-874-0.
- ^ Уоррен . Глава 2-11: Сравнение предикатов.
- ^ Уоррен . Глава 6-2: Найдите первую строку из 1 разряда заданной длины.
- ^ Уоррен . Глава 11-1: Целочисленный квадратный корень.
- ^ Шлегель, Бенджамин; Гемулла, Райнер ; Ленер, Вольфганг (июнь 2010 г.). Быстрое целочисленное сжатие с использованием инструкций SIMD . Материалы шестого международного семинара по управлению данными на новом оборудовании (DaMoN 2010) . С. 34–40. CiteSeerX 10.1.1.230.6379 . DOI : 10.1145 / 1869389.1869394 . ISBN 978-1-45030189-3.
- ^ Уоррен . Глава 2-12: Обнаружение переполнения.
- ^ Госпер, Билл (апрель 1995 г.) [1972-02-29]. Бейкер-младший, Генри Гивенс (ред.). «Петлевой детектор» . ХАКМЕМ (перепечатано и преобразовано под ред.). Кембридж, Массачусетс, США: Лаборатория искусственного интеллекта , Массачусетский технологический институт (MIT). AI Memo 239 Item 132. Архивировано 8 октября 2019 года . Проверено 9 января 2020 .
- ^ Аас, Джош (17 февраля 2005 г.). Общие сведения о планировщике ЦП Linux 2.6.8.1 (PDF) . Silicon Graphics, Inc. (SGI). п. 19. Архивировано (PDF) из оригинала на 19.05.2017 . Проверено 9 января 2020 .
дальнейшее чтение
- Уоррен младший, Генри С. (2013) [2002]. Восторг хакера (2-е изд.). Эддисон Уэсли - ISBN Pearson Education, Inc. 978-0-321-84268-8. 0-321-84268-5.
- Андерсон, Шон Эрон (2005) [1997]. "Bit Twiddling Hacks" . Стэнфордский университет . Архивировано 8 января 2020 года . Проверено 3 января 2012 .(NB. Перечислены несколько эффективных общедоступных реализаций C для подсчета конечных нулей и логической базы 2. )
Внешние ссылки
- Руководство Intel по внутренним функциям
- Wiki по шахматному программированию: BitScan : подробное объяснение ряда методов реализации для ffs (называемых LS1B) и логической базы 2 (называемых MS1B).