फाइंड फर्स्ट सेट: Difference between revisions

From Vigyanwiki
(Created page with "{{Use dmy dates|date=January 2020|cs1-dates=y}} कंप्यूटर सॉफ़्टवेयर और हार्डवेयर में, पहला से...")
 
No edit summary
Tag: Manual revert
 
(12 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Use dmy dates|date=January 2020|cs1-dates=y}}
कंप्यूटर [[सॉफ़्टवेयर]] और हार्डवेयर में, '''फर्स्ट सेट (एफएफएस) फाइंड''' [[बिट ऑपरेशन|बिट संचालन]] है, जिसे मशीन शब्द [[ शब्द (कंप्यूटर वास्तुकला) |(कंप्यूटर आर्किटेक्चर)]]<ref group="nb" name="NB1"/> दिया गया है, इस प्रकार कम से कम महत्वपूर्ण बिट स्थिति से शब्द गणना में पर सेट किए गए कम से कम महत्वपूर्ण बिट के सूचकांक या स्थिति को निर्दिष्ट करता है। इस प्रकार लगभग समतुल्य संचालन अनुगामी शून्यों (ctz) या अनुगामी शून्यों की संख्या (ntz) की गणना है, जो कम से कम महत्वपूर्ण बिट के बाद शून्य बिट्स की संख्या की गणना करता है। इस प्रकार पूरक संचालन जो सबसे महत्वपूर्ण सेट बिट के सूचकांक या स्थिति का पता लगाता है, लॉग बेस 2 है, इसलिए इसे इसलिए कहा जाता है क्योंकि यह [[द्विआधारी लघुगणक]] {{math|⌊log{{sub|2}}(x)⌋}} की गणना करता है .<ref name="Anderson_1"/> यह अग्रणी शून्य (सीएलजेड) या अग्रणी शून्य की संख्या (एनएलजेड) की गणना करने के लिए गुण और संबंध है, जो सबसे महत्वपूर्ण बिट से पहले शून्य बिट्स की संख्या की गणना करता है। पहले सेट को खोजने के दो सामान्य प्रकार हैं, [[POSIX|पॉज़िक्स]] परिभाषा जो 1 पर बिट्स का अनुक्रमण प्रारंभ करती है,<ref name="Linux_2012_FFS3"/> यहां एफएफएस लेबल किया गया है, और वह वेरिएंट जो शून्य पर बिट्स का अनुक्रमण प्रारंभ करता है, जो सीटीजेड के सामान्य है और इसलिए उसे उस नाम से बुलाया जाता है।<ref group="nb" name="NB2"/>
कंप्यूटर [[सॉफ़्टवेयर]] और हार्डवेयर में, पहला सेट (FFS) ढूंढें या पहला सेट ढूंढें एक [[बिट ऑपरेशन]] है, जिसे एक अहस्ताक्षरित [[ शब्द (कंप्यूटर वास्तुकला) ]] दिया गया है,<ref group="nb" name="NB1"/>कम से कम महत्वपूर्ण बिट स्थिति से शब्द गणना में एक पर सेट किए गए कम से कम महत्वपूर्ण बिट के सूचकांक या स्थिति को निर्दिष्ट करता है। लगभग समतुल्य ऑपरेशन अनुगामी शून्यों (ctz) या अनुगामी शून्यों की संख्या (ntz) की गणना है, जो कम से कम महत्वपूर्ण एक बिट के बाद शून्य बिट्स की संख्या की गणना करता है। पूरक ऑपरेशन जो सबसे महत्वपूर्ण सेट बिट के सूचकांक या स्थिति का पता लगाता है, लॉग बेस 2 है, इसलिए इसे इसलिए कहा जाता है क्योंकि यह [[द्विआधारी लघुगणक]] की गणना करता है {{math|⌊log{{sub|2}}(x)⌋}}.<ref name="Anderson_1"/>यह अग्रणी शून्य (सीएलजेड) या अग्रणी शून्य की संख्या (एनएलजेड) की गणना करने के लिए #गुण और संबंध है, जो सबसे महत्वपूर्ण एक बिट से पहले शून्य बिट्स की संख्या की गणना करता है।<ref group="nb" name="NB2"/>पहले सेट को खोजने के दो सामान्य प्रकार हैं, [[POSIX]] परिभाषा जो 1 पर बिट्स का अनुक्रमण शुरू करती है,<ref name="Linux_2012_FFS3"/>यहां एफएफएस लेबल किया गया है, और वह वेरिएंट जो शून्य पर बिट्स का अनुक्रमण शुरू करता है, जो सीटीजेड के बराबर है और इसलिए उसे उस नाम से बुलाया जाएगा।


अधिकांश आधुनिक सीपीयू [[ अनुदेश सेट वास्तुकला ]] इनमें से एक या अधिक को हार्डवेयर ऑपरेटर के रूप में प्रदान करते हैं; सॉफ़्टवेयर अनुकरण आम तौर पर उन सभी के लिए प्रदान किया जाता है जो उपलब्ध नहीं हैं, या तो कंपाइलर इंट्रिनिक्स के रूप में या सिस्टम लाइब्रेरीज़ में।
अधिकांश आधुनिक सीपीयू [[ अनुदेश सेट वास्तुकला |अनुदेश सेट आर्किटेक्चर]] इनमें से या अधिक को हार्डवेयर ऑपरेटर के रूप में प्रदान करते हैं; इस प्रकार सॉफ़्टवेयर अनुकरण सामान्यतः उन सभी के लिए प्रदान किया जाता है जो उपलब्ध नहीं हैं, या तो कंपाइलर इंट्रिनिक्स के रूप में या सिस्टम लाइब्रेरीज़ में उपयोग किया जाता है।


== उदाहरण ==
== उदाहरण ==
Line 9: Line 8:
: 0000 0000 0000 0000 1000 0000 0000 1000
: 0000 0000 0000 0000 1000 0000 0000 1000


गिनती के पीछे शून्य ऑपरेशन 3 लौटाएगा, जबकि गिनती अग्रणी शून्य ऑपरेशन 16 लौटाएगा। गिनती अग्रणी शून्य ऑपरेशन शब्द आकार पर निर्भर करता है: यदि इस 32-बिट शब्द को 16-बिट शब्द में छोटा कर दिया गया था, तो गिनती अग्रणी शून्य शून्य वापस आएगा . पहला सेट ढूंढें ऑपरेशन 4 लौटाएगा, जो दाईं ओर से चौथी स्थिति को दर्शाता है। लॉग बेस 2 15 है।
गणना के पीछे शून्य संचालन 3 वापस करता है, जबकि गणना अग्रणी शून्य संचालन 16 वापस करता है। इस प्रकार गणना अग्रणी शून्य संचालन शब्द आकार पर निर्भर करता है: यदि इस 32-बिट शब्द को 16-बिट शब्द में छोटा कर दिया गया था, तो गणना अग्रणी शून्य शून्य वापस आएगा फर्स्ट सेट फाइंड संचालन 4 वापस करता है, जो दाईं ओर से चौथी स्थिति को दर्शाता है। लॉग बेस 2 15 है।


इसी प्रकार, निम्नलिखित 32-बिट शब्द को देखते हुए, उपरोक्त शब्द का बिटवाइज़ निषेध:
इसी प्रकार, निम्नलिखित 32-बिट शब्द को देखते हुए, उपरोक्त शब्द का बिटवाइज़ निषेध है:


: 1111 1111 1111 1111 0111 1111 1111 0111
: 1111 1111 1111 1111 0111 1111 1111 0111


काउंट ट्रेलिंग वन्स ऑपरेशन 3 लौटाएगा, काउंट लीडिंग वन्स ऑपरेशन 16 लौटाएगा, और फाइंड फर्स्ट जीरो ऑपरेशन ffz 4 लौटाएगा।
काउंट ट्रेलिंग वन्स संचालन 3 वापस करता है, काउंट लीडिंग वन्स संचालन 16 वापस करता है, और फाइंड फर्स्ट जीरो संचालन ffz 4 वापस करता है।


यदि शब्द शून्य है (कोई बिट्स सेट नहीं है), तो अग्रणी शून्यों की गिनती करें और पिछले शून्यों की गिनती करें, दोनों शब्द में बिट्स की संख्या लौटाते हैं, जबकि एफएफएस शून्य लौटाता है। लॉग बेस 2 और फाइंड फर्स्ट सेट के शून्य-आधारित कार्यान्वयन दोनों आम तौर पर शून्य शब्द के लिए एक अपरिभाषित परिणाम लौटाते हैं।
यदि शब्द शून्य है (कोई बिट्स सेट नहीं है), तो अग्रणी शून्यों की गणना करें और पिछले शून्यों की गणना करें, दोनों शब्द में बिट्स की संख्या वापस करते हैं, जबकि एफएफएस शून्य वापस करते है। लॉग बेस 2 और फाइंड फर्स्ट सेट के शून्य-आधारित कार्यान्वयन दोनों सामान्यतः शून्य शब्द के लिए अपरिभाषित परिणाम वापस करते हैं।


== हार्डवेयर समर्थन ==
== हार्डवेयर समर्थन ==
कई आर्किटेक्चर में नीचे सूचीबद्ध पहले सेट और/या संबंधित संचालन को तेजी से निष्पादित करने के लिए निर्देश सेट शामिल हैं। सबसे आम ऑपरेशन गिनती अग्रणी शून्य (सीएलजेड) है, संभवतः क्योंकि अन्य सभी ऑपरेशन इसके संदर्भ में कुशलतापूर्वक कार्यान्वित किए जा सकते हैं (#गुण और संबंध देखें)।
कई आर्किटेक्चर में नीचे सूचीबद्ध पहले सेट और/या संबंधित संचालन को तेजी से निष्पादित करने के लिए निर्देश सेट सम्मिलित हैं। सबसे सामान्य संचालन गणना अग्रणी शून्य (सीएलजेड) है, संभवतः क्योंकि अन्य सभी संचालन इसके संदर्भ में कुशलतापूर्वक कार्यान्वित किए जा सकते हैं (गुण और संबंध देखें)।


{|class="wikitable"
{|class="wikitable"
! Platform !! Mnemonic !! Name !! Operand widths !! Description !! On application to 0
! प्लैटफ़ॉर्म !! मनेमोनिक !! नाम !! ऑपरेंड की चौड़ाई !! विवरण !! 0 के लिए आवेदन पर
|-
|-
| [[ARM architecture|ARM]] ([[List of ARM microarchitectures|ARMv5T architecture and later]])<br />except [[ARM Cortex-M|Cortex-M0/M0+/M1/M23]] || clz<ref name="ARM_2012_CLZ"/> || Count Leading Zeros || 32 || clz || 32
| एआरएम (ARMv5T आर्किटेक्चर और बाद में)
कॉर्टेक्स-M0/M0+/M1/M23 को छोड़कर
| clz<ref name="ARM_2012_CLZ"/> || अग्रणी शून्यों की गणना करें || 32 || clz || 32
|-
|-
| [[ARM architecture|ARM]] ([[List of ARM microarchitectures|ARMv8-A architecture]]) || clz || Count Leading Zeros || 32, 64 || clz || Operand width
| एआरएम (एआरएमवी8-ए आर्किटेक्चर) || clz || अग्रणी शून्यों की गणना करें || 32, 64 || clz || ऑपरेंड की चौड़ाई
|-
|-
| [[AVR32]] || clz<ref name="Atmel_AVR32"/> || Count Leading Zeros || 32 || clz || 32
| [[AVR32|एवीआर32]] || clz<ref name="Atmel_AVR32"/> || अग्रणी शून्यों की गणना करें || 32 || clz || 32
|-
|-
| rowspan=2 | [[DEC Alpha]]
| rowspan=2 | [[DEC Alpha|डीईसी अल्फा]]
| ctlz<ref name="Compaq_2002_Alpha"/> || Count Leading Zeros || 64 || clz || 64
| सीटीएलजेड<ref name="Compaq_2002_Alpha"/> || अग्रणी शून्यों की गणना करें || 64 || clz || 64
|-
|-
| cttz<ref name="Compaq_2002_Alpha"/> || Count Trailing Zeros || 64 || ctz || 64
| सीटीटीजेड<ref name="Compaq_2002_Alpha"/> || अनुगामी शून्यों की गणना करें || 64 || ctz || 64
|-
|-
| rowspan=2 | [[Intel 80386]] and later
| rowspan=2 | इंटेल 80386 और बाद का संस्करण
| bsf<ref name="Intel_64-32_DM-2A"/> || Bit Scan Forward || 16, 32, 64 || ctz || Undefined; sets zero flag
| bsf<ref name="Intel_64-32_DM-2A"/> || बिट स्कैन फॉरवर्ड || 16, 32, 64 || ctz || अपरिभाषित; जीरो फ्लैग सेट करता है
|-
|-
| bsr<ref name="Intel_64-32_DM-2A"/> || Bit Scan Reverse || 16, 32, 64 || Log base 2 || Undefined; sets zero flag
| bsr<ref name="Intel_64-32_DM-2A"/> || बिट स्कैन रिवर्स || 16, 32, 64 || Log base 2 || अपरिभाषित; जीरो फ्लैग सेट करता है
|-
|-
| [[x86]] supporting [[Bit Manipulation Instruction Sets#BMI1|BMI1]] or [[Bit Manipulation Instruction Sets#ABM|ABM]] || lzcnt<ref name="AMD_2011_AMD64"/> || Count Leading Zeros || 16, 32, 64 || clz || Operand width; sets carry flag
| x86 बीएमआई1 या एबीएम का समर्थन करता है || एलज़सीएनटी<ref name="AMD_2011_AMD64"/> || अग्रणी शून्यों की गणना करें || 16, 32, 64 || clz || ऑपरेंड की चौड़ाई; सेट फ्लैग लेकर चलते हैं
|-
|-
| [[x86]] supporting [[Bit Manipulation Instruction Sets#BMI1|BMI1]] || tzcnt<ref name="AMD_2013_AMD64"/> || Count Trailing Zeros || 16, 32, 64 || ctz || Operand width; sets carry flag
| x86 बीएमआई1 का समर्थन करता है || tzcnt<ref name="AMD_2013_AMD64"/> || अनुगामी शून्यों की गणना करें || 16, 32, 64 || ctz || ऑपरेंड की चौड़ाई; सेट फ्लैग लेकर चलते हैं
|-
|-
| [[Itanium]] || clz<ref name="Intel_Itanium_DM-3"/> || Count Leading Zeros || 64 || clz || 64
| [[Itanium|इटेनियम]] || clz<ref name="Intel_Itanium_DM-3"/> || अग्रणी शून्यों की गणना करें || 64 || clz || 64
|-
|-
| rowspan=2 | [[MIPS architecture#MIPS32/MIPS64|MIPS32/MIPS64]]
| rowspan=2 | [[MIPS architecture#MIPS32/MIPS64|एमआईपीएस32/एमआईपीएस64]]
| clz<ref name="MIPS_2011_32"/><ref name="MIPS_2011_64"/> || Count Leading Zeros in Word || 32, 64 || clz || Operand width
| clz<ref name="MIPS_2011_32"/><ref name="MIPS_2011_64"/> || वर्ड में प्रमुख शून्यों की गणना करें || 32, 64 || clz || ऑपरेंड की चौड़ाई
|-
|-
| clo<ref name="MIPS_2011_32"/><ref name="MIPS_2011_64"/> || Count Leading Ones in Word || 32, 64 || clo || Operand width
| clo<ref name="MIPS_2011_32"/><ref name="MIPS_2011_64"/> || वर्ड में अग्रणी लोगों की गिनती करें || 32, 64 || clo || ऑपरेंड की चौड़ाई
|-
|-
| [[Motorola 68020]] and later || bfffo<ref name="Motorola_1992"/> || Find First One in Bit Field || Arbitrary || Log base 2 || Field offset + field width
| मोटोरोला 68020 और बाद में || bfffo<ref name="Motorola_1992"/> || बिट फ़ील्ड में फर्स्ट फाइंड || Arbitrary || Log base 2 || फ़ेसट का फ़ील्ड + फ़ील्ड की चौड़ाई
|-
|-
| [[PDP-10]] || jffo || Jump if Find First One  || 36 || ctz || 0; no operation
| [[PDP-10|पीडीपी-10]] || jffo || यदि पहले वाला मिल जाए || 36 || ctz || 0; कोई संचालन नहीं
|-
|-
| [[IBM POWER Instruction Set Architecture|POWER]]/[[PowerPC]]/[[Power ISA]] || cntlz/cntlzw/cntlzd<ref name="Frey_PowerPC"/> || Count Leading Zeros || 32, 64 || clz || Operand width
| पावर/पावरपीसी/पावर आईएसए || cntlz/cntlzw/cntlzd<ref name="Frey_PowerPC"/> || अग्रणी शून्यों की गणना करें || 32, 64 || clz || ऑपरेंड की चौड़ाई
|-
|-
| [[Power ISA#Power ISA v.3.0|Power ISA 3.0 and later]] || cnttzw/cnttzd<ref name="IBM_PowerISA"/> || Count Trailing Zeros || 32, 64 || ctz || Operand width
| [[Power ISA#Power ISA v.3.0|पावर आईएसए 3.0 और बाद का संस्करण]] || cnttzw/cnttzd<ref name="IBM_PowerISA"/> || अनुगामी शून्यों की गणना करें || 32, 64 || ctz || ऑपरेंड की चौड़ाई
|-
|-
| rowspan=2 | [[RISC-V]] ("B" Extension) (draft)
| rowspan=2 | आरआईएससी-वी ("बी" एक्सटेंशन) (ड्राफ्ट)
| clz<ref name="Wolf_2019_RISC-V-B"/> || Count Leading Zeros || 32, 64 || clz || Operand width
| clz<ref name="Wolf_2019_RISC-V-B"/> || अग्रणी शून्यों की गणना करें || 32, 64 || clz || ऑपरेंड की चौड़ाई
|-
|-
| ctz<ref name="Wolf_2019_RISC-V-B"/> || Count Trailing Zeros || 32, 64 || ctz || Operand width
| ctz<ref name="Wolf_2019_RISC-V-B"/> || अनुगामी शून्यों की गणना करें || 32, 64 || ctz || ऑपरेंड की चौड़ाई
|-
|-
| [[SPARC|SPARC Oracle Architecture 2011 and later]] || lzcnt (synonym: lzd)<ref name="Oracle_2011_SPARC"/> || Leading Zero Count || 64 || clz || 64
| [[SPARC|स्पार्क ओरेकल आर्किटेक्चर 2011 और बाद में]] || एलज़सीएनटी (synonym: lzd)<ref name="Oracle_2011_SPARC"/> || अग्रणी शून्य गणना || 64 || clz || 64
|-
|-
| [[VAX]] || ffs<ref name="DEC_1987_VAX"/> || Find First Set || 0–32 || ctz || Operand width; sets zero flag
| [[VAX|वैक्स]] || एफएफएस<ref name="DEC_1987_VAX"/> || फर्स्ट सेट फाइंड || 0–32 || ctz || ऑपरेंड की चौड़ाई; शून्य फ्लैग सेट करता है
|-
|-
| rowspan=3 | [[z/Architecture|IBM z/Architecture]]
| rowspan=3 | [[z/Architecture|आईबीएम जेड/आर्किटेक्चर]]
| flogr<ref name="IBM_Z_C22"/> || Find Leftmost One || 64 || clz || 64
| flogr<ref name="IBM_Z_C22"/> || सबसे बाईं ओर वाला फाइंड || 64 || clz || 64
|-
|-
| vclz<ref name="IBM_Z_C22"/> || Vector Count Leading Zeroes || 8, 16, 32, 64 || clz || Operand width
| vclz<ref name="IBM_Z_C22"/> || सदिश गणना अग्रणी शून्य || 8, 16, 32, 64 || clz || ऑपरेंड की चौड़ाई
|-
|-
| vctz<ref name="IBM_Z_C22"/> || Vector Count Trailing Zeroes || 8, 16, 32, 64 || ctz || Operand width
| vctz<ref name="IBM_Z_C22"/> || सदिश गणना अनुगामी शून्य || 8, 16, 32, 64 || ctz || ऑपरेंड की चौड़ाई
|}
|}
कुछ अल्फ़ा प्लेटफ़ॉर्म पर CTLZ और CTTZ का सॉफ़्टवेयर में अनुकरण किया जाता है।
कुछ अल्फ़ा प्लेटफ़ॉर्म पर सीटीएलजेड और सीटीटीजेड का सॉफ़्टवेयर में अनुकरण किया जाता है।


==उपकरण और पुस्तकालय समर्थन==
==उपकरण और लाइब्रेरी समर्थन==
कई कंपाइलर और लाइब्रेरी विक्रेता पहले सेट और/या संबंधित संचालन को खोजने के लिए कंपाइलर इंट्रिनिक्स या लाइब्रेरी फ़ंक्शंस की आपूर्ति करते हैं, जिन्हें अक्सर उपरोक्त हार्डवेयर निर्देशों के संदर्भ में कार्यान्वित किया जाता है:
कई कंपाइलर और लाइब्रेरी विक्रेता पहले सेट और/या संबंधित संचालन को खोजने के लिए कंपाइलर इंट्रिनिक्स या लाइब्रेरी फ़ंक्शंस की आपूर्ति करते हैं, जिन्हें अधिकांशतः उपरोक्त हार्डवेयर निर्देशों के संदर्भ में कार्यान्वित किया जाता है:


{|class="wikitable"
{|class="wikitable"
!Tool/library!!Name!!Type!!Input type(s)!!Notes!!On application to 0
!उपकरण/लाइब्रेरी!!नाम!!प्रकार!!इनपुट प्रकार!!टिप्पणियाँ!!0 के लिए आवेदन पर
|-
|-
|[[POSIX]].1 compliant libc<br />[[4.3BSD]] libc<br />OS X 10.3 libc<ref name="Linux_2012_FFS3" /><ref name="Apple_1994_FFS3" />||<code>ffs</code>||Library function||int||Includes [[glibc]]. POSIX does not supply the complementary log base 2 / clz.||0
|[[POSIX|पॉज़िक्स]].1 अनुपालक libc
4.3बीएसडी libc
 
ओएस एक्स 10.3 libc<ref name="Linux_2012_FFS3" /><ref name="Apple_1994_FFS3" />
|<code>एफएफएस</code>||लाइब्रेरी फंक्शन||आईएनटी||ग्लिबैक सम्मिलित है। पॉज़िक्स पूरक लॉग बेस 2/सीएलज़ की आपूर्ति नहीं करता है।||0
|-
|-
|[[FreeBSD]] 5.3 libc<br />OS X 10.4 libc<ref name="Apple_1994_FFS3" />||<code>ffsl</code><br /><code>fls</code><br /><code>flsl</code>||Library function||int,<br />long||fls("find last set") computes (log base 2) + 1.||0
|फ्रीबीएसडी 5.3 libc
ओएस एक्स 10.4 libc<ref name="Apple_1994_FFS3" />
|<code>एफएफएसl</code><br /><code>fls</code><br /><code>flsl</code>||लाइब्रेरी फंक्शन||पूर्णांक,
लंबा
|एफएलएस ("अंतिम सेट खोजे") गणना करता है (लॉग बेस 2) + 1।||0
|-
|-
|[[FreeBSD]] 7.1 libc<ref name="FreeBSD_2012_FFS3" />||<code>ffsll</code><br /><code>flsll</code>||Library function||long long|| ||0
|फ्रीबीएसडी 7.1 libc<ref name="FreeBSD_2012_FFS3" />||<code>एफएफएसll</code><br /><code>flsll</code>||लाइब्रेरी फंक्शन||लॉन्ग लॉन्ग|| ||0
|-
|-
|[[GNU Compiler Collection|GCC]] 3.4.0<ref name="GCC_2015_Functions" /><ref name="GCC_2015_Changes" /><br />[[Clang]] 5.x<ref name="LLVM_Clang_Extensions" /><ref name="LLVM_Clang_Sources" />||<code>__builtin_ffs[l,ll,imax]</code><br /><code>__builtin_clz[l,ll,imax]</code><br /><code>__builtin_ctz[l,ll,imax]</code><br />||Built-in functions||unsigned int,<br />unsigned long,<br />unsigned long long,<br />uintmax_t||GCC documentation considers result undefined clz and ctz on 0.||0 (ffs)
|[[GNU Compiler Collection|जीसीसी]] 3.4.0<ref name="GCC_2015_Functions" /><ref name="GCC_2015_Changes" /><br />[[Clang|क्लैंग]] 5.x<ref name="LLVM_Clang_Extensions" /><ref name="LLVM_Clang_Sources" />||<code>__builtin_एफएफएस[l,ll,imax]</code><br /><code>__builtin_clz[l,ll,imax]</code><br /><code>__builtin_ctz[l,ll,imax]</code><br />||अंतर्निहित कार्य||अहस्ताक्षरित पूर्णांक,
अहस्ताक्षरित लंबा,
 
अहस्ताक्षरित लॉन्ग लॉन्ग,
 
यूइंटमैक्स_टी
|जीसीसी दस्तावेज़ीकरण परिणाम को अपरिभाषित clz और 0 पर ctz मानता है।||0 (एफएफएस)
|-
|-
|[[Visual Studio]] 2005||<code>_BitScanForward</code><ref name="Microsoft_2008_Intrinsics_1" /><br /><code>_BitScanReverse</code><ref name="Microsoft_2008_Intrinsics_2" />||Compiler intrinsics||unsigned long,<br />unsigned __int64||Separate return value to indicate zero input||Undefined
|[[Visual Studio|विजुअल स्टूडियो]] 2005||<code>_BitScanForward</code><ref name="Microsoft_2008_Intrinsics_1" /><br /><code>_BitScanReverse</code><ref name="Microsoft_2008_Intrinsics_2" />||संकलक आंतरिक||अहस्ताक्षरित लंबा,
अहस्ताक्षरित __int64
|शून्य इनपुट इंगित करने के लिए अलग रिटर्न मान||अपरिभाषित
|-
|-
|[[Visual Studio]] 2008||<code>__lzcnt</code><ref name="Microsoft_2008_Intrinsics_3" />||Compiler intrinsic||unsigned short,<br />unsigned int,<br />unsigned __int64||Relies on hardware support for the lzcnt instruction introduced in [[Bit Manipulation Instruction Sets#BMI1|BMI1]] or [[Bit Manipulation Instruction Sets#ABM|ABM]].||Operand width
|[[Visual Studio|विजुअल स्टूडियो]] 2008||<code>__एलज़सीएनटी</code><ref name="Microsoft_2008_Intrinsics_3" />||कंपाइलर आंतरिक||अहस्ताक्षरित लघु,
अहस्ताक्षरित पूर्णांक,
 
अहस्ताक्षरित __int64
|बीएमआई1 या एबीएम में प्रस्तुत एलज़सीएनटी अनुदेश के लिए हार्डवेयर समर्थन पर निर्भर करता है।||ऑपरेंड की चौड़ाई
|-
|-
|[[Visual Studio]] 2012||<code>_arm_clz</code><ref name="Microsoft_2012_Intrinsics_1" />||Compiler intrinsic||unsigned int||Relies on hardware support for the clz instruction introduced in the [[List of ARM microarchitectures|ARMv5T architecture and later]].||?
|[[Visual Studio|विजुअल स्टूडियो]] 2012||<code>_arm_clz</code><ref name="Microsoft_2012_Intrinsics_1" />||कंपाइलर आंतरिक||अहस्ताक्षरित पूर्णांक||ARMv5T आर्किटेक्चर और बाद में पेश किए गए clz निर्देश के लिए हार्डवेयर समर्थन पर निर्भर करता है।||?
|-
|-
|[[Intel C++ Compiler]]||<code>_bit_scan_forward</code><br /><code>_bit_scan_reverse</code><ref name="Intel_Intrinsics_Guide" /><ref name="Intel_2006_Intrinsics" />||Compiler intrinsics||int|| ||Undefined
|[[Intel C++ Compiler|इंटेल सी++ कंपाइलर]]||<code>_bit_scan_forward</code><br /><code>_bit_scan_reverse</code><ref name="Intel_Intrinsics_Guide" /><ref name="Intel_2006_Intrinsics" />||संकलक आंतरिक||पूर्णांक|| ||अपरिभाषित
|-
|-
|rowspan=2|NVIDIA [[CUDA]]<ref name="NVIDIA_2010_CUDA" />||<code>__clz</code>||rowspan=2|Functions||rowspan=2|32-bit, 64-bit||rowspan=2|Compiles to fewer instructions on the [[GeForce 400 Series]]||32
|rowspan=2|एनवीडिया क्यूडा<ref name="NVIDIA_2010_CUDA" />||<code>__clz</code>||rowspan=2|फ़ंक्शंस|| rowspan="2" |32-बिट, 64-बिट|| rowspan="2" |GeForce 400 सीरीज पर कम निर्देशों को संकलित करता है||32
|-
|-
|<code>__ffs</code>||0
|<code>__एफएफएस</code>||0
|-
|-
|[[LLVM]]||<code>llvm.ctlz.*</code><br /><code>llvm.cttz.*</code><ref name="LLVM_Intrinsic" />||Intrinsic||8, 16, 32, 64, 256||LLVM assembly language||Operand width, if 2nd argument is 0; undefined otherwise
|[[LLVM|एलएलवीएम]]||<code>एलएलवीएम.सीटीएलजेड.*</code><br /><code>एलएलवीएम.सीटीटीजेड.*</code><ref name="LLVM_Intrinsic" />||आंतरिक||8, 16, 32, 64, 256||एलएलवीएम असेंबली भाषा||ऑपरेंड की चौड़ाई, यदि दूसरा तर्क 0 है; अन्यथा अपरिभाषित
|-
|-
|[[Glasgow Haskell Compiler|GHC]] 7.10 (base 4.8), in <code>Data.Bits</code>{{citation needed|date=May 2020}}||<code>countLeadingZeros</code><br /><code>countTrailingZeros</code>||Library function||<code>FiniteBits b => b</code>||Haskell programming language||Operand width
|जीएचसी 7.10 (बेस 4.8), <code>Data.Bits</code>||<code>countLeadingZeros</code><br /><code>countTrailingZeros</code>||लाइब्रेरी फंक्शन||<code>FiniteBits b => b</code>||हास्केल प्रोग्रामिंग भाषा||ऑपरेंड की चौड़ाई
|-
|-
|[[C++20]] standard library, in header <code><bit></code><ref>{{cite book |last1=Smith |first1=Richard |title=N4861 Working Draft, Standard for Programming Language C++ |date=2020-04-01 |publisher=ISO/IEC |pages=1150–1153 |url=http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4861.pdf |access-date=25 May 2020}}</ref><ref name="cppreference_header_bit">{{cite web |title=Standard library header <bit> |url=https://en.cppreference.com/w/cpp/header/bit |website=cppreference.com |access-date=25 May 2020}}</ref>||<code>bit_ceil bit_floor</code><br/><code>bit_width</code><br /><code>countl_zero countl_one</code><br /><code>countr_zero countr_one</code>||Library function||unsigned char,<br />unsigned short,<br />unsigned int,<br />unsigned long,<br />unsigned long long|| ||
|[[C++20]] मानक लाइब्रेरी, हेडर में <code><bit></code><ref>{{cite book |last1=Smith |first1=Richard |title=N4861 Working Draft, Standard for Programming Language C++ |date=2020-04-01 |publisher=ISO/IEC |pages=1150–1153 |url=http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4861.pdf |access-date=25 May 2020}}</ref><ref name="cppreference_header_bit">{{cite web |title=Standard library header <bit> |url=https://en.cppreference.com/w/cpp/header/bit |website=cppreference.com |access-date=25 May 2020}}</ref>||<code>bit_ceil bit_floor</code><br/><code>bit_width</code><br /><code>countl_zero countl_one</code><br /><code>countr_zero countr_one</code>||लाइब्रेरी फंक्शन||अचिन्हित वर्ण,
|}
अहस्ताक्षरित लघु,


अहस्ताक्षरित पूर्णांक,


== गुण और संबंध ==
अहस्ताक्षरित लंबा,
यदि बिट्स को 1 से शुरू करके लेबल किया गया है (जो कि इस आलेख में प्रयुक्त परंपरा है), तो अनुगामी शून्यों की गणना करें और पता लगाएं कि पहले सेट ऑपरेशन किससे संबंधित हैं {{math|1=ctz(''x'') = ffs(''x'') − 1}} (सिवाय जब इनपुट शून्य हो)। यदि बिट्स को प्रारंभ से लेबल किया गया है {{math|0}}, फिर पिछले शून्यों की गिनती करें और पता लगाएं कि पहला सेट बिल्कुल समतुल्य संचालन है। दिया गया {{math|''w''}} प्रति शब्द बिट्स, {{math|log<sub>2</sub>}} से आसानी से गणना की जा सकती है {{math|clz}} और इसके विपरीत {{math|1=log<sub>2</sub>(''x'') = ''w'' − 1 − clz(''x'')}}.


जैसा कि ऊपर दिए गए उदाहरण में दिखाया गया है, पहले शून्य ढूंढें, अग्रणी शून्य गिनें, और अनुगामी शून्य गिनें संचालन को इनपुट को अस्वीकार करके और पहले सेट ढूंढें, अग्रणी शून्य गिनें, और अनुगामी शून्य गिनें का उपयोग करके कार्यान्वित किया जा सकता है। विपरीत भी सही है।
अहस्ताक्षरित लॉन्ग लॉन्ग
| ||
|}
== गुण और संबंध                                                                                                                                                                                                                    ==
यदि बिट्स को 1 से प्रारंभ करके लेबल किया गया है (जो कि इस आलेख में प्रयुक्त परंपरा है), तो अनुगामी शून्यों की गणना करें और पता लगाएं कि पहले सेट संचालन किससे संबंधित हैं {{math|1=ctz(''x'') = ffs(''x'') − 1}} (अतिरिक्त जब इनपुट शून्य हो)। यदि बिट्स को प्रारंभ से लेबल किया गया है {{math|0}}, फिर पिछले शून्यों की गणना करें और पता लगाएं कि फर्स्ट सेट बिल्कुल समतुल्य संचालन है। दिया गया {{math|''w''}} प्रति शब्द बिट्स, {{math|log<sub>2</sub>}} से आसानी से गणना की जा सकती है {{math|clz}} और इसके विपरीत {{math|1=log<sub>2</sub>(''x'') = ''w'' − 1 − clz(''x'')}}. है जैसा कि ऊपर दिए गए उदाहरण में दिखाया गया है, पहले शून्य फाइंड, अग्रणी शून्य गिनें, और अनुगामी शून्य गिनें संचालन को इनपुट को अस्वीकार करके और पहले सेट फाइंड, अग्रणी शून्य गिनें, और अनुगामी शून्य गिनें का उपयोग करके कार्यान्वित किया जा सकता है। विपरीत भी सही है।


कुशल लॉग वाले प्लेटफ़ॉर्म पर<sub>2</sub> M68000 जैसे ऑपरेशन, {{math|ctz}} द्वारा गणना की जा सकती है:
कुशल लॉग वाले प्लेटफ़ॉर्म पर M68000<sub>2</sub> जैसे संचालन, {{math|ctz}} द्वारा गणना की जा सकती है:


: {{math|ctz(''x'') {{=}} log<sub>2</sub>(''x'' & ''−x'')}}
: {{math|ctz(''x'') {{=}} log<sub>2</sub>(''x'' & ''−x'')}}


कहाँ {{math|&}} बिटवाइज़ AND और को दर्शाता है {{math|''−x''}} दोनों के पूरक को दर्शाता है {{math|''x''}}. इजहार {{math|''x'' & ''−x''}} न्यूनतम-महत्वपूर्ण को छोड़कर सभी को साफ़ करता है {{math|1}} बिट, ताकि सबसे अधिक- और सबसे कम-महत्वपूर्ण {{math|1}} बिट समान हैं.
कहाँ {{math|&}} बिटवाइज़ और और को दर्शाता है {{math|''−x''}} दोनों के पूरक को दर्शाता है {{math|''x''}}. इजहार {{math|''x'' & ''−x''}} न्यूनतम-महत्वपूर्ण को छोड़कर सभी को साफ़ करता है {{math|1}} बिट, जिससे सबसे अधिक- और सबसे कम-महत्वपूर्ण {{math|1}} बिट समान हैं.


एआरएम और पावरपीसी जैसे कुशल गिनती अग्रणी शून्य संचालन वाले प्लेटफार्मों पर, {{math|ffs}} द्वारा गणना की जा सकती है:
एआरएम और पावरपीसी जैसे कुशल गणना अग्रणी शून्य संचालन वाले प्लेटफार्मों पर, {{math|ffs}} द्वारा गणना की जा सकती है:


: {{math|ffs(''x'') {{=}} w − clz(''x'' & ''−x'')}}.
: {{math|ffs(''x'') {{=}} w − clz(''x'' & ''−x'')}}.


इसके विपरीत, बिना मशीनों पर {{math|log<sub>2</sub>}} या {{math|clz}} ऑपरेटर, {{math|clz}} का उपयोग करके गणना की जा सकती है {{math|ctz}}, यद्यपि अकुशलता से:
इसके विपरीत, बिना मशीनों पर {{math|log<sub>2</sub>}} या {{math|clz}} ऑपरेटर, {{math|clz}} का उपयोग करके गणना की जा सकती है , यद्यपि {{math|ctz}} अकुशलता से प्रयुक्त होता है:


: {{math|clz {{=}} ''w'' − ctz(2<sup>⌈log{{sub|2}}(''x'')⌉</sup>)}} (जिस पर निर्भर करता है {{math|ctz}} लौट रहा हूँ {{math|w}} शून्य इनपुट के लिए)
: {{math|clz {{=}} ''w'' − ctz(2<sup>⌈log{{sub|2}}(''x'')⌉</sup>)}} (जिस पर निर्भर करता है {{math|ctz}} लौट रहा हूँ {{math|w}} शून्य इनपुट के लिए)


[[SPARC]] जैसे कुशल [[ हथौड़ा चलाना वजन ]] (जनसंख्या गणना) ऑपरेशन वाले प्लेटफार्मों पर <code>POPC</code><ref name="SPARC_1992_A41"/><ref name="Warren_2013"/>या [[ Blackfin ]] का <code>ONES</code>,<ref name="AD_2001"/>वहाँ है:
[[SPARC|स्पार्क]] जैसे कुशल [[ हथौड़ा चलाना वजन |हथौड़ा चलाना वजन]] (जनसंख्या गणना) संचालन वाले प्लेटफार्मों पर <code>POPC</code> <ref name="SPARC_1992_A41"/><ref name="Warren_2013"/> या [[ Blackfin |ब्लैकफ़िन]] का <code>ONES</code>,<ref name="AD_2001"/> वहाँ है:


: {{math|ctz(''x'') {{=}} popcount((''x'' & ''−x'') − 1)}},<ref name="Dietz"/><ref name="Isenberg"/>या {{math|{{pipe escape|ctz(''x'') {{=}} popcount(~(''x'' | ''−x''))}}}},
: {{math|ctz(''x'') {{=}} popcount((''x'' & ''−x'') − 1)}},<ref name="Dietz"/><ref name="Isenberg"/>या {{math|{{pipe escape|ctz(''x'') {{=}} popcount(~(''x'' | ''−x''))}}}},
: {{math|ffs(''x'') {{=}} popcount(''x'' ^ ~−''x'')}}<ref name="SPARC_1992_A41"/>: {{math|clz {{=}} 32 − popcount(2<sup>⌈log{{sub|2}}(''x'')⌉</sup> − 1)}}
: {{math|ffs(''x'') {{=}} popcount(''x'' ^ ~−''x'')}}<ref name="SPARC_1992_A41"/>: {{math|clz {{=}} 32 − popcount(2<sup>⌈log{{sub|2}}(''x'')⌉</sup> − 1)}}


कहाँ {{math|^}} बिटवाइज़ एक्सक्लूसिव-OR को दर्शाता है, {{math|{{pipe escape||}}}} बिटवाइज़ OR और को दर्शाता है {{math|~}} बिटवाइज़ नकार को दर्शाता है।
जहाँ {{math|^}} बिटवाइज़ एक्सक्लूसिव-OR को दर्शाता है, {{math|{{pipe escape||}}}} बिटवाइज़ OR और को दर्शाता है {{math|~}} बिटवाइज़ नकार को दर्शाता है।


उलटा समस्या (दिया गया है {{math|''i''}}, एक उत्पादन करें {{math|''x''}} ऐसा है कि {{math|ctz(''x'') {{=}} ''i''}}) की गणना बाईं-शिफ्ट के साथ की जा सकती है ({{math|1 << ''i''}}).
उलटा समस्या (दिया गया है {{math|''i''}}, उत्पादन करें {{math|''x''}} ऐसा है कि {{math|ctz(''x'') {{=}} ''i''}}) की गणना बाईं-शिफ्ट ({{math|1 << ''i''}}) के साथ की जा सकती है .


पहला सेट ढूंढें और संबंधित संचालन को एक छोर से शुरू करके और एक शब्द तक आगे बढ़ते हुए सीधे तरीके से मनमाने ढंग से बड़े [[बिट सरणी]] तक बढ़ाया जा सकता है जो कि पूर्ण-शून्य नहीं है (के लिए) {{math|ffs}}, {{math|ctz}}, {{math|clz}}) या सभी-एक नहीं (के लिए)। {{math|ffz}}, {{math|clo}}, {{math|cto}}) का सामना करना पड़ता है। एक ट्री डेटा संरचना जो पुनरावर्ती रूप से बिटमैप का उपयोग करके ट्रैक करती है कि कौन से शब्द गैर-शून्य हैं, इसे तेज कर सकते हैं।
फर्स्ट सेट फाइंड और संबंधित संचालन को छोर से प्रारंभ करके और शब्द तक आगे बढ़ते हुए सीधे विधि से इच्छानुसार विधि से बड़े [[बिट सरणी]] तक बढ़ाया जा सकता है जो कि पूर्ण-शून्य नहीं है (के लिए) {{math|ffs}}, {{math|ctz}}, {{math|clz}}) या सभी-एक नहीं (के लिए)। {{math|ffz}}, {{math|clo}}, {{math|cto}}) का सामना करना पड़ता है। ट्री डेटा संरचना जो पुनरावर्ती रूप से बिटमैप का उपयोग करके ट्रैक करती है कि कौन से शब्द गैर-शून्य हैं, इसे तेज कर सकते हैं।


==सॉफ़्टवेयर अनुकरण==
==सॉफ़्टवेयर अनुकरण==
1980 के दशक के उत्तरार्ध के अधिकांश सीपीयू में एफएफएस या समकक्ष के लिए बिट ऑपरेटर होते हैं, लेकिन एआरएम-एमएक्स श्रृंखला जैसे कुछ आधुनिक सीपीयू में ऐसा नहीं होता है। एफएफएस, सीएलजेड और सीटीजेड के लिए हार्डवेयर ऑपरेटरों के बदले में, सॉफ्टवेयर उन्हें शिफ्ट, पूर्णांक अंकगणित और बिटवाइज़ ऑपरेटरों के साथ अनुकरण कर सकता है। सीपीयू की वास्तुकला और कुछ हद तक प्रोग्रामिंग भाषा के शब्दार्थ और कंपाइलर कोड पीढ़ी की गुणवत्ता के आधार पर कई दृष्टिकोण हैं। दृष्टिकोणों को शिथिल रूप से [[रैखिक खोज]] के रूप में वर्णित किया जा सकता है<!-- ctz1, clz1 -->, [[द्विआधारी खोज]]<!-- ctz3, clz3 -->, खोज+टेबल लुकअप<!-- ctz2(+ctz3), clz2(+clz3) -->, डी ब्रुइज़न गुणन<!-- ctz5, clz4 -->, फ़्लोटिंग पॉइंट रूपांतरण/प्रतिपादक अर्क<!-- clz6 -->, और बिट ऑपरेटर (शाखा रहित)<!-- ctz4, clz5 --> तरीके. निष्पादन समय और भंडारण स्थान के साथ-साथ पोर्टेबिलिटी और दक्षता के बीच भी विरोधाभास है।
1980 के दशक के उत्तरार्ध के अधिकांश सीपीयू में एफएफएस या समकक्ष के लिए बिट ऑपरेटर होते हैं, किन्तु एआरएम-एमएक्स श्रृंखला जैसे कुछ आधुनिक सीपीयू में ऐसा नहीं होता है। इस प्रकार एफएफएस, सीएलजेड और सीटीजेड के लिए हार्डवेयर ऑपरेटरों के बदले में, सॉफ्टवेयर उन्हें शिफ्ट, पूर्णांक अंकगणित और बिटवाइज़ ऑपरेटरों के साथ अनुकरण कर सकता है। सीपीयू की आर्किटेक्चर और कुछ सीमा तक प्रोग्रामिंग भाषा के शब्दार्थ और कंपाइलर कोड पीढ़ी की गुणवत्ता के आधार पर कई दृष्टिकोण हैं। दृष्टिकोणों को शिथिल रूप से [[रैखिक खोज]] के रूप में वर्णित किया जा सकता है, [[द्विआधारी खोज]], खोज+ टेबल लुकअप, डी ब्रुइज़न गुणन, फ़्लोटिंग पॉइंट रूपांतरण/प्रतिपादक अर्क, और बिट ऑपरेटर (शाखा रहित) विधि. निष्पादन समय और भंडारण स्थान के साथ-साथ पोर्टेबिलिटी और दक्षता के बीच भी विरोधाभास है।


सॉफ़्टवेयर अनुकरण आमतौर पर नियतात्मक होते हैं। वे सभी इनपुट मानों के लिए एक परिभाषित परिणाम लौटाते हैं; विशेष रूप से, सभी शून्य बिट्स के इनपुट का परिणाम आम तौर पर एफएफएस के लिए 0 होता है, और अन्य परिचालनों के लिए ऑपरेंड की बिट लंबाई होती है।
सॉफ़्टवेयर अनुकरण सामान्यतः नियतात्मक होते हैं। वे सभी इनपुट मानों के लिए परिभाषित परिणाम वापस करते हैं; विशेष रूप से, सभी शून्य बिट्स के इनपुट का परिणाम सामान्यतः एफएफएस के लिए 0 होता है, और अन्य परिचालनों के लिए ऑपरेंड की बिट लंबाई होती है।


यदि किसी के पास हार्डवेयर सीएलजेड या समकक्ष है, तो सीटीजेड को बिट ऑपरेशंस के साथ कुशलतापूर्वक गणना की जा सकती है, लेकिन इसका विपरीत सच नहीं है: हार्डवेयर ऑपरेटर की अनुपस्थिति में सीएलजेड गणना करने में कुशल नहीं है।
यदि किसी के पास हार्डवेयर सीएलजेड या समकक्ष है, जिससे सीटीजेड को बिट ऑपरेशंस के साथ कुशलतापूर्वक गणना की जा सकती है, किन्तु इसका विपरीत सच नहीं है: हार्डवेयर ऑपरेटर की अनुपस्थिति में सीएलजेड गणना करने में कुशल नहीं है।


===2<sup>n</sup>===
===2<sup>n</sup>===
कार्यक्रम {{math|2<sup>⌈log{{sub|2}}(x)⌉</sup>}} (दो की निकटतम घात तक पूर्णांकित करें) शिफ्ट और बिटवाइज़ ओआरएस का उपयोग करके<ref name="Anderson_2"/>इस 32-बिट उदाहरण की तरह गणना करना कुशल नहीं है और यदि हमारे पास 64-बिट या 128-बिट ऑपरेंड है तो यह और भी अधिक अक्षम है:
प्रोग्राम {{math|2<sup>⌈log{{sub|2}}(x)⌉</sup>}} (दो की निकटतम घात तक पूर्णांकित करें) शिफ्ट और बिटवाइज़ ओआरएस का उपयोग करके <ref name="Anderson_2"/> इस 32-बिट उदाहरण की तरह गणना करना कुशल नहीं है और यदि हमारे पास 64-बिट या 128-बिट ऑपरेंड है तो यह और भी अधिक अक्षम है:<syntaxhighlight>
 
function pow2(x):                                                                                        
फ़ंक्शन pow2(x):
    if x = 0 return invalid  // invalid is implementation defined (not in [0,63])
    यदि x = 0 वापसी ''अमान्य'' // ''अमान्य'' कार्यान्वयन परिभाषित है ([0,63] में नहीं)
    x ← x - 1                                                                                                
    एक्स ← एक्स - 1
    for each y in {1, 2, 4, 8, 16}: x ← x | (x >> y)                                            
    {1, 2, 4, 8, 16} में प्रत्येक y के लिए: x ← x | (एक्स >> वाई)
    return x + 1                                                          
    वापसी x + 1
</syntaxhighlight>


===एफएफएस===
===एफएफएस===
चूँकि ffs = ctz + 1 (POSIX) या ffs = ctz (अन्य कार्यान्वयन), ctz के लिए लागू एल्गोरिदम का उपयोग किया जा सकता है, जिसके परिणाम में 1 जोड़ने का संभावित अंतिम चरण होता है, और इनपुट के लिए ऑपरेंड लंबाई के बजाय 0 लौटाता है। सभी शून्य बिट्स.
चूँकि ffs = ctz + 1 (पॉज़िक्स) या ffs = ctz (अन्य कार्यान्वयन), ctz के लिए प्रयुक्त एल्गोरिदम का उपयोग किया जा सकता है, जिसके परिणाम में 1 जोड़ने का संभावित अंतिम चरण होता है, और इनपुट के लिए ऑपरेंड लंबाई के अतिरिक्त 0 वापस है। सभी शून्य बिट्स.


===CTZ===
===सीटीजेड===
{{anchor|ctz1}}कैनोनिकल एल्गोरिदम एलएसबी से शुरू होने वाले शून्यों की गिनती करने वाला एक लूप है जब तक कि 1-बिट का सामना न हो जाए:
कैनोनिकल एल्गोरिदम एलएसबी से प्रारंभ होने वाले शून्यों की गणना करने वाला लूप है जब तक कि 1-बिट का सामना न हो जाए:<syntaxhighlight>
 
function ctz1 (x)                                                                                          
फ़ंक्शन ctz1 (x)
    if x = 0 return w                                                                              
    यदि x = 0 वापसी w
    t ← 1                                                                                              
    टी ← 1
    r ← 0                                                                                                  
    आर ← 0
    while (x & t) = 0                                                                                    
    जबकि (x & t) = 0
        t ← t << 1                                                                                              
        टी ← टी << 1
        r ← r + 1                                                                                      
        आर ← आर + 1
    return r                                                                                                 
    वापसी आर
</syntaxhighlight>यह एल्गोरिदम O(n) समय और संचालन निष्पादित करता है, और बड़ी संख्या में सशर्त शाखाओं के कारण व्यवहार में अव्यावहारिक है। एक लुकअप तालिका अधिकांश शाखाओं को समाप्त कर सकती है:<syntaxhighlight>
 
table[0..2n-1] = ctz(i) for i in 0..2n-1                                                                  
यह एल्गोरिदम O(n) समय और संचालन निष्पादित करता है, और बड़ी संख्या में सशर्त शाखाओं के कारण व्यवहार में अव्यावहारिक है।
function ctz2 (x)                                                            
 
    if x = 0 return w
{{anchor|ctz2}}एक लुकअप तालिका अधिकांश शाखाओं को समाप्त कर सकती है:
    r ← 0                                                                                                                                                      
 
    loop                                                                     
तालिका[0..2<sup>n</sup>-1] = ctz(i) i के लिए 0..2 में<sup>n</sup>-1
        if (x & (2n-1)) ≠ 0
फ़ंक्शन ctz2 (x)
            return r + table[x & (2n-1)]                                                        
    यदि x = 0 वापसी w
        x ← x >> n                                                                      
    आर ← 0
        r ← r + n                                                                 
    कुंडली
</syntaxhighlight>पैरामीटर n निश्चित है (सामान्यतः 8) और समय-स्थान ट्रेडऑफ़ का प्रतिनिधित्व करता है। लूप पूरी तरह से [[ लूप का खुलना |लूप]] भी हो सकता है। किन्तु रैखिक लुकअप के रूप में, ऑपरेंड में बिट्स की संख्या में यह दृष्टिकोण अभी भी O(n) है। एक बाइनरी खोज कार्यान्वयन संचालन और शाखाओं की लघुगणकीय संख्या लेता है, जैसा कि इस 32-बिट संस्करण में है:<ref name="Warren_2013_5-3"/><ref name="Warren_2013_5-4"/> इस एल्गोरिदम को तालिका द्वारा भी सहायता प्रदान की जा सकती है, जो सूचकांक के रूप में सामने आए पहले गैर-शून्य बाइट का उपयोग करके 256 प्रविष्टि लुकअप तालिका के साथ नीचे के तीन यदि कथनों को प्रतिस्थापित करती है।<syntaxhighlight>
        अगर (एक्स और (2<sup>n</sup>-1)) ≠ 0
function ctz3 (x)                                              
            वापसी आर + तालिका [एक्स और (2<sup>n</sup>-1)]
    if x = 0 return 32                                                      
        x ← x >> n
    n ← 0                                              
        आर ← आर + एन
    if (x & 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16                                    
 
    if (x & 0x000000FF) = 0: n ← n + 8, x ← x >> 8                                            
पैरामीटर n निश्चित है (आमतौर पर 8) और समय-स्थान ट्रेडऑफ़ का प्रतिनिधित्व करता है। लूप पूरी तरह से [[ लूप का खुलना ]] भी हो सकता है। लेकिन एक रैखिक लुकअप के रूप में, ऑपरेंड में बिट्स की संख्या में यह दृष्टिकोण अभी भी O(n) है।
    if (x & 0x0000000F) = 0: n ← n + 4, x ← x >> 4                                                    
 
    if (x & 0x00000003) = 0: n ← n + 2, x ← x >> 2                                            
{{anchor|ctz3}}एक बाइनरी खोज कार्यान्वयन संचालन और शाखाओं की एक लघुगणकीय संख्या लेता है, जैसा कि इस 32-बिट संस्करण में है:<ref name="Warren_2013_5-3"/><ref name="Warren_2013_5-4"/>इस एल्गोरिदम को एक तालिका द्वारा भी सहायता प्रदान की जा सकती है, जो एक सूचकांक के रूप में सामने आए पहले गैर-शून्य बाइट का उपयोग करके 256 प्रविष्टि लुकअप तालिका के साथ नीचे के तीन यदि कथनों को प्रतिस्थापित करती है।
    if (x & 0x00000001) = 0: n ← n + 1    
 
    return n                                                                                   
फ़ंक्शन ctz3 (x)
</syntaxhighlight>यदि हार्डवेयर में clz ऑपरेटर है, तो ctz की गणना करने का सबसे कुशल विधि इस प्रकार है:<syntaxhighlight>
    यदि x = 0 है तो 32 लौटें
function ctz4 (x)                                                          
    एन ← 0
    x &= -x                             
    यदि (x और 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16
    return w - (clz(x) + 1)                                                        
    यदि (x और 0x000000FF) = 0: n ← n + 8, x ← x >> 8
</syntaxhighlight>32-बिट सीटीज़ के लिए एल्गोरिदम न्यूनतम सही हैश फ़ंक्शन बनाने के लिए डी ब्रुइज़न अनुक्रमों का उपयोग करता है जो सभी शाखाओं को समाप्त करता है।<ref name="Leiserson_1998"/><ref name="Busch_2009"/> यह एल्गोरिदम मानता है कि गुणन के परिणाम को 32 बिट तक छोटा कर दिया गया है।<syntaxhighlight>
    यदि (x और 0x0000000F) = 0: n ← n + 4, x ← x >> 4
for i from 0 to 31: table[ ( 0x077CB531 * ( 1 << i ) ) >> 27 ] ← i // table [0..31] initialized                       
    यदि (x और 0x00000003) = 0: n ← n + 2, x ← x >> 2
function ctz5 (x)                                                                                          
    यदि (x और 0x00000001) = 0: n ← n + 1
    return table[((x & -x) * 0x077CB531) >> 27]                                                          
    वापसी एन
</syntaxhighlight>अभिव्यक्ति (x & -x) फिर से सबसे कम महत्वपूर्ण 1 बिट को अलग करती है। तब केवल 32 संभावित शब्द हैं, जिन्हें अहस्ताक्षरित गुणन और हैश को तालिका में सही स्थिति में स्थानांतरित किया जाता है। (यह एल्गोरिदम शून्य इनपुट को संभाल नहीं पाता है।)
 
{{anchor|ctz4}}यदि हार्डवेयर में clz ऑपरेटर है, तो ctz की गणना करने का सबसे कुशल तरीका इस प्रकार है:
 
फ़ंक्शन ctz4 (x)
    एक्स &= -एक्स
    वापसी w - (clz(x) + 1)
 
{{anchor|ctz5}}32-बिट सीटीज़ के लिए एक एल्गोरिदम एक न्यूनतम सही हैश फ़ंक्शन बनाने के लिए डी ब्रुइज़न अनुक्रमों का उपयोग करता है जो सभी शाखाओं को समाप्त करता है।<ref name="Leiserson_1998"/><ref name="Busch_2009"/>यह एल्गोरिदम मानता है कि गुणन के परिणाम को 32 बिट तक छोटा कर दिया गया है।
 
i के लिए 0 से 31 तक: तालिका[( 0x077CB531 * (1 << i ) ) >> 27 ] ← i // तालिका [0..31] आरंभीकृत
फ़ंक्शन ctz5 (x)
    वापसी तालिका[((x & -x) * 0x077CB531) >> 27]
 
अभिव्यक्ति (x & -x) फिर से सबसे कम महत्वपूर्ण 1 बिट को अलग करती है। तब केवल 32 संभावित शब्द हैं, जिन्हें अहस्ताक्षरित गुणन और हैश को तालिका में सही स्थिति में स्थानांतरित किया जाता है। (यह एल्गोरिदम शून्य इनपुट को संभाल नहीं पाता है।)


===कल्ज़===
===कल्ज़===
{{anchor|clz1}}कैनोनिकल एल्गोरिदम एमएसबी से शुरू करके एक समय में एक बिट की जांच करता है जब तक कि एक गैर-शून्य बिट नहीं मिल जाता, जैसा कि इस उदाहरण में दिखाया गया है। यह O(n) समय में निष्पादित होता है जहां n ऑपरेंड की बिट-लंबाई है, और सामान्य उपयोग के लिए एक व्यावहारिक एल्गोरिदम नहीं है।
कैनोनिकल एल्गोरिदम एमएसबी से प्रारंभ करके समय में बिट की जांच करता है जब तक कि गैर-शून्य बिट नहीं मिल जाता है, जैसा कि इस उदाहरण में दिखाया गया है। यह O(n) समय में निष्पादित होता है जहां n ऑपरेंड की बिट-लंबाई है, और सामान्य उपयोग के लिए व्यावहारिक एल्गोरिदम नहीं है।<syntaxhighlight>
 
function clz1 (x)                                          
फ़ंक्शन clz1 (x)
    if x = 0 return w                                      
    यदि x = 0 वापसी w
    t ← 1 << (w - 1)                                    
    टी ← 1 << (डब्ल्यू - 1)
    r ← 0                                              
    आर ← 0
    while (x & t) = 0                                  
    जबकि (x & t) = 0
        t ← t >> 1                                      
        टी ← टी >> 1
        r ← r + 1                                        
        आर ← आर + 1
    return r                                               
    वापसी आर
</syntaxhighlight>पिछले लूपिंग दृष्टिकोण में सुधार समय में आठ बिट्स की जांच करता है और फिर 256 (2<sup>8</sup>) का उपयोग करता है) पहले गैर-शून्य बाइट के लिए प्रविष्टि लुकअप तालिका चूँकि, यह दृष्टिकोण निष्पादन समय में अभी भी O(n) है।<syntaxhighlight>
 
function clz2 (x)
{{anchor|clz2}}पिछले लूपिंग दृष्टिकोण में सुधार एक समय में आठ बिट्स की जांच करता है और फिर 256 (2) का उपयोग करता है<sup>8</sup>) पहले गैर-शून्य बाइट के लिए प्रविष्टि लुकअप तालिका। हालाँकि, यह दृष्टिकोण निष्पादन समय में अभी भी O(n) है।
    if x = 0 return w
 
    t ← 0xff << (w - 8)
फ़ंक्शन clz2 (x)
    r ← 0
    यदि x = 0 वापसी w
    while (x & t) = 0
    t ← 0xff << (w - 8)
        t ← t >> 8
    आर ← 0
        r ← r + 8
    जबकि (x & t) = 0
    return r + table[x >> (w - 8 - r)]
        टी ← टी >> 8
</syntaxhighlight>बाइनरी खोज निष्पादन समय को घटाकर O<sub>2</sub>n लॉग कर सकती है:<syntaxhighlight>
        आर ← आर + 8
function clz3 (x)
    रिटर्न आर + टेबल[x >> (डब्ल्यू - 8 - आर)]
    if x = 0 return 32
 
    n ← 0
{{anchor|clz3}}बाइनरी खोज निष्पादन समय को घटाकर O(लॉग) कर सकती है<sub>2</sub>एन):
    if (x & 0xFFFF0000) = 0: n ← n + 16, x ← x << 16                                                      
 
    if (x & 0xFF000000) = 0: n ← n + 8, x ← x << 8                                                        
फ़ंक्शन clz3 (x)
    if (x & 0xF0000000) = 0: n ← n + 4, x ← x << 4                                                      
    यदि x = 0 है तो 32 लौटें
    if (x & 0xC0000000) = 0: n ← n + 2, x ← x << 2                                                          
    एन ← 0
    if (x & 0x80000000) = 0: n ← n + 1
    यदि (x और 0xFFFF0000) = 0: n ← n + 16, x ← x << 16
    return n
    यदि (x और 0xFF000000) = 0: n ← n + 8, x ← x << 8
</syntaxhighlight>सीएलज़ को अनुकरण करने के लिए सबसे तेज़ पोर्टेबल दृष्टिकोण बाइनरी सर्च और टेबल लुकअप का संयोजन है: 8-बिट टेबल लुकअप (2)<sup>8</sup>=256 1-बाइट प्रविष्टियाँ) बाइनरी खोज में नीचे की 3 शाखाओं को प्रतिस्थापित कर सकती हैं। 64-बिट ऑपरेंड को अतिरिक्त शाखा की आवश्यकता होती है। बड़ी चौड़ाई वाले लुकअप का उपयोग किया जा सकता है किन्तु अधिकतम व्यावहारिक तालिका का आकार आधुनिक प्रोसेसर पर L1 डेटा कैश के आकार तक सीमित है, जो कई लोगों के लिए 32 KB है। किसी शाखा को सहेजना L1 कैश मिस की विलंबता से ऑफसेट से कहीं अधिक है। CTZ के लिए डी ब्रुइज़न गुणन के समान एल्गोरिथ्म CLZ के लिए कार्य करता है, किन्तु सबसे महत्वपूर्ण बिट को अलग करने के अतिरिक्त, यह फॉर्म 2<sup>n</sup>−1 के निकटतम पूर्णांक तक पूर्णांक बनाता है शिफ्ट और बिटवाइज़ ORs का उपयोग करता है:<ref name="Anderson_3"/><syntaxhighlight>
    यदि (x और 0xF0000000) = 0: n ← n + 4, x ← x << 4
table[0..31] = {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
    यदि (x और 0xC0000000) = 0: n ← n + 2, x ← x << 2
                8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31}
    यदि (x और 0x80000000) = 0: n ← n + 1
function clz4 (x)
    वापसी एन
    for each y in {1, 2, 4, 8, 16}: x ← x | (x >> y)
 
    return table[((x * 0x07C4ACDD) >> 27) % 32]
सीएलज़ को अनुकरण करने के लिए सबसे तेज़ पोर्टेबल दृष्टिकोण बाइनरी सर्च और टेबल लुकअप का संयोजन है: एक 8-बिट टेबल लुकअप (2)<sup>8</sup>=256 1-बाइट प्रविष्टियाँ) बाइनरी खोज में नीचे की 3 शाखाओं को प्रतिस्थापित कर सकती हैं। 64-बिट ऑपरेंड को एक अतिरिक्त शाखा की आवश्यकता होती है। बड़ी चौड़ाई वाले लुकअप का उपयोग किया जा सकता है लेकिन अधिकतम व्यावहारिक तालिका का आकार आधुनिक प्रोसेसर पर L1 डेटा कैश के आकार तक सीमित है, जो कई लोगों के लिए 32 KB है। किसी शाखा को सहेजना L1 कैश मिस की विलंबता से ऑफसेट से कहीं अधिक है।
</syntaxhighlight>गहरे पाइपलाइन वाले प्रोसेसर के लिए, जैसे प्रेस्कॉट और बाद के इंटेल प्रोसेसर, गलत पूर्वानुमानित शाखाओं के लिए पाइपलाइन फ्लश से बचने के लिए शाखाओं को बिटवाइज़ और और OR ऑपरेटरों (तथापि कई और निर्देशों की आवश्यकता होती है) द्वारा प्रतिस्थापित करना तेज़ हो सकता है (और इस प्रकार की शाखाएं हैं) स्वाभाविक रूप से अप्रत्याशित):<syntaxhighlight>
 
function clz5 (x)                                                                                          
{{anchor|clz4}}CTZ के लिए डी ब्रुइज़न गुणन के समान एक एल्गोरिथ्म CLZ के लिए काम करता है, लेकिन सबसे महत्वपूर्ण बिट को अलग करने के बजाय, यह फॉर्म 2 के निकटतम पूर्णांक तक पूर्णांक बनाता है<sup>n</sup>−1 शिफ्ट और बिटवाइज़ ORs का उपयोग करना:<ref name="Anderson_3"/>
  r = (x > 0xFFFF) << 4; x >>= r;                                                                            
तालिका[0..31] = {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  q = (x > 0xFF ) << 3; x >>= q; r |= q;                                                              
                8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31}
  q = (x > 0xF   ) << 2; x >>= q; r |= q;                                                                  
फ़ंक्शन clz4 (x)
  q = (x > 0x3   ) << 1; x >>= q; r |= q;                                                                
    {1, 2, 4, 8, 16} में प्रत्येक y के लिए: x ← x | (एक्स >> वाई)
                                  r |= (x >> 1);                                              
    वापसी तालिका[((x * 0x07C4ACDD) >> 27) % 32]
  return r;                                                                                              
 
</syntaxhighlight>उन प्लेटफार्मों पर जो पूर्णांकों को फ़्लोटिंग पॉइंट में हार्डवेयर रूपांतरण प्रदान करते हैं, अग्रणी शून्य की गणना की गणना करने के लिए घातांक फ़ील्ड को स्थिरांक से निकाला और घटाया जा सकता है। पूर्णांकन त्रुटियों को ध्यान में रखते हुए सुधार की आवश्यकता है।<ref name="Warren_2013_5-3"/><ref name="Anderson_4"/> फ़्लोटिंग पॉइंट रूपांतरण में पर्याप्त विलंबता हो सकती है। यह विधि अत्यधिक गैर-पोर्टेबल है और सामान्यतः इसकी अनुशंसा नहीं की जाती है।
{{anchor|clz5}}गहरे पाइपलाइन वाले प्रोसेसर के लिए, जैसे प्रेस्कॉट और बाद के इंटेल प्रोसेसर, गलत पूर्वानुमानित शाखाओं के लिए पाइपलाइन फ्लश से बचने के लिए शाखाओं को बिटवाइज़ AND और OR ऑपरेटरों (भले ही कई और निर्देशों की आवश्यकता होती है) द्वारा प्रतिस्थापित करना तेज़ हो सकता है (और इस प्रकार की शाखाएं हैं) स्वाभाविक रूप से अप्रत्याशित):
 
फ़ंक्शन clz5 (x)
    आर = (x > 0xFFFF) << 4; एक्स >>= आर;
    क्यू = (x > 0xFF ) << 3; एक्स >>= क्यू; आर |= क्यू;
    q = (x > 0xF ) << 2; एक्स >>= क्यू; आर |= क्यू;
    क्यू = (x > 0x3 ) << 1; एक्स >>= क्यू; आर |= क्यू;
                                    आर |= (x >> 1);
    वापसी आर;
 
{{anchor|clz6}}उन प्लेटफार्मों पर जो पूर्णांकों को फ़्लोटिंग पॉइंट में हार्डवेयर रूपांतरण प्रदान करते हैं, अग्रणी शून्य की गिनती की गणना करने के लिए घातांक फ़ील्ड को स्थिरांक से निकाला और घटाया जा सकता है। पूर्णांकन त्रुटियों को ध्यान में रखते हुए सुधार की आवश्यकता है।<ref name="Warren_2013_5-3"/><ref name="Anderson_4"/>फ़्लोटिंग पॉइंट रूपांतरण में पर्याप्त विलंबता हो सकती है। यह विधि अत्यधिक गैर-पोर्टेबल है और आमतौर पर इसकी अनुशंसा नहीं की जाती है।
<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
int x;  
int x;  
Line 281: Line 281:
r++;  // CLZ
r++;  // CLZ
</syntaxhighlight>
</syntaxhighlight>
==अनुप्रयोग==
==अनुप्रयोग==
सामान्यीकरण को कुशलतापूर्वक लागू करने के लिए गिनती अग्रणी शून्य (सीएलजेड) ऑपरेशन का उपयोग किया जा सकता है, जो एक पूर्णांक को एम × 2 के रूप में एन्कोड करता है<sup>e</sup>, जहां m का ज्ञात स्थिति में सबसे महत्वपूर्ण बिट है (जैसे कि उच्चतम स्थिति)। इसके बदले में इसका उपयोग न्यूटन-रेफसन डिवीजन को लागू करने, सॉफ्टवेयर और अन्य अनुप्रयोगों में पूर्णांक से [[ तैरनेवाला स्थल ]] रूपांतरण करने के लिए किया जा सकता है।<ref name="Warren_2013_5-3"/><ref name="Sloss_2004"/>
सामान्यीकरण को कुशलतापूर्वक प्रयुक्त करने के लिए गणना अग्रणी शून्य (सीएलजेड) संचालन का उपयोग किया जा सकता है, जो पूर्णांक को m× 2<sup>e</sup> के रूप में एन्कोड करता है, जहां m का ज्ञात स्थिति में सबसे महत्वपूर्ण बिट है (जैसे कि उच्चतम स्थिति)। इसके बदले में इसका उपयोग न्यूटन-रेफसन डिवीजन को प्रयुक्त करने, सॉफ्टवेयर और अन्य अनुप्रयोगों में पूर्णांक से [[ तैरनेवाला स्थल |फ़्लोटिंग पॉइंट]] रूपांतरण करने के लिए किया जा सकता है।<ref name="Warren_2013_5-3"/><ref name="Sloss_2004"/>


अग्रणी शून्यों की गणना करें (clz) का उपयोग पहचान के माध्यम से 32-बिट विधेय x = y (यदि सत्य है तो शून्य, यदि गलत है तो एक) की गणना करने के लिए किया जा सकता है {{tt|clz(x − y) >> 5}}, जहां >> अहस्ताक्षरित दायां बदलाव है।<ref name="Warren_2013_2-11"/>इसका उपयोग अधिक परिष्कृत बिट संचालन करने के लिए किया जा सकता है जैसे n 1 बिट्स की पहली स्ट्रिंग ढूंढना।<ref name="Warren_2013_6-2"/>इजहार {{tt|clz(x − y)1 << (16&nbsp;−&nbsp;clz(x&nbsp;−&nbsp;1)/2)}} न्यूटन की विधि का उपयोग करके 32-बिट पूर्णांक के वर्गमूल की गणना के लिए एक प्रभावी प्रारंभिक अनुमान है।<ref name="Warren_2013_11-1"/>सीएलजेड कुशलतापूर्वक शून्य दमन को कार्यान्वित कर सकता है, एक तेज़ डेटा संपीड़न तकनीक जो एक पूर्णांक को गैर-शून्य बाइट्स के साथ अग्रणी शून्य बाइट्स की संख्या के रूप में एन्कोड करती है।<ref name="Schlegel_2010"/>यह समान वितरण (असतत) पूर्णांकों का सीएलजेड लेकर कुशलतापूर्वक घातीय वितरण पूर्णांक उत्पन्न कर सकता है।<ref name="Warren_2013_5-3"/>
अग्रणी शून्यों की गणना करें (clz) का उपयोग पहचान के माध्यम से 32-बिट विधेय x = y (यदि सत्य है तो शून्य, यदि गलत है तो एक) की गणना करने के लिए किया जा सकता है {{tt|clz(x − y) >> 5}}, जहां >> अहस्ताक्षरित दायां बदलाव है।<ref name="Warren_2013_2-11"/> इसका उपयोग अधिक परिष्कृत बिट संचालन करने के लिए किया जा सकता है जैसे n 1 बिट्स की पहली स्ट्रिंग खोजना होता है।<ref name="Warren_2013_6-2"/> इस प्रकार {{tt|clz(x − y)1 << (16&nbsp;−&nbsp;clz(x&nbsp;−&nbsp;1)/2)}} न्यूटन की विधि का उपयोग करके 32-बिट पूर्णांक के वर्गमूल की गणना के लिए प्रभावी प्रारंभिक अनुमान है।<ref name="Warren_2013_11-1"/> सीएलजेड कुशलतापूर्वक शून्य दमन को कार्यान्वित कर सकता है, तेज़ डेटा संपीड़न तकनीक जो पूर्णांक को गैर-शून्य बाइट्स के साथ अग्रणी शून्य बाइट्स की संख्या के रूप में एन्कोड करती है।<ref name="Schlegel_2010"/> यह समान वितरण (असतत) पूर्णांकों का सीएलजेड लेकर कुशलतापूर्वक घातीय वितरण पूर्णांक उत्पन्न कर सकता है।<ref name="Warren_2013_5-3"/>


लॉग बेस 2 का उपयोग यह अनुमान लगाने के लिए किया जा सकता है कि गुणन अतिप्रवाह होगा या नहीं {{math|⌈log{{sub|2}}(xy)⌉ ≤ ⌈log{{sub|2}}(x)⌉ + ⌈log{{sub|2}}(y)⌉}}.<ref name="Warren_2013_2-12"/>
लॉग बेस 2 का उपयोग यह अनुमान लगाने के लिए किया जा सकता है कि गुणन अतिप्रवाह होगा या नहीं {{math|⌈log{{sub|2}}(xy)⌉ ≤ ⌈log{{sub|2}}(x)⌉ + ⌈log{{sub|2}}(y)⌉}}.<ref name="Warren_2013_2-12"/>


गोस्पर के लूप-डिटेक्शन एल्गोरिदम को लागू करने के लिए अग्रणी शून्यों की गिनती और अनुगामी शून्यों की गिनती का एक साथ उपयोग किया जा सकता है,<ref name="Gosper_1972"/>जो सीमित संसाधनों का उपयोग करके परिमित सीमा के किसी फ़ंक्शन की अवधि ज्ञात कर सकता है।<ref name="Warren_2013_5-4"/>
गोस्पर के लूप-डिटेक्शन एल्गोरिदम को प्रयुक्त करने के लिए अग्रणी शून्यों की गणना और अनुगामी शून्यों की गणना का साथ उपयोग किया जा सकता है,<ref name="Gosper_1972"/> जो सीमित संसाधनों का उपयोग करके परिमित सीमा के किसी फ़ंक्शन की अवधि ज्ञात कर सकता है।<ref name="Warren_2013_5-4"/>


[[बाइनरी जीसीडी एल्गोरिदम]] पिछले शून्य को हटाने में कई चक्र खर्च करता है; इसे एक बदलाव के बाद शून्य के पीछे की गिनती (ctz) से बदला जा सकता है। एक समान लूप हेलस्टोन अनुक्रम की गणना में दिखाई देता है।
[[बाइनरी जीसीडी एल्गोरिदम]] पिछले शून्य को हटाने में कई चक्र खर्च करता है; इसे बदलाव के बाद शून्य के पीछे की गणना (ctz) से बदला जा सकता है। समान लूप हेलस्टोन अनुक्रम की गणना में दिखाई देता है।


[[प्राथमिकता कतार]] को लागू करने के लिए एक बिट सरणी का उपयोग किया जा सकता है। इस संदर्भ में, फाइंड फर्स्ट सेट (एफएफएस) पॉप या पुल उच्चतम प्राथमिकता वाले तत्व ऑपरेशन को कुशलतापूर्वक लागू करने में उपयोगी है। [[लिनक्स कर्नेल]] रीयल-टाइम शेड्यूलर आंतरिक रूप से उपयोग करता है <code>sched_find_first_bit()</code> इस उद्देश्य से।<ref name="Aas_2005"/>
[[प्राथमिकता कतार|प्राथमिकता]] को प्रयुक्त करने के लिए बिट सरणी का उपयोग किया जा सकता है। इस संदर्भ में, फाइंड फर्स्ट सेट (एफएफएस) पॉप या पुल उच्चतम प्राथमिकता वाले तत्व संचालन को कुशलतापूर्वक प्रयुक्त करने में उपयोगी है। [[लिनक्स कर्नेल]] रीयल-टाइम शेड्यूलर आंतरिक रूप से <code>sched_find_first_bit()</code> उपयोग करता है।<ref name="Aas_2005"/>


काउंट ट्रेलिंग शून्य ऑपरेशन हनोई टॉवर समस्या का एक सरल इष्टतम समाधान देता है: डिस्क को शून्य से क्रमांकित किया जाता है, और चाल k पर, डिस्क संख्या ctz(k) को दाईं ओर न्यूनतम संभव दूरी पर ले जाया जाता है (वापस चारों ओर चक्कर लगाते हुए) आवश्यकतानुसार छोड़ दिया गया)। यह एक मनमाना शब्द लेकर और चरण k पर बिट ctz(k) फ़्लिप करके एक [[ग्रे कोड]] भी उत्पन्न कर सकता है।<ref name="Warren_2013_5-4"/>
काउंट ट्रेलिंग शून्य संचालन हनोई टॉवर समस्या का सरल इष्टतम समाधान देता है: डिस्क को शून्य से क्रमांकित किया जाता है, और गति k पर, डिस्क संख्या ctz(k) को दाईं ओर न्यूनतम संभव दूरी पर ले जाया जाता है (वापस चारों ओर चक्कर लगाते हुए) आवश्यकतानुसार छोड़ दिया गया)। यह सही शब्द लेकर और चरण k पर बिट ctz(k) फ़्लिप करके [[ग्रे कोड]] भी उत्पन्न कर सकता है।<ref name="Warren_2013_5-4"/>
 
==यह भी देखें                                                                                                                                                                                                                               ==
 
==यह भी देखें==
* इंटेल और एएमडी x86-आधारित प्रोसेसर के लिए [[बिट हेरफेर अनुदेश सेट]] (बीएमआई)।
* इंटेल और एएमडी x86-आधारित प्रोसेसर के लिए [[बिट हेरफेर अनुदेश सेट]] (बीएमआई)।
*[[शून्य से पीछे चल रहा है]]
*[[शून्य से पीछे चल रहा है]]
Line 308: Line 304:
==टिप्पणियाँ==
==टिप्पणियाँ==
{{Reflist|group="nb"|refs=
{{Reflist|group="nb"|refs=
<ref group="nb" name="NB1">Using bit operations on other than an unsigned machine word may yield undefined results.</ref>
<ref group="nb" name="NB1">अहस्ताक्षरित मशीन शब्द के अतिरिक्त अन्य पर बिट संचालन का उपयोग करने से अपरिभाषित परिणाम मिल सकते हैं.</ref>
<ref group="nb" name="NB2">These four operations also have (much less common) negated versions:
<ref group="nb" name="NB2">इन चार ऑपरेशनों में (बहुत कम सामान्य) अस्वीकृत संस्करण भी हैं:
* '''find first zero''' ('''ffz'''), which identifies the index of the least significant zero bit;
* '''पहला शून्य खोजें'''' ('''ffz'''), जो कम से कम महत्वपूर्ण शून्य बिट के सूचकांक की पहचान करता है;
* '''count trailing ones''', which counts the number of one bits following the least significant zero bit.
* '''अनुगामी बिट्स की गिनती करें''', जो कम से कम महत्वपूर्ण शून्य बिट के बाद एक बिट्स की संख्या की गणना करता है।
* '''count leading ones''', which counts the number of one bits preceding the most significant zero bit;
* '''अग्रणी बिट्स की गिनती करें''', जो सबसे महत्वपूर्ण शून्य बिट से पहले के एक बिट्स की संख्या की गणना करता है;
* find the index of the most significant zero bit, which is an inverted version of the [[binary logarithm]].</ref>
* सबसे महत्वपूर्ण शून्य बिट का सूचकांक खोजे, जो [[बाइनरी लॉगरिदम]] का उलटा संस्करण है.</ref>
}}
}}
==संदर्भ==
==संदर्भ==
{{Reflist|refs=
{{Reflist|refs=
Line 372: Line 366:
<ref name="DEC_1987_VAX">{{cite book |title=VAX Architecture Reference Manual |date=1987 |publisher=[[Digital Equipment Corporation]] (DEC) |pages=70–71 |url=http://www.bitsavers.org/pdf/dec/vax/archSpec/EY-3459E-DP_VAX_Architecture_Reference_Manual_1987.pdf |access-date=2020-01-09 |url-status=live |archive-url=https://web.archive.org/web/20190929103217/http://bitsavers.org/pdf/dec/vax/archSpec/EY-3459E-DP_VAX_Architecture_Reference_Manual_1987.pdf |archive-date=2019-09-29}}</ref>
<ref name="DEC_1987_VAX">{{cite book |title=VAX Architecture Reference Manual |date=1987 |publisher=[[Digital Equipment Corporation]] (DEC) |pages=70–71 |url=http://www.bitsavers.org/pdf/dec/vax/archSpec/EY-3459E-DP_VAX_Architecture_Reference_Manual_1987.pdf |access-date=2020-01-09 |url-status=live |archive-url=https://web.archive.org/web/20190929103217/http://bitsavers.org/pdf/dec/vax/archSpec/EY-3459E-DP_VAX_Architecture_Reference_Manual_1987.pdf |archive-date=2019-09-29}}</ref>
}}
}}
==अग्रिम पठन==
==अग्रिम पठन==
* {{anchor|Warren}}{{Cite book |title=Hacker's Delight |title-link=Hacker's Delight |author-first=Henry S. |author-last=Warren, Jr. |date=2013 |orig-date=2002 |edition=2 |publisher=[[Addison Wesley]] - [[Pearson Education, Inc.]] |isbn=978-0-321-84268-8 |id=0-321-84268-5}}
* {{Cite book |title=Hacker's Delight |title-link=Hacker's Delight |author-first=Henry S. |author-last=Warren, Jr. |date=2013 |orig-date=2002 |edition=2 |publisher=[[Addison Wesley]] - [[Pearson Education, Inc.]] |isbn=978-0-321-84268-8 |id=0-321-84268-5}}
* {{anchor|Anderson}}{{cite web |author-last=Anderson |author-first=Sean Eron |title=Bit Twiddling Hacks |url=http://graphics.stanford.edu/~seander/bithacks.html |date=2005 |orig-date=1997 |publisher=[[Stanford University]] |access-date=2012-01-03 |url-status=live |archive-url=https://web.archive.org/web/20200108172348/http://graphics.stanford.edu/~seander/bithacks.html |archive-date=2020-01-08}} (NB. Lists several efficient public domain C implementations for [http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear count trailing zeros] and [http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious log base 2].)
* {{cite web |author-last=Anderson |author-first=Sean Eron |title=Bit Twiddling Hacks |url=http://graphics.stanford.edu/~seander/bithacks.html |date=2005 |orig-date=1997 |publisher=[[Stanford University]] |access-date=2012-01-03 |url-status=live |archive-url=https://web.archive.org/web/20200108172348/http://graphics.stanford.edu/~seander/bithacks.html |archive-date=2020-01-08}} (NB. Lists several efficient public domain C implementations for [http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear अनुगामी शून्यों की गणना करें] और [http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious log base 2].)
 
 
==बाहरी संबंध==
==बाहरी संबंध==
* [https://software.intel.com/sites/landingpage/IntrinsicsGuide/ Intel Intrinsics Guide]
* [https://software.intel.com/sites/landingpage/IntrinsicsGuide/ Intel आंतरिकs Guide]
* [https://www.chessprogramming.org/BitScan Chess Programming Wiki: BitScan]: A detailed explanation of a number of implementation methods for ffs (called LS1B) and log base 2 (called MS1B).
* [https://www.chessprogramming.org/BitScan Chess Programming Wiki: BitScan]: A detailed explanation of a number of implementation methods for एफएफएस (called LS1B) और log base 2 (called MS1B).
[[Category: बाइनरी अंकगणित]] [[Category: कंप्यूटर अंकगणित]]
 
 


[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with reference errors]]
[[Category:Pages with script errors]]
[[Category:Pages with syntax highlighting errors]]
[[Category:Templates Vigyan Ready]]
[[Category:कंप्यूटर अंकगणित]]
[[Category:बाइनरी अंकगणित]]

Latest revision as of 12:32, 25 July 2023

कंप्यूटर सॉफ़्टवेयर और हार्डवेयर में, फर्स्ट सेट (एफएफएस) फाइंड बिट संचालन है, जिसे मशीन शब्द (कंप्यूटर आर्किटेक्चर)[nb 1] दिया गया है, इस प्रकार कम से कम महत्वपूर्ण बिट स्थिति से शब्द गणना में पर सेट किए गए कम से कम महत्वपूर्ण बिट के सूचकांक या स्थिति को निर्दिष्ट करता है। इस प्रकार लगभग समतुल्य संचालन अनुगामी शून्यों (ctz) या अनुगामी शून्यों की संख्या (ntz) की गणना है, जो कम से कम महत्वपूर्ण बिट के बाद शून्य बिट्स की संख्या की गणना करता है। इस प्रकार पूरक संचालन जो सबसे महत्वपूर्ण सेट बिट के सूचकांक या स्थिति का पता लगाता है, लॉग बेस 2 है, इसलिए इसे इसलिए कहा जाता है क्योंकि यह द्विआधारी लघुगणक ⌊log2(x)⌋ की गणना करता है .[1] यह अग्रणी शून्य (सीएलजेड) या अग्रणी शून्य की संख्या (एनएलजेड) की गणना करने के लिए गुण और संबंध है, जो सबसे महत्वपूर्ण बिट से पहले शून्य बिट्स की संख्या की गणना करता है। पहले सेट को खोजने के दो सामान्य प्रकार हैं, पॉज़िक्स परिभाषा जो 1 पर बिट्स का अनुक्रमण प्रारंभ करती है,[2] यहां एफएफएस लेबल किया गया है, और वह वेरिएंट जो शून्य पर बिट्स का अनुक्रमण प्रारंभ करता है, जो सीटीजेड के सामान्य है और इसलिए उसे उस नाम से बुलाया जाता है।[nb 2]

अधिकांश आधुनिक सीपीयू अनुदेश सेट आर्किटेक्चर इनमें से या अधिक को हार्डवेयर ऑपरेटर के रूप में प्रदान करते हैं; इस प्रकार सॉफ़्टवेयर अनुकरण सामान्यतः उन सभी के लिए प्रदान किया जाता है जो उपलब्ध नहीं हैं, या तो कंपाइलर इंट्रिनिक्स के रूप में या सिस्टम लाइब्रेरीज़ में उपयोग किया जाता है।

उदाहरण

निम्नलिखित 32-बिट शब्द दिया गया है:

0000 0000 0000 0000 1000 0000 0000 1000

गणना के पीछे शून्य संचालन 3 वापस करता है, जबकि गणना अग्रणी शून्य संचालन 16 वापस करता है। इस प्रकार गणना अग्रणी शून्य संचालन शब्द आकार पर निर्भर करता है: यदि इस 32-बिट शब्द को 16-बिट शब्द में छोटा कर दिया गया था, तो गणना अग्रणी शून्य शून्य वापस आएगा फर्स्ट सेट फाइंड संचालन 4 वापस करता है, जो दाईं ओर से चौथी स्थिति को दर्शाता है। लॉग बेस 2 15 है।

इसी प्रकार, निम्नलिखित 32-बिट शब्द को देखते हुए, उपरोक्त शब्द का बिटवाइज़ निषेध है:

1111 1111 1111 1111 0111 1111 1111 0111

काउंट ट्रेलिंग वन्स संचालन 3 वापस करता है, काउंट लीडिंग वन्स संचालन 16 वापस करता है, और फाइंड फर्स्ट जीरो संचालन ffz 4 वापस करता है।

यदि शब्द शून्य है (कोई बिट्स सेट नहीं है), तो अग्रणी शून्यों की गणना करें और पिछले शून्यों की गणना करें, दोनों शब्द में बिट्स की संख्या वापस करते हैं, जबकि एफएफएस शून्य वापस करते है। लॉग बेस 2 और फाइंड फर्स्ट सेट के शून्य-आधारित कार्यान्वयन दोनों सामान्यतः शून्य शब्द के लिए अपरिभाषित परिणाम वापस करते हैं।

हार्डवेयर समर्थन

कई आर्किटेक्चर में नीचे सूचीबद्ध पहले सेट और/या संबंधित संचालन को तेजी से निष्पादित करने के लिए निर्देश सेट सम्मिलित हैं। सबसे सामान्य संचालन गणना अग्रणी शून्य (सीएलजेड) है, संभवतः क्योंकि अन्य सभी संचालन इसके संदर्भ में कुशलतापूर्वक कार्यान्वित किए जा सकते हैं (गुण और संबंध देखें)।

प्लैटफ़ॉर्म मनेमोनिक नाम ऑपरेंड की चौड़ाई विवरण 0 के लिए आवेदन पर
एआरएम (ARMv5T आर्किटेक्चर और बाद में)

कॉर्टेक्स-M0/M0+/M1/M23 को छोड़कर

clz[3] अग्रणी शून्यों की गणना करें 32 clz 32
एआरएम (एआरएमवी8-ए आर्किटेक्चर) clz अग्रणी शून्यों की गणना करें 32, 64 clz ऑपरेंड की चौड़ाई
एवीआर32 clz[4] अग्रणी शून्यों की गणना करें 32 clz 32
डीईसी अल्फा सीटीएलजेड[5] अग्रणी शून्यों की गणना करें 64 clz 64
सीटीटीजेड[5] अनुगामी शून्यों की गणना करें 64 ctz 64
इंटेल 80386 और बाद का संस्करण bsf[6] बिट स्कैन फॉरवर्ड 16, 32, 64 ctz अपरिभाषित; जीरो फ्लैग सेट करता है
bsr[6] बिट स्कैन रिवर्स 16, 32, 64 Log base 2 अपरिभाषित; जीरो फ्लैग सेट करता है
x86 बीएमआई1 या एबीएम का समर्थन करता है एलज़सीएनटी[7] अग्रणी शून्यों की गणना करें 16, 32, 64 clz ऑपरेंड की चौड़ाई; सेट फ्लैग लेकर चलते हैं
x86 बीएमआई1 का समर्थन करता है tzcnt[8] अनुगामी शून्यों की गणना करें 16, 32, 64 ctz ऑपरेंड की चौड़ाई; सेट फ्लैग लेकर चलते हैं
इटेनियम clz[9] अग्रणी शून्यों की गणना करें 64 clz 64
एमआईपीएस32/एमआईपीएस64 clz[10][11] वर्ड में प्रमुख शून्यों की गणना करें 32, 64 clz ऑपरेंड की चौड़ाई
clo[10][11] वर्ड में अग्रणी लोगों की गिनती करें 32, 64 clo ऑपरेंड की चौड़ाई
मोटोरोला 68020 और बाद में bfffo[12] बिट फ़ील्ड में फर्स्ट फाइंड Arbitrary Log base 2 फ़ेसट का फ़ील्ड + फ़ील्ड की चौड़ाई
पीडीपी-10 jffo यदि पहले वाला मिल जाए 36 ctz 0; कोई संचालन नहीं
पावर/पावरपीसी/पावर आईएसए cntlz/cntlzw/cntlzd[13] अग्रणी शून्यों की गणना करें 32, 64 clz ऑपरेंड की चौड़ाई
पावर आईएसए 3.0 और बाद का संस्करण cnttzw/cnttzd[14] अनुगामी शून्यों की गणना करें 32, 64 ctz ऑपरेंड की चौड़ाई
आरआईएससी-वी ("बी" एक्सटेंशन) (ड्राफ्ट) clz[15] अग्रणी शून्यों की गणना करें 32, 64 clz ऑपरेंड की चौड़ाई
ctz[15] अनुगामी शून्यों की गणना करें 32, 64 ctz ऑपरेंड की चौड़ाई
स्पार्क ओरेकल आर्किटेक्चर 2011 और बाद में एलज़सीएनटी (synonym: lzd)[16] अग्रणी शून्य गणना 64 clz 64
वैक्स एफएफएस[17] फर्स्ट सेट फाइंड 0–32 ctz ऑपरेंड की चौड़ाई; शून्य फ्लैग सेट करता है
आईबीएम जेड/आर्किटेक्चर flogr[18] सबसे बाईं ओर वाला फाइंड 64 clz 64
vclz[18] सदिश गणना अग्रणी शून्य 8, 16, 32, 64 clz ऑपरेंड की चौड़ाई
vctz[18] सदिश गणना अनुगामी शून्य 8, 16, 32, 64 ctz ऑपरेंड की चौड़ाई

कुछ अल्फ़ा प्लेटफ़ॉर्म पर सीटीएलजेड और सीटीटीजेड का सॉफ़्टवेयर में अनुकरण किया जाता है।

उपकरण और लाइब्रेरी समर्थन

कई कंपाइलर और लाइब्रेरी विक्रेता पहले सेट और/या संबंधित संचालन को खोजने के लिए कंपाइलर इंट्रिनिक्स या लाइब्रेरी फ़ंक्शंस की आपूर्ति करते हैं, जिन्हें अधिकांशतः उपरोक्त हार्डवेयर निर्देशों के संदर्भ में कार्यान्वित किया जाता है:

उपकरण/लाइब्रेरी नाम प्रकार इनपुट प्रकार टिप्पणियाँ 0 के लिए आवेदन पर
पॉज़िक्स.1 अनुपालक libc

4.3बीएसडी libc

ओएस एक्स 10.3 libc[2][19]

एफएफएस लाइब्रेरी फंक्शन आईएनटी ग्लिबैक सम्मिलित है। पॉज़िक्स पूरक लॉग बेस 2/सीएलज़ की आपूर्ति नहीं करता है। 0
फ्रीबीएसडी 5.3 libc

ओएस एक्स 10.4 libc[19]

एफएफएसl
fls
flsl		 लाइब्रेरी फंक्शन पूर्णांक,

लंबा

एफएलएस ("अंतिम सेट खोजे") गणना करता है (लॉग बेस 2) + 1। 0
फ्रीबीएसडी 7.1 libc[20] एफएफएसll
flsll		 लाइब्रेरी फंक्शन लॉन्ग लॉन्ग 0
जीसीसी 3.4.0[21][22]
क्लैंग 5.x[23][24]		 __builtin_एफएफएस[l,ll,imax]
__builtin_clz[l,ll,imax]
__builtin_ctz[l,ll,imax]
 अंतर्निहित कार्य अहस्ताक्षरित पूर्णांक,

अहस्ताक्षरित लंबा,

अहस्ताक्षरित लॉन्ग लॉन्ग,

यूइंटमैक्स_टी

जीसीसी दस्तावेज़ीकरण परिणाम को अपरिभाषित clz और 0 पर ctz मानता है। 0 (एफएफएस)
विजुअल स्टूडियो 2005 _BitScanForward[25]
_BitScanReverse[26]		 संकलक आंतरिक अहस्ताक्षरित लंबा,

अहस्ताक्षरित __int64

शून्य इनपुट इंगित करने के लिए अलग रिटर्न मान अपरिभाषित
विजुअल स्टूडियो 2008 __एलज़सीएनटी[27] कंपाइलर आंतरिक अहस्ताक्षरित लघु,

अहस्ताक्षरित पूर्णांक,

अहस्ताक्षरित __int64

बीएमआई1 या एबीएम में प्रस्तुत एलज़सीएनटी अनुदेश के लिए हार्डवेयर समर्थन पर निर्भर करता है। ऑपरेंड की चौड़ाई
विजुअल स्टूडियो 2012 _arm_clz[28] कंपाइलर आंतरिक अहस्ताक्षरित पूर्णांक ARMv5T आर्किटेक्चर और बाद में पेश किए गए clz निर्देश के लिए हार्डवेयर समर्थन पर निर्भर करता है। ?
इंटेल सी++ कंपाइलर _bit_scan_forward
_bit_scan_reverse[29][30]		 संकलक आंतरिक पूर्णांक अपरिभाषित
एनवीडिया क्यूडा[31] __clz फ़ंक्शंस 32-बिट, 64-बिट GeForce 400 सीरीज पर कम निर्देशों को संकलित करता है 32
__एफएफएस 0
एलएलवीएम एलएलवीएम.सीटीएलजेड.*
एलएलवीएम.सीटीटीजेड.*[32]		 आंतरिक 8, 16, 32, 64, 256 एलएलवीएम असेंबली भाषा ऑपरेंड की चौड़ाई, यदि दूसरा तर्क 0 है; अन्यथा अपरिभाषित
जीएचसी 7.10 (बेस 4.8), Data.Bits countLeadingZeros
countTrailingZeros		 लाइब्रेरी फंक्शन FiniteBits b => b हास्केल प्रोग्रामिंग भाषा ऑपरेंड की चौड़ाई
C++20 मानक लाइब्रेरी, हेडर में <bit>[33][34] bit_ceil bit_floor
bit_width
countl_zero countl_one
countr_zero countr_one		 लाइब्रेरी फंक्शन अचिन्हित वर्ण,

अहस्ताक्षरित लघु,

अहस्ताक्षरित पूर्णांक,

अहस्ताक्षरित लंबा,

अहस्ताक्षरित लॉन्ग लॉन्ग

गुण और संबंध

यदि बिट्स को 1 से प्रारंभ करके लेबल किया गया है (जो कि इस आलेख में प्रयुक्त परंपरा है), तो अनुगामी शून्यों की गणना करें और पता लगाएं कि पहले सेट संचालन किससे संबंधित हैं ctz(x) = ffs(x) − 1 (अतिरिक्त जब इनपुट शून्य हो)। यदि बिट्स को प्रारंभ से लेबल किया गया है 0, फिर पिछले शून्यों की गणना करें और पता लगाएं कि फर्स्ट सेट बिल्कुल समतुल्य संचालन है। दिया गया w प्रति शब्द बिट्स, log2 से आसानी से गणना की जा सकती है clz और इसके विपरीत log2(x) = w − 1 − clz(x). है जैसा कि ऊपर दिए गए उदाहरण में दिखाया गया है, पहले शून्य फाइंड, अग्रणी शून्य गिनें, और अनुगामी शून्य गिनें संचालन को इनपुट को अस्वीकार करके और पहले सेट फाइंड, अग्रणी शून्य गिनें, और अनुगामी शून्य गिनें का उपयोग करके कार्यान्वित किया जा सकता है। विपरीत भी सही है।

कुशल लॉग वाले प्लेटफ़ॉर्म पर M680002 जैसे संचालन, ctz द्वारा गणना की जा सकती है:

ctz(x) = log2(x & −x)

कहाँ & बिटवाइज़ और और को दर्शाता है −x दोनों के पूरक को दर्शाता है x. इजहार x & −x न्यूनतम-महत्वपूर्ण को छोड़कर सभी को साफ़ करता है 1 बिट, जिससे सबसे अधिक- और सबसे कम-महत्वपूर्ण 1 बिट समान हैं.

एआरएम और पावरपीसी जैसे कुशल गणना अग्रणी शून्य संचालन वाले प्लेटफार्मों पर, ffs द्वारा गणना की जा सकती है:

ffs(x) = w − clz(x & −x).

इसके विपरीत, बिना मशीनों पर log2 या clz ऑपरेटर, clz का उपयोग करके गणना की जा सकती है , यद्यपि ctz अकुशलता से प्रयुक्त होता है:

clz = w − ctz(2⌈log2(x)⌉) (जिस पर निर्भर करता है ctz लौट रहा हूँ w शून्य इनपुट के लिए)

स्पार्क जैसे कुशल हथौड़ा चलाना वजन (जनसंख्या गणना) संचालन वाले प्लेटफार्मों पर POPC [35][36] या ब्लैकफ़िन का ONES,[37] वहाँ है:

ctz(x) = popcount((x & −x) − 1),[38][39]या ctz(x) = popcount(~(x | −x)),
ffs(x) = popcount(x ^ ~−x)[35]: clz = 32 − popcount(2⌈log2(x)⌉ − 1)

जहाँ ^ बिटवाइज़ एक्सक्लूसिव-OR को दर्शाता है, | बिटवाइज़ OR और को दर्शाता है ~ बिटवाइज़ नकार को दर्शाता है।

उलटा समस्या (दिया गया है i, उत्पादन करें x ऐसा है कि ctz(x) = i) की गणना बाईं-शिफ्ट (1 << i) के साथ की जा सकती है .

फर्स्ट सेट फाइंड और संबंधित संचालन को छोर से प्रारंभ करके और शब्द तक आगे बढ़ते हुए सीधे विधि से इच्छानुसार विधि से बड़े बिट सरणी तक बढ़ाया जा सकता है जो कि पूर्ण-शून्य नहीं है (के लिए) ffs, ctz, clz) या सभी-एक नहीं (के लिए)। ffz, clo, cto) का सामना करना पड़ता है। ट्री डेटा संरचना जो पुनरावर्ती रूप से बिटमैप का उपयोग करके ट्रैक करती है कि कौन से शब्द गैर-शून्य हैं, इसे तेज कर सकते हैं।

सॉफ़्टवेयर अनुकरण

1980 के दशक के उत्तरार्ध के अधिकांश सीपीयू में एफएफएस या समकक्ष के लिए बिट ऑपरेटर होते हैं, किन्तु एआरएम-एमएक्स श्रृंखला जैसे कुछ आधुनिक सीपीयू में ऐसा नहीं होता है। इस प्रकार एफएफएस, सीएलजेड और सीटीजेड के लिए हार्डवेयर ऑपरेटरों के बदले में, सॉफ्टवेयर उन्हें शिफ्ट, पूर्णांक अंकगणित और बिटवाइज़ ऑपरेटरों के साथ अनुकरण कर सकता है। सीपीयू की आर्किटेक्चर और कुछ सीमा तक प्रोग्रामिंग भाषा के शब्दार्थ और कंपाइलर कोड पीढ़ी की गुणवत्ता के आधार पर कई दृष्टिकोण हैं। दृष्टिकोणों को शिथिल रूप से रैखिक खोज के रूप में वर्णित किया जा सकता है, द्विआधारी खोज, खोज+ टेबल लुकअप, डी ब्रुइज़न गुणन, फ़्लोटिंग पॉइंट रूपांतरण/प्रतिपादक अर्क, और बिट ऑपरेटर (शाखा रहित) विधि. निष्पादन समय और भंडारण स्थान के साथ-साथ पोर्टेबिलिटी और दक्षता के बीच भी विरोधाभास है।

सॉफ़्टवेयर अनुकरण सामान्यतः नियतात्मक होते हैं। वे सभी इनपुट मानों के लिए परिभाषित परिणाम वापस करते हैं; विशेष रूप से, सभी शून्य बिट्स के इनपुट का परिणाम सामान्यतः एफएफएस के लिए 0 होता है, और अन्य परिचालनों के लिए ऑपरेंड की बिट लंबाई होती है।

यदि किसी के पास हार्डवेयर सीएलजेड या समकक्ष है, जिससे सीटीजेड को बिट ऑपरेशंस के साथ कुशलतापूर्वक गणना की जा सकती है, किन्तु इसका विपरीत सच नहीं है: हार्डवेयर ऑपरेटर की अनुपस्थिति में सीएलजेड गणना करने में कुशल नहीं है।

2n

प्रोग्राम 2⌈log2(x)⌉ (दो की निकटतम घात तक पूर्णांकित करें) शिफ्ट और बिटवाइज़ ओआरएस का उपयोग करके [40] इस 32-बिट उदाहरण की तरह गणना करना कुशल नहीं है और यदि हमारे पास 64-बिट या 128-बिट ऑपरेंड है तो यह और भी अधिक अक्षम है:

function pow2(x):                                                                                          
    if x = 0 return invalid  // invalid is implementation defined (not in [0,63])
    x ← x - 1                                                                                                 
    for each y in {1, 2, 4, 8, 16}: x ← x | (x >> y)                                              
    return x + 1

एफएफएस

चूँकि ffs = ctz + 1 (पॉज़िक्स) या ffs = ctz (अन्य कार्यान्वयन), ctz के लिए प्रयुक्त एल्गोरिदम का उपयोग किया जा सकता है, जिसके परिणाम में 1 जोड़ने का संभावित अंतिम चरण होता है, और इनपुट के लिए ऑपरेंड लंबाई के अतिरिक्त 0 वापस है। सभी शून्य बिट्स.

सीटीजेड

कैनोनिकल एल्गोरिदम एलएसबी से प्रारंभ होने वाले शून्यों की गणना करने वाला लूप है जब तक कि 1-बिट का सामना न हो जाए:

function ctz1 (x)                                                                                           
    if x = 0 return w                                                                                
    t ← 1                                                                                                
    r ← 0                                                                                                   
    while (x & t) = 0                                                                                      
        t ← t << 1                                                                                                
        r ← r + 1                                                                                        
    return r

यह एल्गोरिदम O(n) समय और संचालन निष्पादित करता है, और बड़ी संख्या में सशर्त शाखाओं के कारण व्यवहार में अव्यावहारिक है। एक लुकअप तालिका अधिकांश शाखाओं को समाप्त कर सकती है:

table[0..2n-1] = ctz(i) for i in 0..2n-1                                                                   
function ctz2 (x)                                                             
    if x = 0 return w
    r ← 0                                                                                                                                                       
    loop                                                                       
        if (x & (2n-1)) ≠ 0
            return r + table[x & (2n-1)]                                                         
        x ← x >> n                                                                       
        r ← r + n

पैरामीटर n निश्चित है (सामान्यतः 8) और समय-स्थान ट्रेडऑफ़ का प्रतिनिधित्व करता है। लूप पूरी तरह से लूप भी हो सकता है। किन्तु रैखिक लुकअप के रूप में, ऑपरेंड में बिट्स की संख्या में यह दृष्टिकोण अभी भी O(n) है। एक बाइनरी खोज कार्यान्वयन संचालन और शाखाओं की लघुगणकीय संख्या लेता है, जैसा कि इस 32-बिट संस्करण में है:[41][42] इस एल्गोरिदम को तालिका द्वारा भी सहायता प्रदान की जा सकती है, जो सूचकांक के रूप में सामने आए पहले गैर-शून्य बाइट का उपयोग करके 256 प्रविष्टि लुकअप तालिका के साथ नीचे के तीन यदि कथनों को प्रतिस्थापित करती है।

function ctz3 (x)                                               
    if x = 0 return 32                                                       
    n ← 0                                               
    if (x & 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16                                      
    if (x & 0x000000FF) = 0: n ← n +  8, x ← x >>  8                                             
    if (x & 0x0000000F) = 0: n ← n +  4, x ← x >>  4                                                     
    if (x & 0x00000003) = 0: n ← n +  2, x ← x >>  2                                              
    if (x & 0x00000001) = 0: n ← n +  1     
    return n

यदि हार्डवेयर में clz ऑपरेटर है, तो ctz की गणना करने का सबसे कुशल विधि इस प्रकार है:

function ctz4 (x)                                                            
    x &= -x                              
    return w - (clz(x) + 1)

32-बिट सीटीज़ के लिए एल्गोरिदम न्यूनतम सही हैश फ़ंक्शन बनाने के लिए डी ब्रुइज़न अनुक्रमों का उपयोग करता है जो सभी शाखाओं को समाप्त करता है।[43][44] यह एल्गोरिदम मानता है कि गुणन के परिणाम को 32 बिट तक छोटा कर दिया गया है।

for i from 0 to 31: table[ ( 0x077CB531 * ( 1 << i ) ) >> 27 ] ← i  // table [0..31] initialized                        
function ctz5 (x)                                                                                            
    return table[((x & -x) * 0x077CB531) >> 27]

अभिव्यक्ति (x & -x) फिर से सबसे कम महत्वपूर्ण 1 बिट को अलग करती है। तब केवल 32 संभावित शब्द हैं, जिन्हें अहस्ताक्षरित गुणन और हैश को तालिका में सही स्थिति में स्थानांतरित किया जाता है। (यह एल्गोरिदम शून्य इनपुट को संभाल नहीं पाता है।)

कल्ज़

कैनोनिकल एल्गोरिदम एमएसबी से प्रारंभ करके समय में बिट की जांच करता है जब तक कि गैर-शून्य बिट नहीं मिल जाता है, जैसा कि इस उदाहरण में दिखाया गया है। यह O(n) समय में निष्पादित होता है जहां n ऑपरेंड की बिट-लंबाई है, और सामान्य उपयोग के लिए व्यावहारिक एल्गोरिदम नहीं है।

function clz1 (x)                                            
    if x = 0 return w                                        
    t ← 1 << (w - 1)                                      
    r ← 0                                                
    while (x & t) = 0                                    
        t ← t >> 1                                       
        r ← r + 1                                         
    return r

पिछले लूपिंग दृष्टिकोण में सुधार समय में आठ बिट्स की जांच करता है और फिर 256 (28) का उपयोग करता है) पहले गैर-शून्य बाइट के लिए प्रविष्टि लुकअप तालिका चूँकि, यह दृष्टिकोण निष्पादन समय में अभी भी O(n) है।

function clz2 (x)
    if x = 0 return w
    t ← 0xff << (w - 8)
    r ← 0
    while (x & t) = 0
        t ← t >> 8
        r ← r + 8
    return r + table[x >> (w - 8 - r)]

बाइनरी खोज निष्पादन समय को घटाकर O2n लॉग कर सकती है:

function clz3 (x)
    if x = 0 return 32
    n ← 0
    if (x & 0xFFFF0000) = 0: n ← n + 16, x ← x << 16                                                       
    if (x & 0xFF000000) = 0: n ← n +  8, x ← x <<  8                                                         
    if (x & 0xF0000000) = 0: n ← n +  4, x ← x <<  4                                                        
    if (x & 0xC0000000) = 0: n ← n +  2, x ← x <<  2                                                           
    if (x & 0x80000000) = 0: n ← n +  1
    return n

सीएलज़ को अनुकरण करने के लिए सबसे तेज़ पोर्टेबल दृष्टिकोण बाइनरी सर्च और टेबल लुकअप का संयोजन है: 8-बिट टेबल लुकअप (2)8=256 1-बाइट प्रविष्टियाँ) बाइनरी खोज में नीचे की 3 शाखाओं को प्रतिस्थापित कर सकती हैं। 64-बिट ऑपरेंड को अतिरिक्त शाखा की आवश्यकता होती है। बड़ी चौड़ाई वाले लुकअप का उपयोग किया जा सकता है किन्तु अधिकतम व्यावहारिक तालिका का आकार आधुनिक प्रोसेसर पर L1 डेटा कैश के आकार तक सीमित है, जो कई लोगों के लिए 32 KB है। किसी शाखा को सहेजना L1 कैश मिस की विलंबता से ऑफसेट से कहीं अधिक है। CTZ के लिए डी ब्रुइज़न गुणन के समान एल्गोरिथ्म CLZ के लिए कार्य करता है, किन्तु सबसे महत्वपूर्ण बिट को अलग करने के अतिरिक्त, यह फॉर्म 2n−1 के निकटतम पूर्णांक तक पूर्णांक बनाता है शिफ्ट और बिटवाइज़ ORs का उपयोग करता है:[45]

table[0..31] = {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
                8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31}
function clz4 (x)
    for each y in {1, 2, 4, 8, 16}: x ← x | (x >> y)
    return table[((x * 0x07C4ACDD) >> 27) % 32]

गहरे पाइपलाइन वाले प्रोसेसर के लिए, जैसे प्रेस्कॉट और बाद के इंटेल प्रोसेसर, गलत पूर्वानुमानित शाखाओं के लिए पाइपलाइन फ्लश से बचने के लिए शाखाओं को बिटवाइज़ और और OR ऑपरेटरों (तथापि कई और निर्देशों की आवश्यकता होती है) द्वारा प्रतिस्थापित करना तेज़ हो सकता है (और इस प्रकार की शाखाएं हैं) स्वाभाविक रूप से अप्रत्याशित):

function clz5 (x)                                                                                           
   r = (x > 0xFFFF) << 4; x >>= r;                                                                              
   q = (x > 0xFF  ) << 3; x >>= q; r |= q;                                                                
   q = (x > 0xF   ) << 2; x >>= q; r |= q;                                                                   
   q = (x > 0x3   ) << 1; x >>= q; r |= q;                                                                  
                                   r |= (x >> 1);                                                
   return r;

उन प्लेटफार्मों पर जो पूर्णांकों को फ़्लोटिंग पॉइंट में हार्डवेयर रूपांतरण प्रदान करते हैं, अग्रणी शून्य की गणना की गणना करने के लिए घातांक फ़ील्ड को स्थिरांक से निकाला और घटाया जा सकता है। पूर्णांकन त्रुटियों को ध्यान में रखते हुए सुधार की आवश्यकता है।[41][46] फ़्लोटिंग पॉइंट रूपांतरण में पर्याप्त विलंबता हो सकती है। यह विधि अत्यधिक गैर-पोर्टेबल है और सामान्यतः इसकी अनुशंसा नहीं की जाती है। 

int x; 
int r;
union { unsigned int u[2]; double d; } t;

t.u[LE] = 0x43300000;  // LE is 1 for little-endian
t.u[!LE] = x;
t.d -= 4503599627370496.0;
r = (t.u[LE] >> 20) - 0x3FF;  // log2
r++;  // CLZ

अनुप्रयोग

सामान्यीकरण को कुशलतापूर्वक प्रयुक्त करने के लिए गणना अग्रणी शून्य (सीएलजेड) संचालन का उपयोग किया जा सकता है, जो पूर्णांक को m× 2e के रूप में एन्कोड करता है, जहां m का ज्ञात स्थिति में सबसे महत्वपूर्ण बिट है (जैसे कि उच्चतम स्थिति)। इसके बदले में इसका उपयोग न्यूटन-रेफसन डिवीजन को प्रयुक्त करने, सॉफ्टवेयर और अन्य अनुप्रयोगों में पूर्णांक से फ़्लोटिंग पॉइंट रूपांतरण करने के लिए किया जा सकता है।[41][47]

अग्रणी शून्यों की गणना करें (clz) का उपयोग पहचान के माध्यम से 32-बिट विधेय x = y (यदि सत्य है तो शून्य, यदि गलत है तो एक) की गणना करने के लिए किया जा सकता है clz(x − y) >> 5, जहां >> अहस्ताक्षरित दायां बदलाव है।[48] इसका उपयोग अधिक परिष्कृत बिट संचालन करने के लिए किया जा सकता है जैसे n 1 बिट्स की पहली स्ट्रिंग खोजना होता है।[49] इस प्रकार clz(x − y)1 << (16 − clz(x − 1)/2) न्यूटन की विधि का उपयोग करके 32-बिट पूर्णांक के वर्गमूल की गणना के लिए प्रभावी प्रारंभिक अनुमान है।[50] सीएलजेड कुशलतापूर्वक शून्य दमन को कार्यान्वित कर सकता है, तेज़ डेटा संपीड़न तकनीक जो पूर्णांक को गैर-शून्य बाइट्स के साथ अग्रणी शून्य बाइट्स की संख्या के रूप में एन्कोड करती है।[51] यह समान वितरण (असतत) पूर्णांकों का सीएलजेड लेकर कुशलतापूर्वक घातीय वितरण पूर्णांक उत्पन्न कर सकता है।[41]

लॉग बेस 2 का उपयोग यह अनुमान लगाने के लिए किया जा सकता है कि गुणन अतिप्रवाह होगा या नहीं ⌈log2(xy)⌉ ≤ ⌈log2(x)⌉ + ⌈log2(y)⌉.[52]

गोस्पर के लूप-डिटेक्शन एल्गोरिदम को प्रयुक्त करने के लिए अग्रणी शून्यों की गणना और अनुगामी शून्यों की गणना का साथ उपयोग किया जा सकता है,[53] जो सीमित संसाधनों का उपयोग करके परिमित सीमा के किसी फ़ंक्शन की अवधि ज्ञात कर सकता है।[42]

बाइनरी जीसीडी एल्गोरिदम पिछले शून्य को हटाने में कई चक्र खर्च करता है; इसे बदलाव के बाद शून्य के पीछे की गणना (ctz) से बदला जा सकता है। समान लूप हेलस्टोन अनुक्रम की गणना में दिखाई देता है।

प्राथमिकता को प्रयुक्त करने के लिए बिट सरणी का उपयोग किया जा सकता है। इस संदर्भ में, फाइंड फर्स्ट सेट (एफएफएस) पॉप या पुल उच्चतम प्राथमिकता वाले तत्व संचालन को कुशलतापूर्वक प्रयुक्त करने में उपयोगी है। लिनक्स कर्नेल रीयल-टाइम शेड्यूलर आंतरिक रूप से sched_find_first_bit() उपयोग करता है।[54]

काउंट ट्रेलिंग शून्य संचालन हनोई टॉवर समस्या का सरल इष्टतम समाधान देता है: डिस्क को शून्य से क्रमांकित किया जाता है, और गति k पर, डिस्क संख्या ctz(k) को दाईं ओर न्यूनतम संभव दूरी पर ले जाया जाता है (वापस चारों ओर चक्कर लगाते हुए) आवश्यकतानुसार छोड़ दिया गया)। यह सही शब्द लेकर और चरण k पर बिट ctz(k) फ़्लिप करके ग्रे कोड भी उत्पन्न कर सकता है।[42]

यह भी देखें

टिप्पणियाँ

  1. ↑ अहस्ताक्षरित मशीन शब्द के अतिरिक्त अन्य पर बिट संचालन का उपयोग करने से अपरिभाषित परिणाम मिल सकते हैं.
  2. ↑ इन चार ऑपरेशनों में (बहुत कम सामान्य) अस्वीकृत संस्करण भी हैं:
    • पहला शून्य खोजें' (ffz), जो कम से कम महत्वपूर्ण शून्य बिट के सूचकांक की पहचान करता है;
    • अनुगामी बिट्स की गिनती करें, जो कम से कम महत्वपूर्ण शून्य बिट के बाद एक बिट्स की संख्या की गणना करता है।
    • अग्रणी बिट्स की गिनती करें, जो सबसे महत्वपूर्ण शून्य बिट से पहले के एक बिट्स की संख्या की गणना करता है;
    • सबसे महत्वपूर्ण शून्य बिट का सूचकांक खोजे, जो बाइनरी लॉगरिदम का उलटा संस्करण है.

संदर्भ

  1. ↑ Anderson. Find the log base 2 of an integer with the MSB N set in O(N) operations (the obvious way).
  2. ↑ 2.0 2.1 "FFS(3)". Linux Programmer's Manual. The Linux Kernel Archives. Retrieved 2012-01-02.
  3. ↑ "ARM Instruction Reference > ARM general data processing instructions > CLZ". ARM Developer Suite Assembler Guide. ARM. Retrieved 2012-01-03.
  4. ↑ "AVR32 Architecture Document" (PDF) (CORP072610 ed.). Atmel Corporation. 2011. 32000D–04/201. Archived from the original (PDF) on 2017-10-25. Retrieved 2016-10-22.
  5. ↑ 5.0 5.1 Alpha Architecture Reference Manual (PDF). Compaq. 2002. pp. 4-32, 4-34.
  6. ↑ 6.0 6.1 Intel 64 and IA-32 Architectures Software Developer Manual. Vol. 2A. Intel. pp. 3-92–3-97. Order number 325383.
  7. ↑ AMD64 Architecture Programmer's Manual Volume 3: General Purpose and System Instructions (PDF). Vol. 3. Advanced Micro Devices (AMD). 2011. pp. 204–205. Publication No. 24594.
  8. ↑ "AMD64 Architecture Programmer's Manual, Volume 3: General-Purpose and System Instructions" (PDF). AMD64 Technology (Version 3.28 ed.). Advanced Micro Devices (AMD). September 2019 [2013]. Publication No. 24594. Archived (PDF) from the original on 2019-09-30. Retrieved 2014-01-02.
  9. ↑ Intel Itanium Architecture Software Developer's Manual. Volume 3: Intel Itanium Instruction Set. Vol. 3. Intel. 2010. pp. 3:38. Archived from the original on 2019-06-26.
  10. ↑ 10.0 10.1 MIPS Architecture For Programmers. Volume II-A: The MIPS32 Instruction Set (Revision 3.02 ed.). MIPS Technologies. 2011. pp. 101–102.
  11. ↑ 11.0 11.1 MIPS Architecture For Programmers. Volume II-A: The MIPS64 Instruction Set (Revision 3.02 ed.). MIPS Technologies. 2011. pp. 105, 107, 122, 123.
  12. ↑ M68000 Family Programmer's Reference Manual (Includes CPU32 Instructions) (PDF) (revision 1 ed.). Motorola. 1992. pp. 4-43–4-45. M68000PRM/AD. Archived from the original (PDF) on 2019-12-08.
  13. ↑ Frey, Brad. "Chapter 3.3.11 Fixed-Point Logical Instructions". PowerPC Architecture Book (Version 2.02 ed.). IBM. p. 70.
  14. ↑ "Chapter 3.3.13 Fixed-Point Logical Instructions - Chapter 3.3.13.1 64-bit Fixed-Point Logical Instructions". Power ISA Version 3.0B. IBM. pp. 95, 98.
  15. ↑ 15.0 15.1 Wolf, Clifford (2019-03-22). "RISC-V "B" Bit Manipulation Extension for RISC-V" (PDF). Github (Draft) (v0.37 ed.). Retrieved 2020-01-09.
  16. ↑ Oracle SPARC Architecture 2011. Oracle. 2011.
  17. ↑ VAX Architecture Reference Manual (PDF). Digital Equipment Corporation (DEC). 1987. pp. 70–71. Archived (PDF) from the original on 2019-09-29. Retrieved 2020-01-09.
  18. ↑ 18.0 18.1 18.2 "Chapter 22. Vector Integer Instructions". IBM z/Architecture Principles of Operation (PDF) (Eleventh ed.). IBM. March 2015. pp. 7-219–22-10. SA22-7832-10. Retrieved 2020-01-10.
  19. ↑ 19.0 19.1 "FFS(3)". Mac OS X Developer Library. Apple, Inc. 1994-04-19. Retrieved 2012-01-04.
  20. ↑ "FFS(3)". FreeBSD Library Functions Manual. The FreeBSD Project. Retrieved 2012-01-04.
  21. ↑ "Other built-in functions provided by GCC". Using the GNU Compiler Collection (GCC). Free Software Foundation, Inc. Retrieved 2015-11-14.
  22. ↑ "GCC 3.4.0 ChangeLog". GCC 3.4.0. Free Software Foundation, Inc. Retrieved 2015-11-14.
  23. ↑ "Clang Language Extensions - chapter Builtin Functions". The Clang Team. Retrieved 2017-04-09. Clang supports a number of builtin library functions with the same syntax as GCC
  24. ↑ "Source code of Clang". LLVM Team, University of Illinois at Urbana-Champaign. Retrieved 2017-04-09.
  25. ↑ "_BitScanForward, _BitScanForward64". Visual Studio 2008: Visual C++: Compiler Intrinsics. Microsoft. Retrieved 2018-05-21.
  26. ↑ "_BitScanReverse, _BitScanReverse64". Visual Studio 2008: Visual C++: Compiler Intrinsics. Microsoft. Retrieved 2018-05-21.
  27. ↑ "__lzcnt16, __lzcnt, __lzcnt64". Visual Studio 2008: Visual C++: Compiler Intrinsics. Microsoft. Retrieved 2012-01-03.
  28. ↑ "ARM intrinsics". Visual Studio 2012: Visual C++: Compiler Intrinsics. Microsoft. Retrieved 2022-05-09.
  29. ↑ "Intel Intrinsics Guide". Intel. Retrieved 2020-04-03.
  30. ↑ Intel C++ Compiler for Linux Intrinsics Reference. Intel. 2006. p. 21.
  31. ↑ NVIDIA CUDA Programming Guide (PDF) (Version 3.0 ed.). NVIDIA. 2010. p. 92.
  32. ↑ "'llvm.ctlz.*' Intrinsic, 'llvm.cttz.*' Intrinsic". LLVM Language Reference Manual. The LLVM Compiler Infrastructure. Retrieved 2016-02-23.
  33. ↑ Smith, Richard (2020-04-01). N4861 Working Draft, Standard for Programming Language C++ (PDF). ISO/IEC. pp. 1150–1153. Retrieved 25 May 2020.
  34. ↑ "Standard library header <bit>". cppreference.com. Retrieved 25 May 2020.
  35. ↑ 35.0 35.1 SPARC International, Inc. (1992). "A.41: Population Count. Programming Note" (PDF). The SPARC architecture manual: version 8 (Version 8 ed.). Englewood Cliffs, New Jersey, USA: Prentice Hall. pp. 231. ISBN 978-0-13-825001-0.
  36. ↑ Warren, Jr., Henry S. (2013) [2002]. Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.
  37. ↑ Blackfin Instruction Set Reference (Preliminary ed.). Analog Devices. 2001. pp. 8–24. Part Number 82-000410-14.
  38. ↑ Dietz, Henry Gordon. "The Aggregate Magic Algorithms". University of Kentucky. Archived from the original on 2019-10-31.
  39. ↑ Isenberg, Gerd (2019-11-03) [2012]. "BitScanProtected". Chess Programming Wiki (CPW). Archived from the original on 2020-01-09. Retrieved 2020-01-09.
  40. ↑ Anderson. Round up to the next highest power of 2.
  41. ↑ 41.0 41.1 41.2 41.3 Warren. Chapter 5-3: Counting Leading 0's.
  42. ↑ 42.0 42.1 42.2 Warren. Chapter 5-4: Counting Trailing 0's.
  43. ↑ Leiserson, Charles E.; Prokop, Harald; Randall, Keith H. (1998-07-07). "Using de Bruijn Sequences to Index a 1 in a Computer Word" (PDF). MIT Laboratory for Computer Science, Cambridge, MA, USA. Archived (PDF) from the original on 2020-01-09. Retrieved 2020-01-09.
  44. ↑ Busch, Philip (2009-03-01) [2009-02-21]. "Computing Trailing Zeros HOWTO" (PDF). Archived (PDF) from the original on 2016-08-01. Retrieved 2020-01-09.
  45. ↑ Anderson. Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup.
  46. ↑ Anderson. Find the integer log base 2 of an integer with a 64-bit IEEE float.
  47. ↑ Sloss, Andrew N.; Symes, Dominic; Wright, Chris (2004). ARM system developer's guide designing and optimizing system software (1 ed.). San Francisco, CA, USA: Morgan Kaufmann. pp. 212–213. ISBN 978-1-55860-874-0.
  48. ↑ Warren. Chapter 2-11: Comparison Predicates.
  49. ↑ Warren. Chapter 6-2: Find First String of 1-Bits of a Given Length.
  50. ↑ Warren. Chapter 11-1: Integer Square Root.
  51. ↑ Schlegel, Benjamin; Gemulla, Rainer; Lehner, Wolfgang [in Deutsch] (June 2010). Fast integer compression using SIMD instructions. pp. 34–40. CiteSeerX 10.1.1.230.6379. doi:10.1145/1869389.1869394. ISBN 978-1-45030189-3. {{cite book}}: |journal= ignored (help)
  52. ↑ Warren. Chapter 2-12: Overflow Detection.
  53. ↑ Gosper, Bill (April 1995) [1972-02-29]. Baker, Henry Givens Jr. (ed.). "Loop detector". HAKMEM (retyped & converted ed.). Cambridge, Massachusetts, USA: Artificial Intelligence Laboratory, Massachusetts Institute of Technology (MIT). AI Memo 239 Item 132. Archived from the original on 2019-10-08. Retrieved 2020-01-09.
  54. ↑ Aas, Josh (2005-02-17). Understanding the Linux 2.6.8.1 CPU Scheduler (PDF). Silicon Graphics, Inc. (SGI). p. 19. Archived (PDF) from the original on 2017-05-19. Retrieved 2020-01-09.

अग्रिम पठन

बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=फाइंड_फर्स्ट_सेट&oldid=223951’