Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

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

Find first set

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-бітне слово:

00000000000000001000000000001000

Операція підрахунку залишкових нулів повернула б значення 3, а операція підрахунку початкових нулів поверне 16. Операція підрахунку початкових нулів залежить від довжини слова: якби це 32-бітне слово було скорочено до 16-біт, підрахунок початкових нулів би повернув значення нуль. Операція пошуку першого входження повернула б 4, що відповідало б четвертій позиції 4 з права. Логарифм за основою 2 дорівнює 15.

Апаратна підтримка

Багато архітектур містять інструкції для швидкого пошуку першого значимого входження і/або відповідних операцій. Основною операцією є підрахунок початкових нулів (clz), здебільшого тому, що всі інші операції можна виконати за її допомогою.

Платформа Скорочення Назва Розміри слів Опис Результат при нульовому вході
ARM () clz Підрахунок початкових нульових розрядів 32 clz 32
ARM () 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 з підтримкою tzcnt Підрахунок залишкових нульових розрядів 16, 32, 64 ctz вхідний розмір, задає несучий прапорець
Itanium clz Підрахунок початкових нульових розрядів 64 clz 64
MIPS clz Підрахунок початкових нульових розрядів в слові 32, 64 clz вхідний розмір
MIPS clo Підрахунок початкових одиниць в слові 32, 64 clo вхідний розмір
і пізніші bfffo Пошук першої одиниці в бітовому полі довільно логарифм за основою 2 зміщення + ширина
PDP-10 jffo Перейти, якщо знайдено першу одиницю 36 ctz Не виконує перехід
/PowerPC/ 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 (PDF). Atmel. Архів оригіналу (PDF) за 18 березня 2012. Процитовано 22 жовтня 2016.
  5. (PDF). Compaq. 2002. с. 4—32, 4—34. Архів оригіналу (PDF) за 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 (PDF). AMD. 2011. с. 204—5.
  8. (PDF). amd.com. AMD. October 2013. Архів оригіналу (PDF) за 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. (PDF). Motorola. 1992. с. 4-43—4-45. Архів оригіналу (PDF) за 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, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

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 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 sho poznacheno tut yak ffs yakij pochinaye numeraciyu bitiv z nulya sho ekvivalentno ctz i bude nazivatisya tak samo PrikladiMayemo nastupne 32 bitne slovo 00000000000000001000000000001000 Operaciya 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 pidtrimkaBagato 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 vhodi ARM clz Pidrahunok pochatkovih nulovih rozryadiv 32 clz 32 ARM clz Pidrahunok pochatkovih nulovih rozryadiv 32 64 clz vhidnij rozmir AVR32 clz Pidrahunok pochatkovih nulovih rozryadiv 32 clz 32 DEC Alpha ctlz Pidrahunok pochatkovih nulovih rozryadiv 64 clz 64 DEC Alpha cttz Pidrahunok zalishkovih nulovih rozryadiv 64 ctz 64 Intel 80386 i piznishi bsf Pryame skanuvannya bit 16 32 64 ctz Ne viznacheno vstanovlyuye nulovij praporec Intel 80386 i piznishi bsr Zvorotnye skanuvannya bit 16 32 64 logarifm za osnovoyu 2 Ne viznacheno vstanovlyuye nulovij praporec x86 z pidtrimkoyu en ABM lzcnt Pidrahunok pochatkovih nulovih rozryadiv 16 32 64 clz vhidnij rozmir zadaye praporec CF carry flag x86 z pidtrimkoyu tzcnt Pidrahunok zalishkovih nulovih rozryadiv 16 32 64 ctz vhidnij rozmir zadaye nesuchij praporec Itanium clz Pidrahunok pochatkovih nulovih rozryadiv 64 clz 64 MIPS clz Pidrahunok pochatkovih nulovih rozryadiv v slovi 32 64 clz vhidnij rozmir MIPS clo Pidrahunok pochatkovih odinic v slovi 32 64 clo vhidnij rozmir i piznishi bfffo Poshuk pershoyi odinici v bitovomu poli dovilno logarifm za osnovoyu 2 zmishennya shirina PDP 10 jffo Perejti yaksho znajdeno pershu odinicyu 36 ctz Ne vikonuye perehid PowerPC cntlz cntlzw cntlzd Pidrahunok pochatkovih nulovih rozryadiv 32 64 clz vhidnij rozmir SPARC Oracle Architecture 2011 i piznishi lzcnt synonym lzd Pidrahunok pochatkovih nulovih rozryadiv 64 clz 64PrimitkiAnderson Sean Eron angl Arhiv originalu za 8 sichnya 2020 Procitovano 8 grudnya 2016 Linux Programmer s Manual The Linux Kernel Archives Arhiv originalu za 8 serpnya 2011 Procitovano 2 sichnya 2012 ARM Developer Suite Assembler Guide ARM Arhiv originalu za 20 grudnya 2016 Procitovano 3 sichnya 2012 AVR32 Architecture Document PDF Atmel Arhiv originalu PDF za 18 bereznya 2012 Procitovano 22 zhovtnya 2016 PDF Compaq 2002 s 4 32 4 34 Arhiv originalu PDF za 3 chervnya 2016 Procitovano 8 grudnya 2016 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 PDF AMD 2011 s 204 5 PDF amd com AMD October 2013 Arhiv originalu PDF za 22 grudnya 2017 Procitovano 2 sichnya 2014 Intel 2010 s 3 38 Arhiv originalu za 20 grudnya 2016 Procitovano 8 grudnya 2016 vid Revision 3 02 MIPS Technologies 2011 s 101 102 Arhiv originalu za 7 listopada 2017 Procitovano 8 grudnya 2016 vid Revision 3 02 MIPS Technologies 2011 s 105 107 122 123 Arhiv originalu za 7 listopada 2017 Procitovano 8 grudnya 2016 PDF Motorola 1992 s 4 43 4 45 Arhiv originalu PDF za 24 veresnya 2015 Procitovano 8 grudnya 2016 Frey Brad 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 Arhiv originalu za 21 grudnya 2016 Procitovano 8 grudnya 2016

Дата публікації:
Топ