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

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

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

• 1 Примеры
• 2 Поддержка оборудования
• 3 Поддержка инструментов и библиотек
• 4 Свойства и отношения
• 5 Эмуляция программного обеспечения
  • 5.1 2
  • 5.2 FFS
  • 5.3 CTZ
  • 5.4 CLZ
• 6 Приложения
• 7 См. Также
• 8 Примечания
• 9 Ссылки
• 10 Дополнительная литература
• 11 Внешние ссылки

Данные следующее 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 возвращает ноль. Реализация функции find first set как с логической базой 2, так и с нулевой базой обычно возвращает неопределенный результат для нулевого слова.

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

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

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

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

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

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

ctz (x) = log 2 (x - 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) (который зависит от ctz, возвращающего w для нулевого ввода)

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

ctz (x) = popcount ((x −x) - 1),

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 // недействительно, если реализация определена (не в [0,63]) x ← x - 1 для каждого y in{1, 2, 4, 8, 16}: x ← x | (x>>y) return x + 1

FFS

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

CTZ

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

function ctz1 (x) if x = 0 return wt ← 1 r ← 0 while (x t) = 0 t ← t << 1 r ← r + 1 return r

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

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

table [0..2-1] = ctz (i) для i in0..2-1 функция ctz2 (x) if x = 0 return wr ← 0 loop if(x (2-1)) ≠ 0 return r + table [x (2-1)] x ← x>>nr ← r + n

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

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

function ctz3 (x) if x = 0 return 32 n ← 0 if (x 0x0000FFFF) = 0: n ← n + 16, x ← x>>16 если (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 бит.

для i из 0 to31: table [(0x077CB531 * (1 << i))>>27] ← i // таблица [0..31] инициализирована function ctz5 (x) return table [((x -x) * 0x077CB531)>>27]

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

CLZ

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

function clz1 (x) if x = 0 return wt ← 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 wt ← 0xff << w - 8 r ← 0 while (x t) = 0 t ← t>>8 r ← r + 8 return r + table [x>>w-8]

Двоичный поиск может сократить время выполнения до O (log 2 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 если (x 0xC0000000) = 0: n ← n + 2, x ← x << 2 if (x 0x80000000) = 0: n ← n + 1 return n

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

Алгоритм, аналогичный умножению де Брейна для CTZ, работает для CLZ, но вместо выделения наиболее значимого бита он округляет до ближайшего целого числа в форме 2-1 с использованием сдвигов и побитового ИЛИ:

таблица [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 in{1, 2, 4, 8, 16}: x ← x | (x>>y) return table [(x * 0x07C4ACDD)>>27]

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

function clz5 (x) r = (x>0xFFFF) << 4; x>>= г; q = (x>0xFF) << 3; x>>= q; г | = д; q = (x>0xF) << 2; x>>= q; г | = д; q = (x>0x3) << 1; x>>= q; г | = д; г | = (х>>1); return r;

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

int x; int r; объединение {unsigned int u [2]; двойной 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, где m имеет старший бит в известной позиции ( например высшая позиция). Это, в свою очередь, может использоваться для реализации деления Ньютона-Рафсона, выполнения преобразования целых чисел в с плавающей запятой в программном обеспечении и других приложениях.

Подсчет ведущих нулей (clz) может использоваться для вычисления 32-битного предиката «x = y» (ноль, если истина, один, если ложь) через тождество clz (x - y)>>5, где «>>» - сдвиг вправо без знака. Его можно использовать для выполнения более сложных битовых операций, таких как поиск первой строки из n 1 бит. Выражение clz (x - y) 1 << (16 − clz(x − 1)/2) is an effective initial guess for computing the square root of a 32-bit integer using Метод Ньютона. CLZ может эффективно реализовать подавление нуля, метод быстрого сжатия данных, который кодирует целое число как количество начальных нулевых байтов вместе с ненулевыми байтами. Он также может эффективно генерировать экспоненциально распределенные целые числа, взяв clz из равномерно случайных целых чисел.

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

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

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

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

Операция подсчета конечных нулей дает простое оптимальное решение для Tower проблемы Ханоя : диски пронумерованы с нуля, и при перемещении 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]. "Бит-твиддлинг-хаки". Стэнфордский университет. Архивировано из оригинала на 2020-01-08. Проверено 03.01.2012. (NB. Перечисляет несколько эффективных реализаций C в открытом доступе для подсчета конечных нулей и базы журналов 2.)

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