Find first set

Матеріал з Вікіпедії — вільної енциклопедії.
Версія від 15:13, 23 лютого 2022, створена InternetArchiveBot (обговорення | внесок) (Виправлено джерел: 1; позначено як недійсні: 0.) #IABot (v2.0.8.6)
Перейти до навігації Перейти до пошуку

В програмному забезпеченні, знайди першу одиницю (англ. 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) (англ.).
  2. ↑ FFS(3). Linux Programmer's Manual. The Linux Kernel Archives. Процитовано 2 січня 2012.
  3. ↑ ARM Instruction Reference > ARM general data processing instructions > CLZ. ARM Developer Suite Assembler Guide. ARM. Процитовано 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.
  6. ↑ а б Intel 64 and IA-32 Architectures Software Developer Manual. Volume 2A: Intel. с. 3-92—3-97. 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. Процитовано 2 січня 2014.
  9. ↑ Intel Itanium Architecture Software Developer's Manual. Volume 3: Intel Itanium Instruction Set. Intel. 2010. с. 3:38.
  10. ↑ а б MIPS Architecture For Programmers. Volume II-A: The MIPS32 Instruction Set (вид. Revision 3.02). MIPS Technologies. 2011. с. 101—102.
  11. ↑ а б MIPS Architecture For Programmers. Volume II-A: The MIPS64 Instruction Set (вид. Revision 3.02). MIPS Technologies. 2011. с. 105, 107, 122, 123.
  12. ↑ M68000 Family Programmer's Reference Manual (PDF). Motorola. 1992. с. 4-43—4-45.
  13. ↑ Frey, Brad. PowerPC Architecture Book (вид. Version 2.02). 3.3.11 Fixed-Point Logical Instructions: IBM. с. 70.
  14. ↑ Oracle SPARC Architecture 2011. Oracle.
Отримано з https://uk.wikipedia.org/w/index.php?title=Find_first_set&oldid=34722824