Find first set

Пошук першої одиниці (англ. find first set, ffs або find first one) — бітова операція, яка визначає індекс (номер, позицію) найменш значущого біта в машинному слові (біта, який має значення одиниці). Майже еквівалентною операцією є підрахунок залишкових нулів (англ. count trailing zeros, ctz або number of trailing zeros, ntz), яка рахує кількість нульових бітів після найменш значущого (біта зі значенням один).
Дуальною (парною) є операція, яка визначає індекс чи позицію найбільш значущого біта. Для цілих чисел вона фактично визначає цілу частину логарифма за основою 2 ${\displaystyle \lfloor \log _{2}x\rfloor }$.^[1] Ця операція тісно пов’язана з count leading zeros (clz) або number of leading zeros (nlz), що підраховує кількість нульових бітів, які передують найбільш значущому одиничному бітові. Ці чотири операції мають також інвертовані версії:

• пошук першого нуля (find first zero — ffz), яка повертає індекс найменш значущого нульового біта;
• підрахунок залишкових одиниць (count trailing ones, яка повертає кількість одиничних біт, які слідують після останнього значимого нульового біта.
• підрахунок початкових одиниць (count leading ones), яка підраховує кількість одиничних біт, що слідують перед найстаршим значимим нульовим бітом;
• Операція, що повертає індекс найбільш значущого нульового біта, що також є версією двійкового логарифма з округленням.

Існує два варіанти нумерації першого входження: нумерація починається або з одиниці, або з нуля. За визначенням POSIX нумерація бітів має починатися з 1^[2], що позначено тут як "ffs", який починає нумерацію бітів з нуля, що еквівалентно "ctz" і буде називатися так само.

Приклади

Маємо наступне 32-бітне слово:

00000000000000001000000000001000

Операція підрахунку залишкових нулів повернула б значення 3, а операція підрахунку початкових нулів поверне 16. Операція підрахунку початкових нулів залежить від довжини слова: якби це 32-бітне слово було скорочено до 16-біт, підрахунок початкових нулів би повернув значення нуль. Операція пошуку першого входження повернула б 4, що відповідало б четвертій позиції 4 з права. Логарифм за основою 2 дорівнює 15.

Апаратна підтримка

Багато архітектур містять інструкції для швидкого пошуку першого значимого входження і/або відповідних операцій. Основною операцією є підрахунок початкових нулів (clz), здебільшого тому, що всі інші операції можна виконати за її допомогою.

Платформа	Скорочення	Назва	Розміри слів	Опис	Результат при нульовому вході
ARM (Архітектура ARMv5T і пізніші)	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
DEC Alpha	cttz[5]	Підрахунок залишкових нульових розрядів	64	ctz	64
Intel 80386 і пізніші	bsf[6]	Пряме сканування біт	16, 32, 64	ctz	Не визначено, встановлює нульовий прапорець
Intel 80386 і пізніші	bsr[6]	Зворотнє сканування біт	16, 32, 64	логарифм за основою 2	Не визначено, встановлює нульовий прапорець
x86 з підтримкою команд маніпуляції бітами[en] ABM	lzcnt[7]	Підрахунок початкових нульових розрядів	16, 32, 64	clz	вхідний розмір, задає прапорець CF (carry flag)
x86 з підтримкою BMI1	tzcnt[8]	Підрахунок залишкових нульових розрядів	16, 32, 64	ctz	вхідний розмір, задає несучий прапорець
Itanium	clz[9]	Підрахунок початкових нульових розрядів	64	clz	64
MIPS	clz[10][11]	Підрахунок початкових нульових розрядів в слові	32, 64	clz	вхідний розмір
MIPS	clo[10][11]	Підрахунок початкових одиниць в слові	32, 64	clo	вхідний розмір
Motorola 68020 і пізніші	bfffo[12]	Пошук першої одиниці в бітовому полі	довільно	логарифм за основою 2	зміщення + ширина
PDP-10	jffo	Перейти, якщо знайдено першу одиницю	36	ctz	Не виконує перехід
POWER/PowerPC/Power Architecture	cntlz/cntlzw/cntlzd[13]	Підрахунок початкових нульових розрядів	32, 64	clz	вхідний розмір
SPARC Oracle Architecture 2011 і пізніші	lzcnt (synonym: lzd) [14]	Підрахунок початкових нульових розрядів	64	clz	64