Пошук першої одиниці (, ffs або find first one) — бітова операція, яка визначає індекс (номер, позицію) найменш значущого біта в машинному слові (біта, який має значення одиниці). Майже еквівалентною операцією є підрахунок залишкових нулів (, ctz або number of trailing zeros, ntz), яка рахує кількість нульових бітів після найменш значущого (біта зі значенням один). Дуальною (парною) є операція, яка визначає індекс чи позицію найбільш значущого біта. Для цілих чисел вона фактично визначає цілу частину логарифма за основою 2 . Ця операція тісно пов’язана з 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 Order number 325383. Пряме сканування біт 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
Примітки