हैमिंग वेट: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Number of nonzero symbols in a string}} {{more citations needed|date=January 2009}} {{Use dmy dates|date=May 2019|cs1-dates=y}} एक स्ट्रि...")
 
No edit summary
Line 1: Line 1:
{{Short description|Number of nonzero symbols in a string}}
{{Short description|Number of nonzero symbols in a string}}
{{more citations needed|date=January 2009}}
एक स्ट्रिंग का हैमिंग वजन (कंप्यूटर विज्ञान) उन प्रतीकों की संख्या है जो प्रयुक्त [[वर्णमाला]] के शून्य-प्रतीक से भिन्न होते हैं। इस प्रकार यह समान लंबाई की पूर्ण-शून्य स्ट्रिंग से [[हैमिंग दूरी]] के बराबर है। सबसे विशिष्ट मामले के लिए, [[ अंश |अंश]] ्स की स्ट्रिंग, यह स्ट्रिंग में 1 की संख्या है, या किसी दिए गए नंबर की [[बाइनरी अंक प्रणाली]] का [[अंक योग]] और टैक्सीकैब ज्यामिति|''ℓ''₁ बिट वेक्टर का मानदंड . इस द्विआधारी मामले में, इसे जनसंख्या गणना भी कहा जाता है,<ref name="Warren_2013"/>पॉपकाउंट, बग़ल में योग,<ref name="Knuth_2009"/>या बिट योग.<ref name="HP-16C_1982"/>
{{Use dmy dates|date=May 2019|cs1-dates=y}}
एक स्ट्रिंग का हैमिंग वजन (कंप्यूटर विज्ञान) उन प्रतीकों की संख्या है जो प्रयुक्त [[वर्णमाला]] के शून्य-प्रतीक से भिन्न होते हैं। इस प्रकार यह समान लंबाई की पूर्ण-शून्य स्ट्रिंग से [[हैमिंग दूरी]] के बराबर है। सबसे विशिष्ट मामले के लिए, [[ अंश ]]्स की एक स्ट्रिंग, यह स्ट्रिंग में 1 की संख्या है, या किसी दिए गए नंबर की [[बाइनरी अंक प्रणाली]] का [[अंक योग]] और टैक्सीकैब ज्यामिति|''ℓ''₁ बिट वेक्टर का मानदंड . इस द्विआधारी मामले में, इसे जनसंख्या गणना भी कहा जाता है,<ref name="Warren_2013"/>पॉपकाउंट, बग़ल में योग,<ref name="Knuth_2009"/>या बिट योग.<ref name="HP-16C_1982"/>
   
   
{|class="wikitable" align="right"
{|class="wikitable" align="right"
Line 39: Line 37:


== इतिहास और उपयोग ==
== इतिहास और उपयोग ==
हैमिंग वेट का नाम [[रिचर्ड हैमिंग]] के नाम पर रखा गया है, हालांकि उन्होंने इस धारणा की उत्पत्ति नहीं की थी।<ref name="Thompson_1983"/>बाइनरी संख्याओं के हैमिंग वेट का उपयोग 1899 में जेम्स व्हिटब्रेड ली ग्लैशर द्वारा पास्कल के त्रिकोण की एक पंक्ति में गोल्ड के अनुक्रम के लिए एक सूत्र देने के लिए किया गया था।<ref name="Glaisher_1899"/>इरविंग एस. रीड ने 1954 में बाइनरी मामले में हैमिंग वजन के बराबर एक अवधारणा पेश की।<ref name="Reed_1954"/>
हैमिंग वेट का नाम [[रिचर्ड हैमिंग]] के नाम पर रखा गया है, हालांकि उन्होंने इस धारणा की उत्पत्ति नहीं की थी।<ref name="Thompson_1983"/>बाइनरी संख्याओं के हैमिंग वेट का उपयोग 1899 में जेम्स व्हिटब्रेड ली ग्लैशर द्वारा पास्कल के त्रिकोण की पंक्ति में गोल्ड के अनुक्रम के लिए सूत्र देने के लिए किया गया था।<ref name="Glaisher_1899"/>इरविंग एस. रीड ने 1954 में बाइनरी मामले में हैमिंग वजन के बराबर अवधारणा पेश की।<ref name="Reed_1954"/>


हैमिंग वेट का उपयोग [[सूचना सिद्धांत]], [[कोडिंग सिद्धांत]] और [[क्रिप्टोग्राफी]] सहित कई विषयों में किया जाता है। हैमिंग वज़न के अनुप्रयोगों के उदाहरणों में शामिल हैं:
हैमिंग वेट का उपयोग [[सूचना सिद्धांत]], [[कोडिंग सिद्धांत]] और [[क्रिप्टोग्राफी]] सहित कई विषयों में किया जाता है। हैमिंग वज़न के अनुप्रयोगों के उदाहरणों में शामिल हैं:
* वर्ग द्वारा मॉड्यूलर घातांक में, एक घातांक ई के लिए आवश्यक मॉड्यूलर गुणन की संख्या लॉग है<sub>2</sub> ई + वजन(ई)। यही कारण है कि [[आरएसए (एल्गोरिदम)]] में प्रयुक्त सार्वजनिक कुंजी मान ई को आम तौर पर कम हैमिंग वजन की संख्या के रूप में चुना जाता है।<ref name="CLNZ"/>* हैमिंग वजन [[कॉर्ड (वितरित हैश तालिका)]] में नोड्स के बीच पथ की लंबाई निर्धारित करता है।<ref name="Stoica_2003"/>* बायोमेट्रिक डेटाबेस में [[आईरिसकोड]] लुकअप आमतौर पर प्रत्येक संग्रहीत रिकॉर्ड के लिए हैमिंग दूरी की गणना करके कार्यान्वित किया जाता है।
* वर्ग द्वारा मॉड्यूलर घातांक में, घातांक ई के लिए आवश्यक मॉड्यूलर गुणन की संख्या लॉग है<sub>2</sub> ई + वजन(ई)। यही कारण है कि [[आरएसए (एल्गोरिदम)]] में प्रयुक्त सार्वजनिक कुंजी मान ई को आम तौर पर कम हैमिंग वजन की संख्या के रूप में चुना जाता है।<ref name="CLNZ"/>* हैमिंग वजन [[कॉर्ड (वितरित हैश तालिका)]] में नोड्स के बीच पथ की लंबाई निर्धारित करता है।<ref name="Stoica_2003"/>* बायोमेट्रिक डेटाबेस में [[आईरिसकोड]] लुकअप आमतौर पर प्रत्येक संग्रहीत रिकॉर्ड के लिए हैमिंग दूरी की गणना करके कार्यान्वित किया जाता है।
* [[बिटबोर्ड]] प्रतिनिधित्व का उपयोग करने वाले [[कंप्यूटर शतरंज]] कार्यक्रमों में, बिटबोर्ड का हैमिंग वजन खेल में शेष दिए गए प्रकार के टुकड़ों की संख्या, या एक खिलाड़ी के टुकड़ों द्वारा नियंत्रित बोर्ड के वर्गों की संख्या देता है, और इसलिए यह एक महत्वपूर्ण योगदान है किसी पद के मूल्य के लिए शब्द।
* [[बिटबोर्ड]] प्रतिनिधित्व का उपयोग करने वाले [[कंप्यूटर शतरंज]] कार्यक्रमों में, बिटबोर्ड का हैमिंग वजन खेल में शेष दिए गए प्रकार के टुकड़ों की संख्या, या खिलाड़ी के टुकड़ों द्वारा नियंत्रित बोर्ड के वर्गों की संख्या देता है, और इसलिए यह महत्वपूर्ण योगदान है किसी पद के मूल्य के लिए शब्द।
* हैमिंग वेट का उपयोग पहचान एफएफएस (एक्स) = पॉप (एक्स ^ (एक्स - 1)) का उपयोग करके पहले सेट को कुशलतापूर्वक खोजने के लिए किया जा सकता है। यह [[SPARC]] जैसे प्लेटफ़ॉर्म पर उपयोगी है जिसमें हार्डवेयर हैमिंग वेट निर्देश हैं लेकिन कोई हार्डवेयर पहले सेट निर्देश नहीं ढूंढता है।<ref name="SPARC_1992"/><ref name="Warren_2013"/>* हैमिंग वेट ऑपरेशन की व्याख्या यूनरी अंक प्रणाली से [[बाइनरी संख्या]]ओं में रूपांतरण के रूप में की जा सकती है।<ref name="Blaxell_1978"/>* [[बिट सरणी]] और [[ तरंगिका वृक्ष ]] जैसी कुछ [[संक्षिप्त डेटा संरचना]]ओं के कार्यान्वयन में।
* हैमिंग वेट का उपयोग पहचान एफएफएस (एक्स) = पॉप (एक्स ^ (एक्स - 1)) का उपयोग करके पहले सेट को कुशलतापूर्वक खोजने के लिए किया जा सकता है। यह [[SPARC]] जैसे प्लेटफ़ॉर्म पर उपयोगी है जिसमें हार्डवेयर हैमिंग वेट निर्देश हैं लेकिन कोई हार्डवेयर पहले सेट निर्देश नहीं ढूंढता है।<ref name="SPARC_1992"/><ref name="Warren_2013"/>* हैमिंग वेट ऑपरेशन की व्याख्या यूनरी अंक प्रणाली से [[बाइनरी संख्या]]ओं में रूपांतरण के रूप में की जा सकती है।<ref name="Blaxell_1978"/>* [[बिट सरणी]] और [[ तरंगिका वृक्ष |तरंगिका वृक्ष]] जैसी कुछ [[संक्षिप्त डेटा संरचना]]ओं के कार्यान्वयन में।


== कुशल कार्यान्वयन ==
== कुशल कार्यान्वयन ==
Line 129: Line 127:
| style="text-align:left;" | Count of 1s in each 4-bit slice of a
| style="text-align:left;" | Count of 1s in each 4-bit slice of a
|-
|-
| style="text-align:left;" | <code>f0 = (e >> 0) & 00001111 00001111</code>
| style="text-align:left;" | <code>f0 = (e >> 0) & 00001111 00001111</code>
| colspan=4 | 00000010
| colspan=4 | 00000010
| colspan=4 | 00000010
| colspan=4 | 00000010
Line 214: Line 212:
}
}
</syntaxhighlight>
</syntaxhighlight>
उपरोक्त कार्यान्वयन में किसी भी ज्ञात एल्गोरिदम की तुलना में सबसे खराब स्थिति वाला व्यवहार है। हालाँकि, जब किसी मान में कुछ गैर-शून्य बिट्स होने की उम्मीद होती है, तो इसके बजाय एल्गोरिदम का उपयोग करना अधिक कुशल हो सकता है जो इन बिट्स को एक समय में गिनता है। जैसा कि वेगनर ने 1960 में वर्णित किया था,<ref name="Wegner_1960"/>x के साथ x का बिटवाइज़ AND - 1 केवल सबसे कम महत्वपूर्ण गैर-शून्य बिट को शून्य करने में x से भिन्न होता है: 1 घटाने से 0s की सबसे दाईं स्ट्रिंग को 1s में बदल दिया जाता है, और सबसे दाईं ओर 1 को 0 में बदल दिया जाता है। यदि x में मूल रूप से n बिट्स थे जो थे 1, तो इस ऑपरेशन के केवल n पुनरावृत्तियों के बाद, x शून्य हो जाएगा। निम्नलिखित कार्यान्वयन इसी सिद्धांत पर आधारित है।
उपरोक्त कार्यान्वयन में किसी भी ज्ञात एल्गोरिदम की तुलना में सबसे खराब स्थिति वाला व्यवहार है। हालाँकि, जब किसी मान में कुछ गैर-शून्य बिट्स होने की उम्मीद होती है, तो इसके बजाय एल्गोरिदम का उपयोग करना अधिक कुशल हो सकता है जो इन बिट्स को समय में गिनता है। जैसा कि वेगनर ने 1960 में वर्णित किया था,<ref name="Wegner_1960"/>x के साथ x का बिटवाइज़ AND - 1 केवल सबसे कम महत्वपूर्ण गैर-शून्य बिट को शून्य करने में x से भिन्न होता है: 1 घटाने से 0s की सबसे दाईं स्ट्रिंग को 1s में बदल दिया जाता है, और सबसे दाईं ओर 1 को 0 में बदल दिया जाता है। यदि x में मूल रूप से n बिट्स थे जो थे 1, तो इस ऑपरेशन के केवल n पुनरावृत्तियों के बाद, x शून्य हो जाएगा। निम्नलिखित कार्यान्वयन इसी सिद्धांत पर आधारित है।


<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
Line 228: Line 226:
}
}
</syntaxhighlight>
</syntaxhighlight>
यदि अधिक मेमोरी उपयोग की अनुमति है, तो हम उपरोक्त विधियों की तुलना में हैमिंग वजन की तेजी से गणना कर सकते हैं। असीमित मेमोरी के साथ, हम आसानी से प्रत्येक 64 बिट पूर्णांक के हैमिंग वजन की एक बड़ी लुकअप तालिका बना सकते हैं। यदि हम प्रत्येक 16 बिट पूर्णांक के हैमिंग फ़ंक्शन की एक लुकअप तालिका संग्रहीत कर सकते हैं, तो हम प्रत्येक 32 बिट पूर्णांक के हैमिंग वजन की गणना करने के लिए निम्नलिखित कार्य कर सकते हैं।
यदि अधिक मेमोरी उपयोग की अनुमति है, तो हम उपरोक्त विधियों की तुलना में हैमिंग वजन की तेजी से गणना कर सकते हैं। असीमित मेमोरी के साथ, हम आसानी से प्रत्येक 64 बिट पूर्णांक के हैमिंग वजन की बड़ी लुकअप तालिका बना सकते हैं। यदि हम प्रत्येक 16 बिट पूर्णांक के हैमिंग फ़ंक्शन की लुकअप तालिका संग्रहीत कर सकते हैं, तो हम प्रत्येक 32 बिट पूर्णांक के हैमिंग वजन की गणना करने के लिए निम्नलिखित कार्य कर सकते हैं।
<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
static uint8_t wordbits[65536] = { /* bitcounts of integers 0 through 65535, inclusive */ };
static uint8_t wordbits[65536] = { /* bitcounts of integers 0 through 65535, inclusive */ };
Line 257: Line 255:


==न्यूनतम वजन==
==न्यूनतम वजन==
[[त्रुटि-सुधार कोड]]|त्रुटि-सुधार कोडिंग में, न्यूनतम हैमिंग वजन, जिसे आमतौर पर न्यूनतम वजन ''डब्ल्यू'' कहा जाता है<sub>min</sub> एक कोड का वजन सबसे कम वजन वाले गैर-शून्य कोड शब्द का होता है। किसी कोड शब्द का भार w शब्द में 1s की संख्या है। उदाहरण के लिए, शब्द 11001010 का भार 4 है।
[[त्रुटि-सुधार कोड]]|त्रुटि-सुधार कोडिंग में, न्यूनतम हैमिंग वजन, जिसे आमतौर पर न्यूनतम वजन ''डब्ल्यू'' कहा जाता है<sub>min</sub> कोड का वजन सबसे कम वजन वाले गैर-शून्य कोड शब्द का होता है। किसी कोड शब्द का भार w शब्द में 1s की संख्या है। उदाहरण के लिए, शब्द 11001010 का भार 4 है।


एक [[रैखिक ब्लॉक कोड]] में न्यूनतम वजन भी [[न्यूनतम हैमिंग दूरी]] (डी) है<sub>min</sub>) और कोड की त्रुटि सुधार क्षमता को परिभाषित करता है। यदि डब्ल्यू<sub>min</sub>= n, फिर d<sub>min</sub>= n और कोड d तक सही हो जाएगा<sub>min</sub>/2 त्रुटियाँ.<ref>Stern & Mahmoud, ''Communications System Design'', [[Prentice Hall]], 2004, p&nbsp;477ff.</ref>
एक [[रैखिक ब्लॉक कोड]] में न्यूनतम वजन भी [[न्यूनतम हैमिंग दूरी]] (डी) है<sub>min</sub>) और कोड की त्रुटि सुधार क्षमता को परिभाषित करता है। यदि डब्ल्यू<sub>min</sub>= n, फिर d<sub>min</sub>= n और कोड d तक सही हो जाएगा<sub>min</sub>/2 त्रुटियाँ.<ref>Stern & Mahmoud, ''Communications System Design'', [[Prentice Hall]], 2004, p&nbsp;477ff.</ref>
Line 263: Line 261:


== भाषा समर्थन ==
== भाषा समर्थन ==
कुछ सी कंपाइलर आंतरिक कार्य प्रदान करते हैं जो बिट गिनती की सुविधा प्रदान करते हैं। उदाहरण के लिए, [[जीएनयू कंपाइलर संग्रह]] (अप्रैल 2004 में संस्करण 3.4 से) में एक अंतर्निहित फ़ंक्शन शामिल है <code>__builtin_popcount</code> यदि उपलब्ध हो तो यह एक प्रोसेसर निर्देश का उपयोग करेगा या अन्यथा एक कुशल लाइब्रेरी कार्यान्वयन का उपयोग करेगा।<ref name="GCC"/>[[एलएलवीएम]]|एलएलवीएम-जीसीसी ने जून 2005 में संस्करण 1.5 से इस फ़ंक्शन को शामिल किया है।<ref name="LLVM"/>
कुछ सी कंपाइलर आंतरिक कार्य प्रदान करते हैं जो बिट गिनती की सुविधा प्रदान करते हैं। उदाहरण के लिए, [[जीएनयू कंपाइलर संग्रह]] (अप्रैल 2004 में संस्करण 3.4 से) में अंतर्निहित फ़ंक्शन शामिल है <code>__builtin_popcount</code> यदि उपलब्ध हो तो यह प्रोसेसर निर्देश का उपयोग करेगा या अन्यथा कुशल लाइब्रेरी कार्यान्वयन का उपयोग करेगा।<ref name="GCC"/>[[एलएलवीएम]]|एलएलवीएम-जीसीसी ने जून 2005 में संस्करण 1.5 से इस फ़ंक्शन को शामिल किया है।<ref name="LLVM"/>


C++ मानक लाइब्रेरी में, बिट-सरणी डेटा संरचना <code>bitset</code> एक <code>count()</code> वह विधि जो सेट किए गए बिट्स की संख्या को गिनती है। [[C++20]] में, एक नया हेडर <code><bit></code> फ़ंक्शंस युक्त, जोड़ा गया था <code>std::popcount</code> और <code>std::has_single_bit</code>, अहस्ताक्षरित पूर्णांक प्रकारों के तर्क लेना।
C++ मानक लाइब्रेरी में, बिट-सरणी डेटा संरचना <code>bitset</code> <code>count()</code> वह विधि जो सेट किए गए बिट्स की संख्या को गिनती है। [[C++20]] में, नया हेडर <code><bit></code> फ़ंक्शंस युक्त, जोड़ा गया था <code>std::popcount</code> और <code>std::has_single_bit</code>, अहस्ताक्षरित पूर्णांक प्रकारों के तर्क लेना।


जावा में, बढ़ने योग्य बिट-सरणी डेटा संरचना {{Javadoc:SE|java/util|BitSet}} एक {{Javadoc:SE|java/util|BitSet|cardinality()}} विधि जो सेट किए गए बिट्स की संख्या की गणना करती है। इसके अलावा, वहाँ हैं {{Javadoc:SE|java/lang|Integer|bitCount(int)}} और {{Javadoc:SE|java/lang|Long|bitCount(long)}} क्रमशः आदिम 32-बिट और 64-बिट पूर्णांकों में बिट्स की गिनती करने का कार्य करता है। यह भी {{Javadoc:SE|java/math|BigInteger}} मनमाना-परिशुद्धता पूर्णांक वर्ग में भी एक है {{Javadoc:SE|java/math|BigInteger|bitCount()}} विधि जो बिट्स की गिनती करती है।
जावा में, बढ़ने योग्य बिट-सरणी डेटा संरचना {{Javadoc:SE|java/util|BitSet}} {{Javadoc:SE|java/util|BitSet|cardinality()}} विधि जो सेट किए गए बिट्स की संख्या की गणना करती है। इसके अलावा, वहाँ हैं {{Javadoc:SE|java/lang|Integer|bitCount(int)}} और {{Javadoc:SE|java/lang|Long|bitCount(long)}} क्रमशः आदिम 32-बिट और 64-बिट पूर्णांकों में बिट्स की गिनती करने का कार्य करता है। यह भी {{Javadoc:SE|java/math|BigInteger}} मनमाना-परिशुद्धता पूर्णांक वर्ग में भी है {{Javadoc:SE|java/math|BigInteger|bitCount()}} विधि जो बिट्स की गिनती करती है।


[[पायथन (प्रोग्रामिंग भाषा)]] में, <code>int</code> प्रकार में एक है <code>bit_count()</code> सेट बिट्स की संख्या गिनने की विधि। यह कार्यक्षमता अक्टूबर 2021 में जारी Python 3.10 में पेश की गई थी।<ref>{{cite web |title=What's New In Python 3.10 |url=https://docs.python.org/3.10/whatsnew/3.10.html |website=python.org}}</ref>
[[पायथन (प्रोग्रामिंग भाषा)]] में, <code>int</code> प्रकार में है <code>bit_count()</code> सेट बिट्स की संख्या गिनने की विधि। यह कार्यक्षमता अक्टूबर 2021 में जारी Python 3.10 में पेश की गई थी।<ref>{{cite web |title=What's New In Python 3.10 |url=https://docs.python.org/3.10/whatsnew/3.10.html |website=python.org}}</ref>
[[ सामान्य लिस्प ]] में, फ़ंक्शन <code>logcount</code>, एक गैर-नकारात्मक पूर्णांक दिया गया है, 1 बिट्स की संख्या लौटाता है। (नकारात्मक पूर्णांकों के लिए यह 2 के पूरक संकेतन में 0 बिट्स की संख्या लौटाता है।) किसी भी स्थिति में पूर्णांक एक BIGNUM हो सकता है।
[[ सामान्य लिस्प | सामान्य लिस्प]] में, फ़ंक्शन <code>logcount</code>, गैर-नकारात्मक पूर्णांक दिया गया है, 1 बिट्स की संख्या लौटाता है। (नकारात्मक पूर्णांकों के लिए यह 2 के पूरक संकेतन में 0 बिट्स की संख्या लौटाता है।) किसी भी स्थिति में पूर्णांक BIGNUM हो सकता है।


[[ग्लासगो हास्केल कंपाइलर]] 7.4 से शुरू होकर, [[हास्केल (प्रोग्रामिंग भाषा)]] बेस पैकेज में एक है <code>popCount</code> फ़ंक्शन सभी प्रकार के उदाहरणों पर उपलब्ध है <code>Bits</code> कक्षा (से उपलब्ध है <code>Data.Bits</code> मापांक)।<ref name="GHC"/>
[[ग्लासगो हास्केल कंपाइलर]] 7.4 से शुरू होकर, [[हास्केल (प्रोग्रामिंग भाषा)]] बेस पैकेज में है <code>popCount</code> फ़ंक्शन सभी प्रकार के उदाहरणों पर उपलब्ध है <code>Bits</code> कक्षा (से उपलब्ध है <code>Data.Bits</code> मापांक)।<ref name="GHC"/>


[[SQL]] भाषा का [[MySQL]] संस्करण प्रदान करता है <code>BIT_COUNT()</code> एक मानक फ़ंक्शन के रूप में।<ref name="MySQL_50"/>
[[SQL]] भाषा का [[MySQL]] संस्करण प्रदान करता है <code>BIT_COUNT()</code> मानक फ़ंक्शन के रूप में।<ref name="MySQL_50"/>


[[फोरट्रान 2008]] में मानक, आंतरिक, मौलिक कार्य है <code>popcnt</code> एक पूर्णांक (या पूर्णांक सरणी) के भीतर गैर-शून्य बिट्स की संख्या लौटाना।<ref name="Metcalf_2011"/>
[[फोरट्रान 2008]] में मानक, आंतरिक, मौलिक कार्य है <code>popcnt</code> पूर्णांक (या पूर्णांक सरणी) के भीतर गैर-शून्य बिट्स की संख्या लौटाना।<ref name="Metcalf_2011"/>


कुछ प्रोग्रामयोग्य वैज्ञानिक पॉकेट कैलकुलेटर सेट बिट्स की संख्या की गणना करने के लिए विशेष कमांड की सुविधा देते हैं, उदाहरण के लिए <code>#B</code> [[HP-16C]] पर<ref name="HP-16C_1982"/><ref name="Schwartz_Grevelle_2003"/>और WP 43S,<ref name="Bonin_2019_OG"/><ref name="Bonin_2019_RG"/> <code>#BITS</code><ref name="Martin_McClure_2015"/><ref name="Martin_2015"/>या <code>BITSUM</code><ref name="Thörngren_2017"/><ref name="Thörngren_2017_2"/>एचपी-16सी एमुलेटर पर, और <code>nBITS</code> WP 34S पर.<ref name="Bonin_2012"/><ref name="Bonin_2015"/>
कुछ प्रोग्रामयोग्य वैज्ञानिक पॉकेट कैलकुलेटर सेट बिट्स की संख्या की गणना करने के लिए विशेष कमांड की सुविधा देते हैं, उदाहरण के लिए <code>#B</code> [[HP-16C]] पर<ref name="HP-16C_1982"/><ref name="Schwartz_Grevelle_2003"/>और WP 43S,<ref name="Bonin_2019_OG"/><ref name="Bonin_2019_RG"/> <code>#BITS</code><ref name="Martin_McClure_2015"/><ref name="Martin_2015"/>या <code>BITSUM</code><ref name="Thörngren_2017"/><ref name="Thörngren_2017_2"/>एचपी-16सी एमुलेटर पर, और <code>nBITS</code> WP 34S पर.<ref name="Bonin_2012"/><ref name="Bonin_2015"/>
Line 284: Line 282:


== प्रोसेसर समर्थन ==
== प्रोसेसर समर्थन ==
* 1960 के दशक में [[IBM STRETCH]] कंप्यूटर ने सभी तार्किक परिचालनों के उप-उत्पाद के रूप में सेट बिट्स की संख्या के साथ-साथ अग्रणी शून्य की संख्या की गणना की।<ref name="Warren_2013"/>* [[क्रे]] सुपरकंप्यूटर में शुरुआत में जनसंख्या गणना [[मशीन अनुदेश]] प्रदर्शित किया गया था, ऐसी अफवाह थी कि [[क्रिप्ट विश्लेषण]] अनुप्रयोगों के लिए अमेरिकी सरकार की [[राष्ट्रीय सुरक्षा एजेंसी]] द्वारा विशेष रूप से अनुरोध किया गया था।<ref name="Warren_2013"/><!-- This ref supports the rumour in general, but does not mention Cray -->
* 1960 के दशक में [[IBM STRETCH]] कंप्यूटर ने सभी तार्किक परिचालनों के उप-उत्पाद के रूप में सेट बिट्स की संख्या के साथ-साथ अग्रणी शून्य की संख्या की गणना की।<ref name="Warren_2013"/>* [[क्रे]] सुपरकंप्यूटर में शुरुआत में जनसंख्या गणना [[मशीन अनुदेश]] प्रदर्शित किया गया था, ऐसी अफवाह थी कि [[क्रिप्ट विश्लेषण]] अनुप्रयोगों के लिए अमेरिकी सरकार की [[राष्ट्रीय सुरक्षा एजेंसी]] द्वारा विशेष रूप से अनुरोध किया गया था।<ref name="Warren_2013"/>
* [[नियंत्रण डेटा निगम]] (सीडीसी) की [[सीडीसी 6000 श्रृंखला]] और सीडीसी साइबर|साइबर 70/170 श्रृंखला की मशीनों में जनसंख्या गणना निर्देश शामिल हैं; 60-बिट मशीनों के लिए COMPASS#COMPASS में, इस निर्देश को इस प्रकार कोडित किया गया था <code>CXi</code>.
* [[नियंत्रण डेटा निगम]] (सीडीसी) की [[सीडीसी 6000 श्रृंखला]] और सीडीसी साइबर|साइबर 70/170 श्रृंखला की मशीनों में जनसंख्या गणना निर्देश शामिल हैं; 60-बिट मशीनों के लिए COMPASS#COMPASS में, इस निर्देश को इस प्रकार कोडित किया गया था <code>CXi</code>.
* 64-बिट SPARC संस्करण 9 आर्किटेक्चर परिभाषित करता है <code>POPC</code> निर्देश,<ref name="SPARC_1992"/><ref name="Warren_2013"/>लेकिन अधिकांश कार्यान्वयन इसे लागू नहीं करते हैं, जिसके लिए ऑपरेटिंग सिस्टम द्वारा इसका अनुकरण करना आवश्यक होता है।<ref name="JDK_BitCount"/>* [[डोनाल्ड नुथ]] का मॉडल कंप्यूटर [[M[[MIX]]]] जो अपनी पुस्तक [[कंप्यूटर प्रोग्रामिंग की कला]] में MIX का स्थान लेने जा रहा है, उसमें एक है <code>SADD</code> 1999 से निर्देश। <code>SADD a,b,c</code> सभी बिट्स को गिनता है जो b में 1 और c में 0 हैं और परिणाम को a में लिखता है।
* 64-बिट SPARC संस्करण 9 आर्किटेक्चर परिभाषित करता है <code>POPC</code> निर्देश,<ref name="SPARC_1992"/><ref name="Warren_2013"/>लेकिन अधिकांश कार्यान्वयन इसे लागू नहीं करते हैं, जिसके लिए ऑपरेटिंग सिस्टम द्वारा इसका अनुकरण करना आवश्यक होता है।<ref name="JDK_BitCount"/>* [[डोनाल्ड नुथ]] का मॉडल कंप्यूटर [[M[[MIX]]]] जो अपनी पुस्तक [[कंप्यूटर प्रोग्रामिंग की कला]] में MIX का स्थान लेने जा रहा है, उसमें है <code>SADD</code> 1999 से निर्देश। <code>SADD a,b,c</code> सभी बिट्स को गिनता है जो b में 1 और c में 0 हैं और परिणाम को a में लिखता है।
* 1999 में जारी [[कॉम्पैक]] का अल्फा 21264A, पहला अल्फा श्रृंखला सीपीयू डिज़ाइन था जिसमें काउंट एक्सटेंशन था (<code>CIX</code>).
* 1999 में जारी [[कॉम्पैक]] का अल्फा 21264A, पहला अल्फा श्रृंखला सीपीयू डिज़ाइन था जिसमें काउंट एक्सटेंशन था (<code>CIX</code>).
* [[एनालॉग डिवाइस]]ेस के [[ Blackfin ]] प्रोसेसर की सुविधा है <code>ONES</code> 32-बिट जनसंख्या गणना करने का निर्देश।<ref name="AD_2001"/>* [[AMD]] के [[AMD K10]] आर्किटेक्चर ने उन्नत बिट मैनिपुलेशन (ABM) [[ निर्देश समुच्चय ]] की शुरुआत की <code>POPCNT</code> 2007 में [[SSE4a]] एक्सटेंशन के भाग के रूप में निर्देश।
* [[एनालॉग डिवाइस]]ेस के [[ Blackfin |Blackfin]] प्रोसेसर की सुविधा है <code>ONES</code> 32-बिट जनसंख्या गणना करने का निर्देश।<ref name="AD_2001"/>* [[AMD]] के [[AMD K10]] आर्किटेक्चर ने उन्नत बिट मैनिपुलेशन (ABM) [[ निर्देश समुच्चय |निर्देश समुच्चय]] की शुरुआत की <code>POPCNT</code> 2007 में [[SSE4a]] एक्सटेंशन के भाग के रूप में निर्देश।
* [[ इण्टेल कोर ]] प्रोसेसर पेश किया गया <code>POPCNT</code> SSE4.2 इंस्ट्रक्शन सेट एक्सटेंशन के साथ निर्देश, पहली बार नेहलेम (माइक्रोआर्किटेक्चर)-आधारित [[कोर i7]] प्रोसेसर में उपलब्ध है, जो नवंबर 2008 में जारी किया गया था।
* [[ इण्टेल कोर | इण्टेल कोर]] प्रोसेसर पेश किया गया <code>POPCNT</code> SSE4.2 इंस्ट्रक्शन सेट एक्सटेंशन के साथ निर्देश, पहली बार नेहलेम (माइक्रोआर्किटेक्चर)-आधारित [[कोर i7]] प्रोसेसर में उपलब्ध है, जो नवंबर 2008 में जारी किया गया था।
* [[एआरएम वास्तुकला]] की शुरुआत की गई <code>VCNT</code> [[एआरएम एडवांस्ड SIMD]] (NEON (निर्देश सेट)) एक्सटेंशन के भाग के रूप में निर्देश।
* [[एआरएम वास्तुकला]] की शुरुआत की गई <code>VCNT</code> [[एआरएम एडवांस्ड SIMD]] (NEON (निर्देश सेट)) एक्सटेंशन के भाग के रूप में निर्देश।
* [[ RISC-वी ]]ी वास्तुकला की शुरुआत की गई <code>PCNT</code> बिट मैनिपुलेशन (बी) एक्सटेंशन के भाग के रूप में निर्देश।<ref name="RISC-V-B"/>
* [[ RISC-वी ]]ी वास्तुकला की शुरुआत की गई <code>PCNT</code> बिट मैनिपुलेशन (बी) एक्सटेंशन के भाग के रूप में निर्देश।<ref name="RISC-V-B"/>

Revision as of 10:52, 19 July 2023

एक स्ट्रिंग का हैमिंग वजन (कंप्यूटर विज्ञान) उन प्रतीकों की संख्या है जो प्रयुक्त वर्णमाला के शून्य-प्रतीक से भिन्न होते हैं। इस प्रकार यह समान लंबाई की पूर्ण-शून्य स्ट्रिंग से हैमिंग दूरी के बराबर है। सबसे विशिष्ट मामले के लिए, अंश ्स की स्ट्रिंग, यह स्ट्रिंग में 1 की संख्या है, या किसी दिए गए नंबर की बाइनरी अंक प्रणाली का अंक योग और टैक्सीकैब ज्यामिति|ℓ₁ बिट वेक्टर का मानदंड . इस द्विआधारी मामले में, इसे जनसंख्या गणना भी कहा जाता है,[1]पॉपकाउंट, बग़ल में योग,[2]या बिट योग.[3]

Examples
String Hamming weight
11101 4
11101000 4
00000000 0
678012340567 10
<graph>{"legends":[],"scales":[{"type":"linear","name":"x","zero":false,"domain":{"data":"chart","field":"x"},"range":"width","nice":true},{"type":"linear","name":"y","domain":{"data":"chart","field":"y"},"zero":false,"range":"height","nice":true},{"domain":{"data":"chart","field":"series"},"type":"ordinal","name":"color","range":["red"]}],"version":2,"marks":[{"type":"line","properties":{"hover":{"stroke":{"value":"red"}},"update":{"stroke":{"scale":"color","field":"series"}},"enter":{"y":{"scale":"y","field":"y"},"x":{"scale":"x","field":"x"},"stroke":{"scale":"color","field":"series"},"strokeWidth":{"value":1}}},"from":{"data":"chart"}}],"height":200,"axes":[{"type":"x","scale":"x","format":"d","properties":{"title":{"fill":{"value":"#54595d"}},"grid":{"stroke":{"value":"#54595d"}},"ticks":{"stroke":{"value":"#54595d"}},"axis":{"strokeWidth":{"value":2},"stroke":{"value":"#54595d"}},"labels":{"fill":{"value":"#54595d"}}},"grid":false},{"type":"y","scale":"y","format":"d","properties":{"title":{"fill":{"value":"#54595d"}},"grid":{"stroke":{"value":"#54595d"}},"ticks":{"stroke":{"value":"#54595d"}},"axis":{"strokeWidth":{"value":2},"stroke":{"value":"#54595d"}},"labels":{"fill":{"value":"#54595d"}}},"grid":true}],"data":[{"format":{"parse":{"y":"integer","x":"integer"},"type":"json"},"name":"chart","values":[{"y":0,"series":"y","x":0},{"y":1,"series":"y","x":1},{"y":1,"series":"y","x":2},{"y":2,"series":"y","x":3},{"y":1,"series":"y","x":4},{"y":2,"series":"y","x":5},{"y":2,"series":"y","x":6},{"y":3,"series":"y","x":7},{"y":1,"series":"y","x":8},{"y":2,"series":"y","x":9},{"y":2,"series":"y","x":10},{"y":3,"series":"y","x":11},{"y":2,"series":"y","x":12},{"y":3,"series":"y","x":13},{"y":3,"series":"y","x":14},{"y":4,"series":"y","x":15},{"y":1,"series":"y","x":16},{"y":2,"series":"y","x":17},{"y":2,"series":"y","x":18},{"y":3,"series":"y","x":19},{"y":2,"series":"y","x":20},{"y":3,"series":"y","x":21},{"y":3,"series":"y","x":22},{"y":4,"series":"y","x":23},{"y":2,"series":"y","x":24},{"y":3,"series":"y","x":25},{"y":3,"series":"y","x":26},{"y":4,"series":"y","x":27},{"y":3,"series":"y","x":28},{"y":4,"series":"y","x":29},{"y":4,"series":"y","x":30},{"y":5,"series":"y","x":31},{"y":1,"series":"y","x":32},{"y":2,"series":"y","x":33},{"y":2,"series":"y","x":34},{"y":3,"series":"y","x":35},{"y":2,"series":"y","x":36},{"y":3,"series":"y","x":37},{"y":3,"series":"y","x":38},{"y":4,"series":"y","x":39},{"y":2,"series":"y","x":40},{"y":3,"series":"y","x":41},{"y":3,"series":"y","x":42},{"y":4,"series":"y","x":43},{"y":3,"series":"y","x":44},{"y":4,"series":"y","x":45},{"y":4,"series":"y","x":46},{"y":5,"series":"y","x":47},{"y":2,"series":"y","x":48},{"y":3,"series":"y","x":49},{"y":3,"series":"y","x":50},{"y":4,"series":"y","x":51},{"y":3,"series":"y","x":52},{"y":4,"series":"y","x":53},{"y":4,"series":"y","x":54},{"y":5,"series":"y","x":55},{"y":3,"series":"y","x":56},{"y":4,"series":"y","x":57},{"y":4,"series":"y","x":58},{"y":5,"series":"y","x":59},{"y":4,"series":"y","x":60},{"y":5,"series":"y","x":61},{"y":5,"series":"y","x":62},{"y":6,"series":"y","x":63},{"y":1,"series":"y","x":64},{"y":2,"series":"y","x":65},{"y":2,"series":"y","x":66},{"y":3,"series":"y","x":67},{"y":2,"series":"y","x":68},{"y":3,"series":"y","x":69},{"y":3,"series":"y","x":70},{"y":4,"series":"y","x":71},{"y":2,"series":"y","x":72},{"y":3,"series":"y","x":73},{"y":3,"series":"y","x":74},{"y":4,"series":"y","x":75},{"y":3,"series":"y","x":76},{"y":4,"series":"y","x":77},{"y":4,"series":"y","x":78},{"y":5,"series":"y","x":79},{"y":2,"series":"y","x":80},{"y":3,"series":"y","x":81},{"y":3,"series":"y","x":82},{"y":4,"series":"y","x":83},{"y":3,"series":"y","x":84},{"y":4,"series":"y","x":85},{"y":4,"series":"y","x":86},{"y":5,"series":"y","x":87},{"y":3,"series":"y","x":88},{"y":4,"series":"y","x":89},{"y":4,"series":"y","x":90},{"y":5,"series":"y","x":91},{"y":4,"series":"y","x":92},{"y":5,"series":"y","x":93},{"y":5,"series":"y","x":94},{"y":6,"series":"y","x":95},{"y":2,"series":"y","x":96},{"y":3,"series":"y","x":97},{"y":3,"series":"y","x":98},{"y":4,"series":"y","x":99},{"y":3,"series":"y","x":100},{"y":4,"series":"y","x":101},{"y":4,"series":"y","x":102},{"y":5,"series":"y","x":103},{"y":3,"series":"y","x":104},{"y":4,"series":"y","x":105},{"y":4,"series":"y","x":106},{"y":5,"series":"y","x":107},{"y":4,"series":"y","x":108},{"y":5,"series":"y","x":109},{"y":5,"series":"y","x":110},{"y":6,"series":"y","x":111},{"y":3,"series":"y","x":112},{"y":4,"series":"y","x":113},{"y":4,"series":"y","x":114},{"y":5,"series":"y","x":115},{"y":4,"series":"y","x":116},{"y":5,"series":"y","x":117},{"y":5,"series":"y","x":118},{"y":6,"series":"y","x":119},{"y":4,"series":"y","x":120},{"y":5,"series":"y","x":121},{"y":5,"series":"y","x":122},{"y":6,"series":"y","x":123},{"y":5,"series":"y","x":124},{"y":6,"series":"y","x":125},{"y":6,"series":"y","x":126},{"y":7,"series":"y","x":127},{"y":1,"series":"y","x":128},{"y":2,"series":"y","x":129},{"y":2,"series":"y","x":130},{"y":3,"series":"y","x":131},{"y":2,"series":"y","x":132},{"y":3,"series":"y","x":133},{"y":3,"series":"y","x":134},{"y":4,"series":"y","x":135},{"y":2,"series":"y","x":136},{"y":3,"series":"y","x":137},{"y":3,"series":"y","x":138},{"y":4,"series":"y","x":139},{"y":3,"series":"y","x":140},{"y":4,"series":"y","x":141},{"y":4,"series":"y","x":142},{"y":5,"series":"y","x":143},{"y":2,"series":"y","x":144},{"y":3,"series":"y","x":145},{"y":3,"series":"y","x":146},{"y":4,"series":"y","x":147},{"y":3,"series":"y","x":148},{"y":4,"series":"y","x":149},{"y":4,"series":"y","x":150},{"y":5,"series":"y","x":151},{"y":3,"series":"y","x":152},{"y":4,"series":"y","x":153},{"y":4,"series":"y","x":154},{"y":5,"series":"y","x":155},{"y":4,"series":"y","x":156},{"y":5,"series":"y","x":157},{"y":5,"series":"y","x":158},{"y":6,"series":"y","x":159},{"y":2,"series":"y","x":160},{"y":3,"series":"y","x":161},{"y":3,"series":"y","x":162},{"y":4,"series":"y","x":163},{"y":3,"series":"y","x":164},{"y":4,"series":"y","x":165},{"y":4,"series":"y","x":166},{"y":5,"series":"y","x":167},{"y":3,"series":"y","x":168},{"y":4,"series":"y","x":169},{"y":4,"series":"y","x":170},{"y":5,"series":"y","x":171},{"y":4,"series":"y","x":172},{"y":5,"series":"y","x":173},{"y":5,"series":"y","x":174},{"y":6,"series":"y","x":175},{"y":3,"series":"y","x":176},{"y":4,"series":"y","x":177},{"y":4,"series":"y","x":178},{"y":5,"series":"y","x":179},{"y":4,"series":"y","x":180},{"y":5,"series":"y","x":181},{"y":5,"series":"y","x":182},{"y":6,"series":"y","x":183},{"y":4,"series":"y","x":184},{"y":5,"series":"y","x":185},{"y":5,"series":"y","x":186},{"y":6,"series":"y","x":187},{"y":5,"series":"y","x":188},{"y":6,"series":"y","x":189},{"y":6,"series":"y","x":190},{"y":7,"series":"y","x":191},{"y":2,"series":"y","x":192},{"y":3,"series":"y","x":193},{"y":3,"series":"y","x":194},{"y":4,"series":"y","x":195},{"y":3,"series":"y","x":196},{"y":4,"series":"y","x":197},{"y":4,"series":"y","x":198},{"y":5,"series":"y","x":199},{"y":3,"series":"y","x":200},{"y":4,"series":"y","x":201},{"y":4,"series":"y","x":202},{"y":5,"series":"y","x":203},{"y":4,"series":"y","x":204},{"y":5,"series":"y","x":205},{"y":5,"series":"y","x":206},{"y":6,"series":"y","x":207},{"y":3,"series":"y","x":208},{"y":4,"series":"y","x":209},{"y":4,"series":"y","x":210},{"y":5,"series":"y","x":211},{"y":4,"series":"y","x":212},{"y":5,"series":"y","x":213},{"y":5,"series":"y","x":214},{"y":6,"series":"y","x":215},{"y":4,"series":"y","x":216},{"y":5,"series":"y","x":217},{"y":5,"series":"y","x":218},{"y":6,"series":"y","x":219},{"y":5,"series":"y","x":220},{"y":6,"series":"y","x":221},{"y":6,"series":"y","x":222},{"y":7,"series":"y","x":223},{"y":3,"series":"y","x":224},{"y":4,"series":"y","x":225},{"y":4,"series":"y","x":226},{"y":5,"series":"y","x":227},{"y":4,"series":"y","x":228},{"y":5,"series":"y","x":229},{"y":5,"series":"y","x":230},{"y":6,"series":"y","x":231},{"y":4,"series":"y","x":232},{"y":5,"series":"y","x":233},{"y":5,"series":"y","x":234},{"y":6,"series":"y","x":235},{"y":5,"series":"y","x":236},{"y":6,"series":"y","x":237},{"y":6,"series":"y","x":238},{"y":7,"series":"y","x":239},{"y":4,"series":"y","x":240},{"y":5,"series":"y","x":241},{"y":5,"series":"y","x":242},{"y":6,"series":"y","x":243},{"y":5,"series":"y","x":244},{"y":6,"series":"y","x":245},{"y":6,"series":"y","x":246},{"y":7,"series":"y","x":247},{"y":5,"series":"y","x":248},{"y":6,"series":"y","x":249},{"y":6,"series":"y","x":250},{"y":7,"series":"y","x":251},{"y":6,"series":"y","x":252},{"y":7,"series":"y","x":253},{"y":7,"series":"y","x":254},{"y":8,"series":"y","x":255},{"y":1,"series":"y","x":256}]}],"width":300}</graph>
A plot for the population count (Hamming weight for binary numbers) for (decimal) numbers 0 to 256.[4][5][6]


इतिहास और उपयोग

हैमिंग वेट का नाम रिचर्ड हैमिंग के नाम पर रखा गया है, हालांकि उन्होंने इस धारणा की उत्पत्ति नहीं की थी।[7]बाइनरी संख्याओं के हैमिंग वेट का उपयोग 1899 में जेम्स व्हिटब्रेड ली ग्लैशर द्वारा पास्कल के त्रिकोण की पंक्ति में गोल्ड के अनुक्रम के लिए सूत्र देने के लिए किया गया था।[8]इरविंग एस. रीड ने 1954 में बाइनरी मामले में हैमिंग वजन के बराबर अवधारणा पेश की।[9]

हैमिंग वेट का उपयोग सूचना सिद्धांत, कोडिंग सिद्धांत और क्रिप्टोग्राफी सहित कई विषयों में किया जाता है। हैमिंग वज़न के अनुप्रयोगों के उदाहरणों में शामिल हैं:

  • वर्ग द्वारा मॉड्यूलर घातांक में, घातांक ई के लिए आवश्यक मॉड्यूलर गुणन की संख्या लॉग है2 ई + वजन(ई)। यही कारण है कि आरएसए (एल्गोरिदम) में प्रयुक्त सार्वजनिक कुंजी मान ई को आम तौर पर कम हैमिंग वजन की संख्या के रूप में चुना जाता है।[10]* हैमिंग वजन कॉर्ड (वितरित हैश तालिका) में नोड्स के बीच पथ की लंबाई निर्धारित करता है।[11]* बायोमेट्रिक डेटाबेस में आईरिसकोड लुकअप आमतौर पर प्रत्येक संग्रहीत रिकॉर्ड के लिए हैमिंग दूरी की गणना करके कार्यान्वित किया जाता है।
  • बिटबोर्ड प्रतिनिधित्व का उपयोग करने वाले कंप्यूटर शतरंज कार्यक्रमों में, बिटबोर्ड का हैमिंग वजन खेल में शेष दिए गए प्रकार के टुकड़ों की संख्या, या खिलाड़ी के टुकड़ों द्वारा नियंत्रित बोर्ड के वर्गों की संख्या देता है, और इसलिए यह महत्वपूर्ण योगदान है किसी पद के मूल्य के लिए शब्द।
  • हैमिंग वेट का उपयोग पहचान एफएफएस (एक्स) = पॉप (एक्स ^ (एक्स - 1)) का उपयोग करके पहले सेट को कुशलतापूर्वक खोजने के लिए किया जा सकता है। यह SPARC जैसे प्लेटफ़ॉर्म पर उपयोगी है जिसमें हार्डवेयर हैमिंग वेट निर्देश हैं लेकिन कोई हार्डवेयर पहले सेट निर्देश नहीं ढूंढता है।[12][1]* हैमिंग वेट ऑपरेशन की व्याख्या यूनरी अंक प्रणाली से बाइनरी संख्याओं में रूपांतरण के रूप में की जा सकती है।[13]* बिट सरणी और तरंगिका वृक्ष जैसी कुछ संक्षिप्त डेटा संरचनाओं के कार्यान्वयन में।

कुशल कार्यान्वयन

क्रिप्टोग्राफी और अन्य अनुप्रयोगों में बिट सरणी की जनसंख्या गणना की अक्सर आवश्यकता होती है। दो शब्दों ए और बी की हैमिंग दूरी की गणना ए एक्स या बी के हैमिंग वजन के रूप में की जा सकती है।[1]

इसे कुशलतापूर्वक कैसे कार्यान्वित किया जाए इसकी समस्या का व्यापक अध्ययन किया गया है। गणना के लिए एकल ऑपरेशन, या बिट वैक्टर पर समानांतर संचालन #प्रोसेसर समर्थन हैं। जिन प्रोसेसरों में उन सुविधाओं की कमी है, उनके लिए ज्ञात सर्वोत्तम समाधान ट्री पैटर्न में गिनती जोड़ने पर आधारित हैं। उदाहरण के लिए, 16-बिट बाइनरी संख्या a = 0110 1100 1011 1010 में 1 बिट की संख्या गिनने के लिए, ये ऑपरेशन किए जा सकते हैं:

Expression Binary Decimal Comment
a 01 10 11 00 10 11 10 10 27834 The original number
b0 = (a >> 0) & 01 01 01 01 01 01 01 01 01 00 01 00 00 01 00 00 1, 0, 1, 0, 0, 1, 0, 0 Every other bit from a
b1 = (a >> 1) & 01 01 01 01 01 01 01 01 00 01 01 00 01 01 01 01 0, 1, 1, 0, 1, 1, 1, 1 The remaining bits from a
c = b0 + b1 01 01 10 00 01 10 01 01 1, 1, 2, 0, 1, 2, 1, 1 Count of 1s in each 2-bit slice of a
d0 = (c >> 0) & 0011 0011 0011 0011 0001 0000 0010 0001 1, 0, 2, 1 Every other count from c
d2 = (c >> 2) & 0011 0011 0011 0011 0001 0010 0001 0001 1, 2, 1, 1 The remaining counts from c
e = d0 + d2 0010 0010 0011 0010 2, 2, 3, 2 Count of 1s in each 4-bit slice of a
f0 = (e >> 0) & 00001111 00001111 00000010 00000010 2, 2 Every other count from e
f4 = (e >> 4) & 00001111 00001111 00000010 00000011 2, 3 The remaining counts from e
g = f0 + f4 00000100 00000101 4, 5 Count of 1s in each 8-bit slice of a
h0 = (g >> 0) & 0000000011111111 0000000000000101 5 Every other count from g
h8 = (g >> 8) & 0000000011111111 0000000000000100 4 The remaining counts from g
i = h0 + h8 0000000000001001 9 Count of 1s in entire 16-bit word

यहां, ऑपरेशन सी (प्रोग्रामिंग भाषा) के समान हैं X >> Y का अर्थ है X को Y बिट्स द्वारा दाईं ओर स्थानांतरित करना, X और Y का अर्थ है X और Y का बिटवाइज़ AND, और + सामान्य जोड़ है। इस समस्या के लिए ज्ञात सर्वोत्तम एल्गोरिदम ऊपर चित्रित अवधारणा पर आधारित हैं और यहां दिए गए हैं:[1] 

//types and constants used in the functions below
//uint64_t is an unsigned 64-bit integer variable type (defined in C99 version of C language)
const uint64_t m1  = 0x5555555555555555; //binary: 0101...
const uint64_t m2  = 0x3333333333333333; //binary: 00110011..
const uint64_t m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64_t m8  = 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
const uint64_t m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64_t m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...

//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//This algorithm uses 24 arithmetic operations (shift, add, and).
int popcount64a(uint64_t x)
{
    x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits 
    x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits 
    x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits 
    x = (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits 
    x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits 
    x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits 
    return x;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with slow multiplication.
//This algorithm uses 17 arithmetic operations.
int popcount64b(uint64_t x)
{
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    x += x >>  8;  //put count of each 16 bits into their lowest 8 bits
    x += x >> 16;  //put count of each 32 bits into their lowest 8 bits
    x += x >> 32;  //put count of each 64 bits into their lowest 8 bits
    return x & 0x7f;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with fast multiplication.
//This algorithm uses 12 arithmetic operations, one of which is a multiply.
int popcount64c(uint64_t x)
{
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    return (x * h01) >> 56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}

उपरोक्त कार्यान्वयन में किसी भी ज्ञात एल्गोरिदम की तुलना में सबसे खराब स्थिति वाला व्यवहार है। हालाँकि, जब किसी मान में कुछ गैर-शून्य बिट्स होने की उम्मीद होती है, तो इसके बजाय एल्गोरिदम का उपयोग करना अधिक कुशल हो सकता है जो इन बिट्स को समय में गिनता है। जैसा कि वेगनर ने 1960 में वर्णित किया था,[14]x के साथ x का बिटवाइज़ AND - 1 केवल सबसे कम महत्वपूर्ण गैर-शून्य बिट को शून्य करने में x से भिन्न होता है: 1 घटाने से 0s की सबसे दाईं स्ट्रिंग को 1s में बदल दिया जाता है, और सबसे दाईं ओर 1 को 0 में बदल दिया जाता है। यदि x में मूल रूप से n बिट्स थे जो थे 1, तो इस ऑपरेशन के केवल n पुनरावृत्तियों के बाद, x शून्य हो जाएगा। निम्नलिखित कार्यान्वयन इसी सिद्धांत पर आधारित है। 

//This is better when most bits in x are 0
//This algorithm works the same for all data sizes.
//This algorithm uses 3 arithmetic operations and 1 comparison/branch per "1" bit in x.
int popcount64d(uint64_t x)
{
    int count;
    for (count=0; x; count++)
        x &= x - 1;
    return count;
}

यदि अधिक मेमोरी उपयोग की अनुमति है, तो हम उपरोक्त विधियों की तुलना में हैमिंग वजन की तेजी से गणना कर सकते हैं। असीमित मेमोरी के साथ, हम आसानी से प्रत्येक 64 बिट पूर्णांक के हैमिंग वजन की बड़ी लुकअप तालिका बना सकते हैं। यदि हम प्रत्येक 16 बिट पूर्णांक के हैमिंग फ़ंक्शन की लुकअप तालिका संग्रहीत कर सकते हैं, तो हम प्रत्येक 32 बिट पूर्णांक के हैमिंग वजन की गणना करने के लिए निम्नलिखित कार्य कर सकते हैं। 

static uint8_t wordbits[65536] = { /* bitcounts of integers 0 through 65535, inclusive */ };
//This algorithm uses 3 arithmetic operations and 2 memory reads.
int popcount32e(uint32_t x)
{
    return wordbits[x & 0xFFFF] + wordbits[x >> 16];
}

//Optionally, the wordbits[] table could be filled using this function
int popcount32e_init(void)
{
    uint32_t i;
    uint16_t x;
    int count;
    for (i=0; i <= 0xFFFF; i++)
    {
        x = i;
        for (count=0; x; count++) // borrowed from popcount64d() above
            x &= x - 1;
        wordbits[i] = count;
    }
}

मुला एट अल.[15]दिखाया गया है कि पॉपकाउंट64बी का वेक्टरकृत संस्करण समर्पित निर्देशों (उदाहरण के लिए, x64 प्रोसेसर पर पॉपसीएनटी) की तुलना में तेजी से चल सकता है।

न्यूनतम वजन

त्रुटि-सुधार कोड|त्रुटि-सुधार कोडिंग में, न्यूनतम हैमिंग वजन, जिसे आमतौर पर न्यूनतम वजन डब्ल्यू कहा जाता हैmin कोड का वजन सबसे कम वजन वाले गैर-शून्य कोड शब्द का होता है। किसी कोड शब्द का भार w शब्द में 1s की संख्या है। उदाहरण के लिए, शब्द 11001010 का भार 4 है।

एक रैखिक ब्लॉक कोड में न्यूनतम वजन भी न्यूनतम हैमिंग दूरी (डी) हैmin) और कोड की त्रुटि सुधार क्षमता को परिभाषित करता है। यदि डब्ल्यूmin= n, फिर dmin= n और कोड d तक सही हो जाएगाmin/2 त्रुटियाँ.[16]


भाषा समर्थन

कुछ सी कंपाइलर आंतरिक कार्य प्रदान करते हैं जो बिट गिनती की सुविधा प्रदान करते हैं। उदाहरण के लिए, जीएनयू कंपाइलर संग्रह (अप्रैल 2004 में संस्करण 3.4 से) में अंतर्निहित फ़ंक्शन शामिल है __builtin_popcount यदि उपलब्ध हो तो यह प्रोसेसर निर्देश का उपयोग करेगा या अन्यथा कुशल लाइब्रेरी कार्यान्वयन का उपयोग करेगा।[17]एलएलवीएम|एलएलवीएम-जीसीसी ने जून 2005 में संस्करण 1.5 से इस फ़ंक्शन को शामिल किया है।[18]

C++ मानक लाइब्रेरी में, बिट-सरणी डेटा संरचना bitset count() वह विधि जो सेट किए गए बिट्स की संख्या को गिनती है। C++20 में, नया हेडर <bit> फ़ंक्शंस युक्त, जोड़ा गया था std::popcount और std::has_single_bit, अहस्ताक्षरित पूर्णांक प्रकारों के तर्क लेना।

जावा में, बढ़ने योग्य बिट-सरणी डेटा संरचना BitSet BitSet.cardinality() विधि जो सेट किए गए बिट्स की संख्या की गणना करती है। इसके अलावा, वहाँ हैं Integer.bitCount(int) और Long.bitCount(long) क्रमशः आदिम 32-बिट और 64-बिट पूर्णांकों में बिट्स की गिनती करने का कार्य करता है। यह भी BigInteger मनमाना-परिशुद्धता पूर्णांक वर्ग में भी है BigInteger.bitCount() विधि जो बिट्स की गिनती करती है।

पायथन (प्रोग्रामिंग भाषा) में, int प्रकार में है bit_count() सेट बिट्स की संख्या गिनने की विधि। यह कार्यक्षमता अक्टूबर 2021 में जारी Python 3.10 में पेश की गई थी।[19] सामान्य लिस्प में, फ़ंक्शन logcount, गैर-नकारात्मक पूर्णांक दिया गया है, 1 बिट्स की संख्या लौटाता है। (नकारात्मक पूर्णांकों के लिए यह 2 के पूरक संकेतन में 0 बिट्स की संख्या लौटाता है।) किसी भी स्थिति में पूर्णांक BIGNUM हो सकता है।

ग्लासगो हास्केल कंपाइलर 7.4 से शुरू होकर, हास्केल (प्रोग्रामिंग भाषा) बेस पैकेज में है popCount फ़ंक्शन सभी प्रकार के उदाहरणों पर उपलब्ध है Bits कक्षा (से उपलब्ध है Data.Bits मापांक)।[20]

SQL भाषा का MySQL संस्करण प्रदान करता है BIT_COUNT() मानक फ़ंक्शन के रूप में।[21]

फोरट्रान 2008 में मानक, आंतरिक, मौलिक कार्य है popcnt पूर्णांक (या पूर्णांक सरणी) के भीतर गैर-शून्य बिट्स की संख्या लौटाना।[22]

कुछ प्रोग्रामयोग्य वैज्ञानिक पॉकेट कैलकुलेटर सेट बिट्स की संख्या की गणना करने के लिए विशेष कमांड की सुविधा देते हैं, उदाहरण के लिए #B HP-16C पर[3][23]और WP 43S,[24][25] #BITS[26][27]या BITSUM[28][29]एचपी-16सी एमुलेटर पर, और nBITS WP 34S पर.[30][31]

फ्रीपास्कल संस्करण 3.0 से पॉपसीएनटी लागू करता है।[32]


प्रोसेसर समर्थन

  • 1960 के दशक में IBM STRETCH कंप्यूटर ने सभी तार्किक परिचालनों के उप-उत्पाद के रूप में सेट बिट्स की संख्या के साथ-साथ अग्रणी शून्य की संख्या की गणना की।[1]* क्रे सुपरकंप्यूटर में शुरुआत में जनसंख्या गणना मशीन अनुदेश प्रदर्शित किया गया था, ऐसी अफवाह थी कि क्रिप्ट विश्लेषण अनुप्रयोगों के लिए अमेरिकी सरकार की राष्ट्रीय सुरक्षा एजेंसी द्वारा विशेष रूप से अनुरोध किया गया था।[1]
  • नियंत्रण डेटा निगम (सीडीसी) की सीडीसी 6000 श्रृंखला और सीडीसी साइबर|साइबर 70/170 श्रृंखला की मशीनों में जनसंख्या गणना निर्देश शामिल हैं; 60-बिट मशीनों के लिए COMPASS#COMPASS में, इस निर्देश को इस प्रकार कोडित किया गया था CXi.
  • 64-बिट SPARC संस्करण 9 आर्किटेक्चर परिभाषित करता है POPC निर्देश,[12][1]लेकिन अधिकांश कार्यान्वयन इसे लागू नहीं करते हैं, जिसके लिए ऑपरेटिंग सिस्टम द्वारा इसका अनुकरण करना आवश्यक होता है।[33]* डोनाल्ड नुथ का मॉडल कंप्यूटर [[MMIX]] जो अपनी पुस्तक कंप्यूटर प्रोग्रामिंग की कला में MIX का स्थान लेने जा रहा है, उसमें है SADD 1999 से निर्देश। SADD a,b,c सभी बिट्स को गिनता है जो b में 1 और c में 0 हैं और परिणाम को a में लिखता है।
  • 1999 में जारी कॉम्पैक का अल्फा 21264A, पहला अल्फा श्रृंखला सीपीयू डिज़ाइन था जिसमें काउंट एक्सटेंशन था (CIX).
  • एनालॉग डिवाइसेस के Blackfin प्रोसेसर की सुविधा है ONES 32-बिट जनसंख्या गणना करने का निर्देश।[34]* AMD के AMD K10 आर्किटेक्चर ने उन्नत बिट मैनिपुलेशन (ABM) निर्देश समुच्चय की शुरुआत की POPCNT 2007 में SSE4a एक्सटेंशन के भाग के रूप में निर्देश।
  • इण्टेल कोर प्रोसेसर पेश किया गया POPCNT SSE4.2 इंस्ट्रक्शन सेट एक्सटेंशन के साथ निर्देश, पहली बार नेहलेम (माइक्रोआर्किटेक्चर)-आधारित कोर i7 प्रोसेसर में उपलब्ध है, जो नवंबर 2008 में जारी किया गया था।
  • एआरएम वास्तुकला की शुरुआत की गई VCNT एआरएम एडवांस्ड SIMD (NEON (निर्देश सेट)) एक्सटेंशन के भाग के रूप में निर्देश।
  • RISC-वी ी वास्तुकला की शुरुआत की गई PCNT बिट मैनिपुलेशन (बी) एक्सटेंशन के भाग के रूप में निर्देश।[35]


यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Warren Jr., Henry S. (2013) [2002]. Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. pp. 81–96. ISBN 978-0-321-84268-8. 0-321-84268-5.
  2. ↑ Knuth, Donald Ervin (2009). "Bitwise tricks & techniques; Binary Decision Diagrams". The Art of Computer Programming. Vol. 4, Fascicle 1. Addison–Wesley Professional. ISBN 978-0-321-58050-4. (NB. Draft of Fascicle 1b available for download.)
  3. ↑ 3.0 3.1 Hewlett-Packard HP-16C Computer Scientist Owner's Handbook (PDF). Hewlett-Packard Company. April 1982. 00016-90001. Archived (PDF) from the original on 2017-03-28. Retrieved 2017-03-28.
  4. ↑ [1], written in Fōrmulæ. The Fōrmulæ wiki. Retrieved 2019-09-30.
  5. ↑ A solution to the task Population count. Retrieved 2019-09-30.
  6. ↑ Rosetta Code. Retrieved 2019-09-30.
  7. ↑ Thompson, Thomas M. (1983). From Error-Correcting Codes through Sphere Packings to Simple Groups. The Carus Mathematical Monographs #21. The Mathematical Association of America. p. 33.
  8. ↑ Glaisher, James Whitbread Lee (1899). "On the residue of a binomial-theorem coefficient with respect to a prime modulus". The Quarterly Journal of Pure and Applied Mathematics. 30: 150–156. (NB. See in particular the final paragraph of p. 156.)
  9. ↑ Reed, Irving Stoy (1954). "A Class of Multiple-Error-Correcting Codes and the Decoding Scheme". IRE Professional Group on Information Theory. Institute of Radio Engineers (IRE). PGIT-4: 38–49.
  10. ↑ Cohen, Gérard D.; Lobstein, Antoine; Naccache, David; Zémor, Gilles (1998). "How to improve an exponentiation black-box". In Nyberg, Kaisa (ed.). Advances in Cryptology – EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 – June 4, 1998, Proceeding. Lecture Notes in Computer Science. Vol. 1403. Springer. pp. 211–220. doi:10.1007/BFb0054128.
  11. ↑ Stoica, I.; Morris, R.; Liben-Nowell, D.; Karger, D. R.; Kaashoek, M. F.; Dabek, F.; Balakrishnan, H. (February 2003). "Chord: a scalable peer-to-peer lookup protocol for internet applications". IEEE/ACM Transactions on Networking. 11 (1): 17–32. doi:10.1109/TNET.2002.808407. S2CID 221276912. Section 6.3: "In general, the number of fingers we need to follow will be the number of ones in the binary representation of the distance from node to query."
  12. ↑ 12.0 12.1 SPARC International, Inc. (1992). "A.41: Population Count. Programming Note". The SPARC architecture manual: version 8 (Version 8 ed.). Englewood Cliffs, New Jersey, USA: Prentice Hall. pp. 231. ISBN 0-13-825001-4.
  13. ↑ Blaxell, David (1978). Hogben, David; Fife, Dennis W. (eds.). "Record linkage by bit pattern matching". Computer Science and Statistics--Tenth Annual Symposium on the Interface. NBS Special Publication. U.S. Department of Commerce / National Bureau of Standards. 503: 146–156.
  14. ↑ Wegner, Peter (May 1960). "A technique for counting ones in a binary computer". Communications of the ACM. 3 (5): 322. doi:10.1145/367236.367286. S2CID 31683715.
  15. ↑ Muła, Wojciech; Kurz, Nathan; Lemire, Daniel (January 2018). "Faster Population Counts Using AVX2 Instructions". Computer Journal. 61 (1): 111–120. arXiv:1611.07612. doi:10.1093/comjnl/bxx046. S2CID 540973.
  16. ↑ Stern & Mahmoud, Communications System Design, Prentice Hall, 2004, p 477ff.
  17. ↑ "GCC 3.4 Release Notes". GNU Project.
  18. ↑ "LLVM 1.5 Release Notes". LLVM Project.
  19. ↑ "What's New In Python 3.10". python.org.
  20. ↑ "GHC 7.4.1 release notes". GHC documentation.
  21. ↑ "Chapter 12.11. Bit Functions — MySQL 5.0 Reference Manual".
  22. ↑ Metcalf, Michael; Reid, John; Cohen, Malcolm (2011). Modern Fortran Explained. Oxford University Press. p. 380. ISBN 978-0-19-960142-4.
  23. ↑ Schwartz, Jake; Grevelle, Rick (2003-10-20) [1993]. HP16C Emulator Library for the HP48S/SX. 1.20 (1 ed.). Retrieved 2015-08-15. (NB. This library also works on the HP 48G/GX/G+. Beyond the feature set of the HP-16C this package also supports calculations for binary, octal, and hexadecimal floating-point numbers in scientific notation in addition to the usual decimal floating-point numbers.)
  24. ↑ Bonin, Walter (2019) [2015]. WP 43S Owner's Manual (PDF). 0.12 (draft ed.). p. 135. ISBN 978-1-72950098-9. Retrieved 2019-08-05. [2] [3] (314 pages)
  25. ↑ Bonin, Walter (2019) [2015]. WP 43S Reference Manual (PDF). 0.12 (draft ed.). pp. xiii, 104, 115, 120, 188. ISBN 978-1-72950106-1. Retrieved 2019-08-05. [4] [5] (271 pages)
  26. ↑ Martin, Ángel M.; McClure, Greg J. (2015-09-05). "HP16C Emulator Module for the HP-41CX - User's Manual and QRG" (PDF). Archived (PDF) from the original on 2017-04-27. Retrieved 2017-04-27. (NB. Beyond the HP-16C feature set this custom library for the HP-41CX extends the functionality of the calculator by about 50 additional functions.)
  27. ↑ Martin, Ángel M. (2015-09-07). "HP-41: New HP-16C Emulator available". Archived from the original on 2017-04-27. Retrieved 2017-04-27.
  28. ↑ Thörngren, Håkan (2017-01-10). "Ladybug Documentation" (release 0A ed.). Retrieved 2017-01-29. [6]
  29. ↑ "New HP-41 module available: Ladybug". 2017-01-10. Archived from the original on 2017-01-29. Retrieved 2017-01-29.
  30. ↑ Dale, Paul; Bonin, Walter (2012) [2008]. "WP 34S Owner's Manual" (PDF) (3.1 ed.). Retrieved 2017-04-27.
  31. ↑ Bonin, Walter (2015) [2008]. WP 34S Owner's Manual (3.3 ed.). ISBN 978-1-5078-9107-0.
  32. ↑ "Free Pascal documentation popcnt". Retrieved 2019-12-07.
  33. ↑ "JDK-6378821: bitCount() should use POPC on SPARC processors and AMD+10h". Java bug database. 2006-01-30.
  34. ↑ Blackfin Instruction Set Reference (Preliminary ed.). Analog Devices. 2001. pp. 8–24. Part Number 82-000410-14.
  35. ↑ Wolf, Claire (2019-03-22). "RISC-V "B" Bit Manipulation Extension for RISC-V, Draft v0.37" (PDF). Github.


अग्रिम पठन


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=हैमिंग_वेट&oldid=223048’