फाइंड फर्स्ट सेट

From Vigyanwiki

कंप्यूटर सॉफ़्टवेयर और हार्डवेयर में, फर्स्ट सेट (एफएफएस) फाइंड बिट संचालन है, जिसे मशीन शब्द (कंप्यूटर आर्किटेक्चर)[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’