Find first set

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

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

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

Приклади

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

00000000000000001000000000001000

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

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

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

Платформа	Скорочення	Назва	Розміри слів	Опис	Результат при нульовому вході
ARM (Архітектура ARMv5T і пізніші)	clz	Підрахунок початкових нульових розрядів	32	clz	32
ARM (Архітектура ARMv8-A)	clz	Підрахунок початкових нульових розрядів	32, 64	clz	вхідний розмір
AVR32	clz	Підрахунок початкових нульових розрядів	32	clz	32
DEC Alpha	ctlz	Підрахунок початкових нульових розрядів	64	clz	64
DEC Alpha	cttz	Підрахунок залишкових нульових розрядів	64	ctz	64
Intel 80386 і пізніші	bsf	Пряме сканування біт	16, 32, 64	ctz	Не визначено, встановлює нульовий прапорець
Intel 80386 і пізніші	bsr	Зворотнє сканування біт	16, 32, 64	логарифм за основою 2	Не визначено, встановлює нульовий прапорець
x86 з підтримкою Шаблон:Нп ABM	lzcnt	Підрахунок початкових нульових розрядів	16, 32, 64	clz	вхідний розмір, задає прапорець CF (carry flag)
x86 з підтримкою BMI1	tzcnt	Підрахунок залишкових нульових розрядів	16, 32, 64	ctz	вхідний розмір, задає несучий прапорець
Itanium	clz	Підрахунок початкових нульових розрядів	64	clz	64
MIPS	clz	Підрахунок початкових нульових розрядів в слові	32, 64	clz	вхідний розмір
MIPS	clo	Підрахунок початкових одиниць в слові	32, 64	clo	вхідний розмір
Motorola 68020 і пізніші	bfffo	Пошук першої одиниці в бітовому полі	довільно	логарифм за основою 2	зміщення + ширина
PDP-10	jffo	Перейти, якщо знайдено першу одиницю	36	ctz	Не виконує перехід
POWER/PowerPC/Power Architecture	cntlz/cntlzw/cntlzd	Підрахунок початкових нульових розрядів	32, 64	clz	вхідний розмір
SPARC Oracle Architecture 2011 і пізніші	lzcnt (synonym: lzd)	Підрахунок початкових нульових розрядів	64	clz	64