Найти первый набор - Find first set

В компьютере программного обеспечения и оборудование, найти первый набор (ffs) или же найди первый это битовая операция что, учитывая беззнаковый машинное слово,[nb 1] обозначает индекс или позицию младшего значащего бита, равного единице в слове, считая от позиции младшего значащего бита. Почти эквивалентная операция подсчитывать конечные нули (ctz) или же количество завершающих нулей (NTZ), который считает количество нулевых битов, следующих за младшим значащим битом. Дополнительная операция, которая находит индекс или позицию самого значимого бита набора, - бревенчатая база 2, так называемый, потому что он вычисляет двоичный логарифм ⌊бревно2(Икс)⌋.[1] Это тесно связанный к считать ведущие нули (clz) или же количество ведущих нулей (нлз), который подсчитывает количество нулевых битов, предшествующих старшему значащему биту.[nb 2]Есть два распространенных варианта поиска первого набора: POSIX определение, которое начинает индексирование битов с 1,[2] здесь обозначен как ffs, и вариант, который начинает индексирование битов с нуля, что эквивалентно ctz и поэтому будет называться этим именем.

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

Примеры

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

0000 0000 0000 0000 1000 0000 0000 1000

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

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

1111 1111 1111 1111 0111 1111 1111 0111

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

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

Поддержка оборудования

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

ПлатформаМнемоническийИмяШирина операндаОписаниеПо заявке на 0
РУКА (Архитектура ARMv5T и выше )
Кроме Cortex-M0 / M0 + / M1 / ​​M23		clz[3]Считайте ведущие нули32clz32
РУКА (ARMv8-A архитектура )clzСчитайте ведущие нули32, 64clzШирина операнда
AVR32clz[4]Считайте ведущие нули32clz32
DEC Alphactlz[5]Считайте ведущие нули64clz64
cttz[5]Считать конечные нули64ctz64
Intel 80386 и позжеbsf[6]Битовое сканирование вперед16, 32, 64ctzНеопределенный; устанавливает нулевой флаг
бср[6]Битовое сканирование в обратном направлении16, 32, 64Бревенчатое основание 2Неопределенный; устанавливает нулевой флаг
x86 поддерживающий ИМТ1 или же ПРОlzcnt[7]Считайте ведущие нули16, 32, 64clzШирина операнда; устанавливает флаг переноса
x86 поддерживающий ИМТ1tzcnt[8]Считать конечные нули16, 32, 64ctzШирина операнда; устанавливает флаг переноса
Itaniumclz[9]Считайте ведущие нули64clz64
MIPSclz[10][11]Подсчитайте ведущие нули в Word32, 64clzШирина операнда
Clo[10][11]Подсчитайте ведущих в слове32, 64CloШирина операнда
Motorola 68020 и позжеbfffo[12]Найти первую в битовом полеПроизвольныйБревенчатое основание 2Смещение поля + ширина поля
PDP-10jffoПрыгай, если найдешь первого36ctz0; нет операции
МОЩНОСТЬ /PowerPC /Питание ISAcntlz / cntlzw / cntlzd[13]Считайте ведущие нули32, 64clzШирина операнда
Power ISA 3.0 и вышеcnttzw / cnttzd[14]Подсчет конечных нулей32, 64ctzШирина операнда
RISC-V (Расширение "B") (черновик)clz[15]Считайте ведущие нули32, 64clzШирина операнда
ctz[15]Подсчет конечных нулей32, 64ctzШирина операнда
SPARC Oracle Architecture 2011 и новееlzcnt (синоним: lzd)[16]Ведущий нулевой счет64clz64
VAXffs[17]Найти первый набор0–32ctzШирина операнда; устанавливает нулевой флаг
IBM z / АрхитектураFlogr[18]Найдите крайний левый64clz64
vclz[18]Векторный подсчет ведущих нулей8, 16, 32, 64clzШирина операнда
vctz[18]Счетчик векторов в конце нулей8, 16, 32, 64ctzШирина операнда

На некоторых платформах 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,
длинный		fls ("найти последний набор") вычисляет (логарифм с основанием 2) + 1.0
FreeBSD 7.1 библиотека libc[20]ffsll
flsll		Библиотечная функциядолго долго0
GCC 3.4.0[21][22]
Лязг 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, представленной в ИМТ1 или же ПРО.Ширина операнда
Компилятор Intel C ++_bit_scan_forward
_bit_scan_reverse[28][29]		Внутренние функции компилятораintНеопределенный
NVIDIA CUDA[30]__clzФункции32-бит, 64-битКомпилируется с меньшим количеством инструкций на GeForce 400 серии32
__ffs0
LLVMllvm.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 стандартная библиотека, в заголовке <bit>[32][33]bit_ceil bit_floor
bit_width
countl_zero countl_one
countr_zero countr_one		Библиотечная функциябеззнаковый символ,
беззнаковый короткий,
беззнаковое int,
беззнаковый длинный,
беззнаковый длинный длинный

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

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

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

На платформах с эффективным журналом2 операция[который? ] например M68000, ctz можно вычислить:

ctz (Икс) = журнал2(Икс & −x)

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

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

ffs (Икс) = w - clz (Икс & −x).

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

clz = ш - ctz (2⌈бревно2(Икс)⌉) (что зависит от ctz возвращение ш для нулевого входа)

На платформах с эффективным Вес Хэмминга (подсчет населения) операция, такая как SPARC с POPC[34][35] или же Blackfin с ОДИН,[36] есть:

ctz (Икс) = popcount ((Икс & −x) − 1),[37][38]
ffs (Икс) = popcount (Икс ^ ~−Икс)[34]
clz = 32 - popcount (2⌈бревно2(Икс)⌉ − 1)

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

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

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

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

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

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

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

2п

Функция 2⌈бревно2(Икс)⌉ (округлить до ближайшей степени двойки) с использованием сдвигов и побитового ИЛИ[39] неэффективно для вычислений, как в этом 32-битном примере, и еще более неэффективно, если у нас есть 64-битный или 128-битный операнд:

функция pow2 (x): если x = 0 возврат инвалид  // инвалид определяется реализацией (не в [0,63]) x ← x - 1 для каждого у в {1, 2, 4, 8, 16}: x ← x | (х >> у) возвращаться х + 1

FFS

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

CTZ

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

функция ctz1 (x) если х = 0 возвращаться w t ← 1 r ← 0 пока (x & t) = 0 t ← t << 1 r ← r + 1 возвращаться р

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

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

таблица [0..2п-1] = ctz (i) за я в 0..2п-1функция ctz2 (x) если х = 0 возвращаться w r ← 0 петля        если (x & (2п-1)) ≠ 0            возвращаться r + таблица [x & (2п-1)] x ← x >> n r ← r + n

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

А бинарный поиск реализация требует логарифмического количества операций и ветвей, как в этой 32-битной версии:[40][41]Этому алгоритму также может помочь таблица, заменяющая три нижних оператора if на поисковую таблицу из 256 записей, использующую первый ненулевой байт, обнаруженный в качестве индекса.

функция ctz3 (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 возвращаться п

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

функция ctz4 (x) x & = -x возвращаться ш - (clz (x) + 1)

Алгоритм для 32-битного ctz использует последовательности де Брейна построить минимальная идеальная хеш-функция что устраняет все ветви.[42][43]Этот алгоритм предполагает, что результат умножения усечен до 32 бит.

за я из 0 к 31: table [(0x077CB531 * (1 << i)) >> 27] ← i // таблица [0..31] инициализированафункция ctz5 (х) возвращаться таблица [((x & -x) * 0x077CB531) >> 27]

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

CLZ

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

функция clz1 (x) если х = 0 возвращаться w t ← 1 << w - 1 r ← 0 пока (x & t) = 0 t ← t >> 1 r ← r + 1 возвращаться р

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

функция clz2 (x) если х = 0 возвращаться w t ← 0xff << w - 8 r ← 0 пока (x & t) = 0 t ← t >> 8 r ← r + 8 возвращаться r + таблица [x >> w-8]

Двоичный поиск может сократить время выполнения до O (журнал2п):

функция clz3 (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 возвращаться п

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

Алгоритм, похожий на умножение де Брюйна для CTZ, работает для CLZ, но вместо того, чтобы выделять самый старший бит, он округляет до ближайшего целого числа формы 2п−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) для каждого у в {1, 2, 4, 8, 16}: x ← x | (х >> у) возвращаться таблица [(x * 0x07C4ACDD) >> 27]

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

функция clz5 (x) r = (x> 0xFFFF) << 4; х >> = г; д = (х> 0xFF) << 3; х >> = q; г | = д; д = (х> 0xF) << 2; х >> = q; г | = д; д = (х> 0x3) << 1; х >> = q; г | = д; г | = (х >> 1); возвращаться р;

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

int Икс; int р;союз { беззнаковый int ты[2]; двойной d; } т; т.ты[LE] = 0x43300000;  // LE равно 1 для прямого порядка байтовт.ты[!LE] = Икс;т.d -= 4503599627370496.0;р = (т.ты[LE] >> 20) - 0x3FF;  // log2р++;  // CLZ

Приложения

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

Подсчет начальных нулей (clz) можно использовать для вычисления 32-битного предиката «x = y» (ноль, если истина, один, если ложь) через тождество clz (x - y) >> 5, где ">>" - сдвиг вправо без знака.[47] Его можно использовать для выполнения более сложных битовых операций, таких как поиск первой строки п 1 бит.[48] Выражение clz (x - y) 1 << (16 - clz (x - 1) / 2) является эффективным начальным предположением для вычисления квадратного корня из 32-битного целого числа с использованием Метод Ньютона.[49] CLZ может эффективно реализовать нулевое подавление, быстрый Сжатие данных метод, который кодирует целое число как количество начальных нулевых байтов вместе с ненулевыми байтами.[50] Он также может эффективно генерировать экспоненциально распределенный целые числа, взяв clz из равномерно случайный целые числа.[40]

Основание журнала 2 можно использовать, чтобы предвидеть, произойдет ли переполнение при умножении, поскольку ⌈бревно2(ху) ⌉ ≤ ⌈log2(x) ⌉ + ⌈log2(у) ⌉.[51]

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

В двоичный алгоритм GCD тратит много циклов на удаление завершающих нулей; это может быть заменено подсчетом конечных нулей (ctz) с последующим сдвигом. Аналогичный цикл появляется при вычислении последовательность градин.

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

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

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

Примечания

  1. ^ Использование битовых операций с машинным словом, отличным от беззнакового, может привести к неопределенным результатам.
  2. ^ Эти четыре операции также имеют (гораздо реже) инвертированные версии:
    • найти первый ноль (ffz), который определяет индекс младшего значащего нулевого бита;
    • подсчитывать конечные, который подсчитывает количество единиц, следующих за младшим значащим нулевым битом.
    • посчитать ведущие, который подсчитывает количество единиц, предшествующих старшему значащему нулю;
    • найти индекс старшего нулевого бита, который является инвертированной версией двоичный логарифм.

Рекомендации

  1. ^ Андерсон. Найдите логарифмическую базу 2 целого числа с MSB N, установленным за O (N) операций (очевидный способ).
  2. ^ а б «ФФС (3)». Руководство программиста Linux. Архивы ядра Linux. Получено 2012-01-02.
  3. ^ "Справочник инструкций ARM> Общие инструкции обработки данных ARM> CLZ". Руководство по сборщику ARM Developer Suite. РУКА. Получено 2012-01-03.
  4. ^ «Архитектурный документ AVR32» (PDF) (Издание CORP072610). Atmel Corporation. 2011. 32000D – 04/201. Архивировано из оригинал (PDF) на 2017-10-25. Получено 2016-10-22.
  5. ^ а б Справочное руководство по альфа-архитектуре (PDF). Compaq. 2002. С. 4-32, 4-34.
  6. ^ а б Руководство разработчика программного обеспечения для архитектур Intel 64 и IA-32. Том 2А. Intel. С. 3-92–3-97. Номер заказа 325383.
  7. ^ Руководство программиста по архитектуре AMD64, том 3: Общие и системные инструкции (PDF). 3. Продвинутые микроустройства (AMD). 2011. С. 204–205. Публикация № 24594.
  8. ^ «Руководство программиста по архитектуре AMD64, том 3: общие и системные инструкции» (PDF). Технология AMD64 (версия 3.28 изд.). Продвинутые микроустройства (AMD). Сентябрь 2019 [2013]. Публикация № 24594. В архиве (PDF) из оригинала на 2019-09-30. Получено 2014-01-02.
  9. ^ Руководство разработчика программного обеспечения для архитектуры Intel Itanium. Том 3: Набор инструкций Intel Itanium. 3. Intel. 2010. С. 3:38. В архиве из оригинала от 26.06.2019.
  10. ^ а б Архитектура MIPS для программистов. Том II-A: Набор инструкций MIPS32 (Редакция 3.02 ред.). MIPS Technologies. 2011. С. 101–102.
  11. ^ а б Архитектура MIPS для программистов. Том II-A: Набор инструкций MIPS64 (Редакция 3.02 ред.). MIPS Technologies. 2011. С. 105, 107, 122, 123.
  12. ^ Справочное руководство программиста семейства M68000 (включает инструкции CPU32) (PDF) (редакция 1-го изд.). Motorola. 1992. С. 4-43–4-45. M68000PRM / AD. Архивировано из оригинал (PDF) на 2019-12-08.
  13. ^ Фрей, Брэд. «Глава 3.3.11 Логические инструкции для фиксированной точки». Книга по архитектуре PowerPC (Версия 2.02 ред.). IBM. п. 70.
  14. ^ «Глава 3.3.13 Логические команды с фиксированной точкой - Глава 3.3.13.1 64-битные логические команды с фиксированной точкой». Power ISA версии 3.0B. IBM. С. 95, 98.
  15. ^ а б Вольф, Клиффорд (22 марта 2019 г.). "RISC-V" B "Расширение управления битами для RISC-V" (PDF). Github (Проект) (v0.37 изд.). Получено 2020-01-09.
  16. ^ Архитектура Oracle SPARC 2011. Oracle. 2011.
  17. ^ Справочное руководство по архитектуре VAX (PDF). Корпорация цифрового оборудования (DEC). 1987. С. 70–71. В архиве (PDF) из оригинала на 2019-09-29. Получено 2020-01-09.
  18. ^ а б c «Глава 22. Векторные целочисленные команды». Принципы работы IBM z / Architecture (PDF) (Одиннадцатое изд.). IBM. Март 2015. С. 7-219–22-10. SA22-7832-10. Получено 2020-01-10.
  19. ^ а б «ФФС (3)». Библиотека разработчика Mac OS X. Apple, Inc. 1994-04-19. Получено 2012-01-04.
  20. ^ «ФФС (3)». Руководство по функциям библиотеки FreeBSD. Проект FreeBSD. Получено 2012-01-04.
  21. ^ «Другие встроенные функции, предоставляемые GCC». Использование коллекции компиляторов GNU (GCC). Фонд свободного программного обеспечения, Inc. Получено 2015-11-14.
  22. ^ "Журнал изменений GCC 3.4.0". GCC 3.4.0. Фонд свободного программного обеспечения, Inc. Получено 2015-11-14.
  23. ^ "Расширения языка Clang - глава" Встроенные функции ". Команда Clang. Получено 2017-04-09. Clang поддерживает ряд встроенных библиотечных функций с тем же синтаксисом, что и GCC.
  24. ^ «Исходный код Clang». Команда LLVM, Университет Иллинойса в Урбана-Шампейн. Получено 2017-04-09.
  25. ^ "_BitScanForward, _BitScanForward64". Visual Studio 2008: Visual C ++: встроенные функции компилятора. Microsoft. Получено 2018-05-21.
  26. ^ "_BitScanReverse, _BitScanReverse64". Visual Studio 2008: Visual C ++: встроенные функции компилятора. Microsoft. Получено 2018-05-21.
  27. ^ "__lzcnt16, __lzcnt, __lzcnt64". Visual Studio 2008: Visual C ++: встроенные функции компилятора. Microsoft. Получено 2012-01-03.
  28. ^ «Руководство Intel по внутренним функциям». Intel. Получено 2020-04-03.
  29. ^ Справочник по компилятору Intel C ++ для встроенных функций Linux. Intel. 2006. с. 21.
  30. ^ Руководство по программированию NVIDIA CUDA (PDF) (Версия 3.0 изд.). NVIDIA. 2010. с. 92.
  31. ^ "'llvm.ctlz. * 'Внутренний,' llvm.cttz. * 'Внутренний ". Справочное руководство по языку LLVM. Инфраструктура компилятора LLVM. Получено 2016-02-23.
  32. ^ Смит, Ричард (01.04.2020). N4861 Рабочий проект стандарта языка программирования C ++ (PDF). ИСО / МЭК. стр. 1150–1153. Получено 2020-05-25.
  33. ^ "Заголовок стандартной библиотеки <бит>". cppreference.com. Получено 2020-05-25.
  34. ^ а б SPARC International, Inc. (1992). «A.41: Подсчет населения. Примечание по программированию» (PDF). Руководство по архитектуре SPARC: версия 8 (Версия 8-е изд.). Энглвуд Клиффс, Нью-Джерси, США: Prentice Hall. стр.231. ISBN  978-0-13-825001-0.
  35. ^ Уоррен младший, Генри С. (2013) [2002]. Хакерское наслаждение (2-е изд.). Эддисон Уэсли - Pearson Education, Inc. ISBN  978-0-321-84268-8. 0-321-84268-5.
  36. ^ Справочник по набору инструкций Blackfin (Предварительная ред.). Аналоговые устройства. 2001. С. 8–24. Каталожный номер 82-000410-14.
  37. ^ Диц, Генри Гордон. «Агрегированные магические алгоритмы». Университет Кентукки. В архиве с оригинала от 31.10.2019.
  38. ^ Изенберг, Герд (2019-11-03) [2012]. «BitScanProtected». Вики по шахматному программированию (CPW). В архиве из оригинала на 2020-01-09. Получено 2020-01-09.
  39. ^ Андерсон. Округлить до ближайшей степени двойки.
  40. ^ а б c d Уоррен. Глава 5-3: Подсчет ведущих нулей.
  41. ^ а б c Уоррен. Глава 5-4: Подсчет конечных нулей.
  42. ^ Лейзерсон, Чарльз Э.; Прокоп, Харальд; Рэндалл, Кейт Х. (1998-07-07). «Использование последовательностей де Брейна для индексации 1 в компьютерном слове» (PDF). Лаборатория компьютерных наук Массачусетского технологического института, Кембридж, Массачусетс, США. В архиве (PDF) из оригинала на 2020-01-09. Получено 2020-01-09.
  43. ^ Буш, Филип (2009-03-01) [2009-02-21]. "Вычисление конечных нулей HOWTO" (PDF). В архиве (PDF) из оригинала на 2016-08-01. Получено 2020-01-09.
  44. ^ Андерсон. Найдите логарифмическую базу 2 N-битного целого числа за O (lg (N)) операций с умножением и поиском.
  45. ^ Андерсон. Найдите целочисленный журнал с основанием 2 целого числа с 64-битным IEEE float.
  46. ^ Sloss, Andrew N .; Саймс, Доминик; Райт, Крис (2004). Руководство разработчика системы ARM по проектированию и оптимизации системного программного обеспечения (1-е изд.). Сан-Франциско, Калифорния, США: Морган Кауфманн. С. 212–213. ISBN  978-1-55860-874-0.
  47. ^ Уоррен. Глава 2-11: Сравнение предикатов.
  48. ^ Уоррен. Глава 6-2: Найдите первую строку из 1 разряда заданной длины.
  49. ^ Уоррен. Глава 11-1: Целочисленный квадратный корень.
  50. ^ Шлегель, Бенджамин; Гемулла, Райнер; Ленер, Вольфганг (Июнь 2010 г.). Быстрое целочисленное сжатие с использованием инструкций SIMD. Материалы шестого международного семинара по управлению данными на новом оборудовании (DaMoN 2010). С. 34–40. CiteSeerX  10.1.1.230.6379. Дои:10.1145/1869389.1869394. ISBN  978-1-45030189-3.
  51. ^ Уоррен. Глава 2-12: Обнаружение переполнения.
  52. ^ Госпер, Билл (Апрель 1995 г.) [1972-02-29]. Бейкер-младший, Генри Гивенс (ред.). «Петлевой детектор». HAKMEM (перепечатано и преобразовано ред.). Кембридж, Массачусетс, США: Лаборатория искусственного интеллекта, Массачусетский Институт Технологий (Массачусетский технологический институт). Памятка AI 239, пункт 132. В архиве из оригинала на 2019-10-08. Получено 2020-01-09.
  53. ^ Аас, Джош (17 февраля 2005 г.). Понимание планировщика ЦП Linux 2.6.8.1 (PDF). Silicon Graphics, Inc. (SGI). п. 19. В архиве (PDF) из оригинала на 19.05.2017. Получено 2020-01-09.

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

внешняя ссылка