Find first set: відмінності між версіями

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Наступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
Inna Z (обговорення | внесок)
8038 редагувань
Створена сторінка: В програмному забезпеченні, '''знайди першу одиницю''' (англ. '''...
(Немає відмінностей)

Версія за 16:21, 8 грудня 2016

В програмному забезпеченні, знайди першу одиницю (англ. 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), which counts the number of zero bits preceding the most significant one bit. Ці чотири операції мають також інвертовані версії:

  • пошук першого нуля (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 з підтримкою ABM lzcnt[7] Підрахунок початкових нульових розрядів 16, 32, 64 clz вхідний розмір, задає несучий флаг
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, 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 January 2012.
  3. ↑ ARM Instruction Reference > ARM general data processing instructions > CLZ. ARM Developer Suite Assembler Guide. ARM. Процитовано 3 January 2012.
  4. ↑ AVR32 Architecture Document (PDF). Atmel. Процитовано 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=19304373