Вікіпедія

Find first set

Немає перевірених версій цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

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

Примітки

ред.
  1. ↑ Anderson, Sean Eron. Find the log base 2 of an integer with the MSB N set in O(N) operations (the obvious way) (англ.). Архів оригіналу за 8 січня 2020. Процитовано 8 грудня 2016.
  2. ↑ FFS(3). Linux Programmer's Manual. The Linux Kernel Archives. Архів оригіналу за 8 серпня 2011. Процитовано 2 січня 2012.
  3. ↑ ARM Instruction Reference > ARM general data processing instructions > CLZ. ARM Developer Suite Assembler Guide. ARM. Архів оригіналу за 20 грудня 2016. Процитовано 3 січня 2012.
  4. ↑ AVR32 Architecture Document (PDF). Atmel. Архів оригіналу (PDF) за 18 березня 2012. Процитовано 22 жовтня 2016.
  5. ↑ а б Alpha Architecture Reference Manual (PDF). Compaq. 2002. с. 4—32, 4—34. Архів оригіналу (PDF) за 3 червня 2016. Процитовано 8 грудня 2016.
  6. ↑ а б Intel 64 and IA-32 Architectures Software Developer Manual. Volume 2A: Intel. с. 3-92—3-97. Архів оригіналу за 26 січня 2012. Процитовано 8 грудня 2016. Order number 325383.
  7. ↑ AMD64 Architecture Programmer's Manual Volume 3: General Purpose and System Instructions3 (PDF). AMD. 2011. с. 204—5.
  8. ↑ AMD64 Architecture Programmer's Manual, Volume 3: General-Purpose and System Instructions (PDF). amd.com. AMD. October 2013. Архів оригіналу (PDF) за 22 грудня 2017. Процитовано 2 січня 2014.
  9. ↑ Intel Itanium Architecture Software Developer's Manual. Volume 3: Intel Itanium Instruction Set. Intel. 2010. с. 3:38. Архів оригіналу за 20 грудня 2016. Процитовано 8 грудня 2016.
  10. ↑ а б MIPS Architecture For Programmers. Volume II-A: The MIPS32 Instruction Set (вид. Revision 3.02). MIPS Technologies. 2011. с. 101—102. Архів оригіналу за 7 листопада 2017. Процитовано 8 грудня 2016. [Архівовано 2017-11-07 у Wayback Machine.]
  11. ↑ а б MIPS Architecture For Programmers. Volume II-A: The MIPS64 Instruction Set (вид. Revision 3.02). MIPS Technologies. 2011. с. 105, 107, 122, 123. Архів оригіналу за 7 листопада 2017. Процитовано 8 грудня 2016. [Архівовано 2017-11-07 у Wayback Machine.]
  12. ↑ M68000 Family Programmer's Reference Manual (PDF). Motorola. 1992. с. 4-43—4-45. Архів оригіналу (PDF) за 24 вересня 2015. Процитовано 8 грудня 2016.
  13. ↑ Frey, Brad. PowerPC Architecture Book (вид. Version 2.02). 3.3.11 Fixed-Point Logical Instructions: IBM. с. 70. Архів оригіналу за 3 листопада 2011. Процитовано 8 грудня 2016.
  14. ↑ Oracle SPARC Architecture 2011. Oracle. Архів оригіналу за 21 грудня 2016. Процитовано 8 грудня 2016.
Отримано з https://uk.wiki.x.io/wiki/Find_first_set