www.wikidata.uk-ua.nina.az

Find first set Пошук першої одиниці англ find first set ffs або find first one бітова операція яка визначає індекс номер

Find first set

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

Операція підрахунку залишкових нулів повернула б значення 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 з підтримкою команд маніпуляції бітами[en] 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

Примітки Редагувати

  1. Anderson, Sean Eron. (англ.). Архів оригіналу за 8 січня 2020. Процитовано 8 грудня 2016. 
  2. . Linux Programmer's Manual. The Linux Kernel Archives. Архів оригіналу за 8 серпня 2011. Процитовано 2 січня 2012. 
  3. . ARM Developer Suite Assembler Guide. ARM. Архів оригіналу за 20 грудня 2016. Процитовано 3 січня 2012. 
  4. AVR32 Architecture Document. Atmel. Архів оригіналу за 18 березня 2012. Процитовано 22 жовтня 2016. 
  5. ↑ . Compaq. 2002. с. 4–32, 4–34. Архів оригіналу за 3 червня 2016. Процитовано 8 грудня 2016. 
  6. ↑ . 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. AMD. 2011. с. 204–5. 
  8. (PDF). amd.com. AMD. October 2013. Архів оригіналу за 22 грудня 2017. Процитовано 2 січня 2014. 
  9. . Intel. 2010. с. 3:38. Архів оригіналу за 20 грудня 2016. Процитовано 8 грудня 2016. 
  10. ↑ (вид. Revision 3.02). MIPS Technologies. 2011. с. 101–102. Архів оригіналу за 7 листопада 2017. Процитовано 8 грудня 2016. 
  11. ↑ (вид. Revision 3.02). MIPS Technologies. 2011. с. 105, 107, 122, 123. Архів оригіналу за 7 листопада 2017. Процитовано 8 грудня 2016. 
  12. . Motorola. 1992. с. 4–43–4–45. Архів оригіналу за 24 вересня 2015. Процитовано 8 грудня 2016. 
  13. Frey, Brad. (вид. Version 2.02). 3.3.11 Fixed-Point Logical Instructions: IBM. с. 70. Архів оригіналу за 3 листопада 2011. Процитовано 8 грудня 2016. 
  14. . Oracle. Архів оригіналу за 21 грудня 2016. Процитовано 8 грудня 2016. 
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Poshuk pershoyi odinici angl find first set ffs abo find first one bitova operaciya yaka viznachaye indeks nomer poziciyu najmensh znachushogo bita v mashinnomu slovi bita yakij maye znachennya odinici Majzhe ekvivalentnoyu operaciyeyu ye pidrahunok zalishkovih nuliv angl count trailing zeros ctz abo number of trailing zeros ntz yaka rahuye kilkist nulovih bitiv pislya najmensh znachushogo bita zi znachennyam odin Dualnoyu parnoyu ye operaciya yaka viznachaye indeks chi poziciyu najbilsh znachushogo bita Dlya cilih chisel vona faktichno viznachaye cilu chastinu logarifma za osnovoyu 2 log 2 x displaystyle lfloor log 2 x rfloor 1 Cya operaciya tisno pov yazana z count leading zeros clz abo number of leading zeros nlz sho pidrahovuye kilkist nulovih bitiv yaki pereduyut najbilsh znachushomu odinichnomu bitovi Ci chotiri operaciyi mayut takozh invertovani versiyi poshuk pershogo nulya find first zero ffz yaka povertaye indeks najmensh znachushogo nulovogo bita pidrahunok zalishkovih odinic count trailing ones yaka povertaye kilkist odinichnih bit yaki sliduyut pislya ostannogo znachimogo nulovogo bita pidrahunok pochatkovih odinic count leading ones yaka pidrahovuye kilkist odinichnih bit sho sliduyut pered najstarshim znachimim nulovim bitom Operaciya sho povertaye indeks najbilsh znachushogo nulovogo bita sho takozh ye versiyeyu dvijkovogo logarifma z okruglennyam Isnuye dva varianti numeraciyi pershogo vhodzhennya numeraciya pochinayetsya abo z odinici abo z nulya Za viznachennyam POSIX numeraciya bitiv maye pochinatisya z 1 2 sho poznacheno tut yak ffs yakij pochinaye numeraciyu bitiv z nulya sho ekvivalentno ctz i bude nazivatisya tak samo Prikladi RedaguvatiMayemo nastupne 32 bitne slovo 00000000000000001000000000001000Operaciya pidrahunku zalishkovih nuliv povernula b znachennya 3 a operaciya pidrahunku pochatkovih nuliv poverne 16 Operaciya pidrahunku pochatkovih nuliv zalezhit vid dovzhini slova yakbi ce 32 bitne slovo bulo skorocheno do 16 bit pidrahunok pochatkovih nuliv bi povernuv znachennya nul Operaciya poshuku pershogo vhodzhennya povernula b 4 sho vidpovidalo b chetvertij poziciyi 4 z prava Logarifm za osnovoyu 2 dorivnyuye 15 Aparatna pidtrimka RedaguvatiBagato arhitektur mistyat instrukciyi dlya shvidkogo poshuku pershogo znachimogo vhodzhennya i abo vidpovidnih operacij Osnovnoyu operaciyeyu ye pidrahunok pochatkovih nuliv clz zdebilshogo tomu sho vsi inshi operaciyi mozhna vikonati za yiyi dopomogoyu Platforma Skorochennya Nazva Rozmiri sliv Opis Rezultat pri nulovomu vhodiARM Arhitektura ARMv5T i piznishi clz 3 Pidrahunok pochatkovih nulovih rozryadiv 32 clz 32ARM Arhitektura ARMv8 A clz Pidrahunok pochatkovih nulovih rozryadiv 32 64 clz vhidnij rozmirAVR32 clz 4 Pidrahunok pochatkovih nulovih rozryadiv 32 clz 32DEC Alpha ctlz 5 Pidrahunok pochatkovih nulovih rozryadiv 64 clz 64DEC Alpha cttz 5 Pidrahunok zalishkovih nulovih rozryadiv 64 ctz 64Intel 80386 i piznishi bsf 6 Pryame skanuvannya bit 16 32 64 ctz Ne viznacheno vstanovlyuye nulovij praporecIntel 80386 i piznishi bsr 6 Zvorotnye skanuvannya bit 16 32 64 logarifm za osnovoyu 2 Ne viznacheno vstanovlyuye nulovij praporecx86 z pidtrimkoyu komand manipulyaciyi bitami en ABM lzcnt 7 Pidrahunok pochatkovih nulovih rozryadiv 16 32 64 clz vhidnij rozmir zadaye praporec CF carry flag x86 z pidtrimkoyu BMI1 tzcnt 8 Pidrahunok zalishkovih nulovih rozryadiv 16 32 64 ctz vhidnij rozmir zadaye nesuchij praporecItanium clz 9 Pidrahunok pochatkovih nulovih rozryadiv 64 clz 64MIPS clz 10 11 Pidrahunok pochatkovih nulovih rozryadiv v slovi 32 64 clz vhidnij rozmirMIPS clo 10 11 Pidrahunok pochatkovih odinic v slovi 32 64 clo vhidnij rozmirMotorola 68020 i piznishi bfffo 12 Poshuk pershoyi odinici v bitovomu poli dovilno logarifm za osnovoyu 2 zmishennya shirinaPDP 10 jffo Perejti yaksho znajdeno pershu odinicyu 36 ctz Ne vikonuye perehidPOWER PowerPC Power Architecture cntlz cntlzw cntlzd 13 Pidrahunok pochatkovih nulovih rozryadiv 32 64 clz vhidnij rozmirSPARC Oracle Architecture 2011 i piznishi lzcnt synonym lzd 14 Pidrahunok pochatkovih nulovih rozryadiv 64 clz 64Primitki Redaguvati Anderson Sean Eron Find the log base 2 of an integer with the MSB N set in O N operations the obvious way angl Arhiv originalu za 8 sichnya 2020 Procitovano 8 grudnya 2016 FFS 3 Linux Programmer s Manual The Linux Kernel Archives Arhiv originalu za 8 serpnya 2011 Procitovano 2 sichnya 2012 ARM Instruction Reference gt ARM general data processing instructions gt CLZ ARM Developer Suite Assembler Guide ARM Arhiv originalu za 20 grudnya 2016 Procitovano 3 sichnya 2012 AVR32 Architecture Document Atmel Arhiv originalu za 18 bereznya 2012 Procitovano 22 zhovtnya 2016 a b Alpha Architecture Reference Manual Compaq 2002 s 4 32 4 34 Arhiv originalu za 3 chervnya 2016 Procitovano 8 grudnya 2016 a b Intel 64 and IA 32 Architectures Software Developer Manual Volume 2A Intel s 3 92 3 97 Arhiv originalu za 26 sichnya 2012 Procitovano 8 grudnya 2016 Order number 325383 AMD64 Architecture Programmer s Manual Volume 3 General Purpose and System Instructions3 AMD 2011 s 204 5 AMD64 Architecture Programmer s Manual Volume 3 General Purpose and System Instructions PDF amd com AMD October 2013 Arhiv originalu za 22 grudnya 2017 Procitovano 2 sichnya 2014 Intel Itanium Architecture Software Developer s Manual Volume 3 Intel Itanium Instruction Set Intel 2010 s 3 38 Arhiv originalu za 20 grudnya 2016 Procitovano 8 grudnya 2016 a b MIPS Architecture For Programmers Volume II A The MIPS32 Instruction Set vid Revision 3 02 MIPS Technologies 2011 s 101 102 Arhiv originalu za 7 listopada 2017 Procitovano 8 grudnya 2016 a b MIPS Architecture For Programmers Volume II A The MIPS64 Instruction Set vid Revision 3 02 MIPS Technologies 2011 s 105 107 122 123 Arhiv originalu za 7 listopada 2017 Procitovano 8 grudnya 2016 M68000 Family Programmer s Reference Manual Motorola 1992 s 4 43 4 45 Arhiv originalu za 24 veresnya 2015 Procitovano 8 grudnya 2016 Frey Brad PowerPC Architecture Book vid Version 2 02 3 3 11 Fixed Point Logical Instructions IBM s 70 Arhiv originalu za 3 listopada 2011 Procitovano 8 grudnya 2016 Oracle SPARC Architecture 2011 Oracle Arhiv originalu za 21 grudnya 2016 Procitovano 8 grudnya 2016 Otrimano z https uk wikipedia org w index php title Find first set amp oldid 40326826