हैमिंग वेट: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (8 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Number of nonzero symbols in a string}} | {{Short description|Number of nonzero symbols in a string}} | ||
स्ट्रिंग का '''हैमिंग | स्ट्रिंग का '''हैमिंग वेट''' (कंप्यूटर विज्ञान) उन प्रतीकों की संख्या है जो प्रयुक्त [[वर्णमाला]] के शून्य-प्रतीक से भिन्न होते हैं। इस प्रकार यह समान लंबाई की पूर्ण-शून्य स्ट्रिंग से [[हैमिंग दूरी]] के सामान्य है। सबसे विशिष्ट स्थिति के लिए, [[ अंश |अंश]] की स्ट्रिंग, यह स्ट्रिंग में 1 की संख्या है, या किसी दिए गए नंबर की [[बाइनरी अंक प्रणाली]] का [[अंक योग]] और टैक्सीकैब ज्यामिति या ''ℓ''₁ बिट सदिश का मानदंड इस द्विआधारी स्थिति में, इसे जनसंख्या गणना भी कहा जाता है,<ref name="Warren_2013"/> पॉपकाउंट, पार्श्व में योग,<ref name="Knuth_2009"/> या बिट योग का उपयोग किया जाता है.<ref name="HP-16C_1982"/> | ||
{|class="wikitable" align="right" | {|class="wikitable" align="right" | ||
|+ | |+Examples | ||
! | !String | ||
! | !Hamming weight | ||
|- | |- | ||
|'''111'''0'''1''' | |'''111'''0'''1''' | ||
| Line 32: | Line 32: | ||
}} | }} | ||
|- | |- | ||
| class="thumbcaption" | A plot for the population count (Hamming weight for | | class="thumbcaption" | A plot for the population count (Hamming weight for binary numbers) for (decimal) numbers 0 to 256.<ref name="Rosetta_1"/><ref name="Rosetta_2"/><ref name="Rosetta_3"/> | ||
|} | |} | ||
== इतिहास और उपयोग == | == इतिहास और उपयोग == | ||
हैमिंग वेट का नाम [[रिचर्ड हैमिंग]] के नाम पर रखा गया है, चूँकि उन्होंने इस धारणा की उत्पत्ति नहीं की थी।<ref name="Thompson_1983"/> बाइनरी संख्याओं के हैमिंग वेट का उपयोग 1899 में जेम्स व्हिटब्रेड ली ग्लैशर द्वारा पास्कल के त्रिकोण की पंक्ति में गोल्ड के अनुक्रम के लिए सूत्र देने के लिए किया गया था।<ref name="Glaisher_1899"/> इरविंग एस. रीड ने 1954 में बाइनरी स्थिति में हैमिंग | हैमिंग वेट का नाम [[रिचर्ड हैमिंग]] के नाम पर रखा गया है, चूँकि उन्होंने इस धारणा की उत्पत्ति नहीं की थी।<ref name="Thompson_1983"/> बाइनरी संख्याओं के हैमिंग वेट का उपयोग 1899 में जेम्स व्हिटब्रेड ली ग्लैशर द्वारा पास्कल के त्रिकोण की पंक्ति में गोल्ड के अनुक्रम के लिए सूत्र देने के लिए किया गया था।<ref name="Glaisher_1899"/> इरविंग एस. रीड ने 1954 में बाइनरी स्थिति में हैमिंग वेट के सामान्य अवधारणा प्रस्तुत की थी।<ref name="Reed_1954"/> | ||
हैमिंग वेट का उपयोग [[सूचना सिद्धांत]], [[कोडिंग सिद्धांत]] और [[क्रिप्टोग्राफी]] सहित कई विषयों में किया जाता है। हैमिंग वज़न के अनुप्रयोगों के उदाहरणों में सम्मिलित हैं: | हैमिंग वेट का उपयोग [[सूचना सिद्धांत]], [[कोडिंग सिद्धांत]] और [[क्रिप्टोग्राफी]] सहित कई विषयों में किया जाता है। हैमिंग वज़न के अनुप्रयोगों के उदाहरणों में सम्मिलित हैं: | ||
* वर्ग द्वारा मॉड्यूलर घातांक में, घातांक e के लिए आवश्यक मॉड्यूलर गुणन की संख्या लॉग है यही कारण है कि [[आरएसए (एल्गोरिदम)]] में प्रयुक्त | * वर्ग द्वारा मॉड्यूलर घातांक में, घातांक e के लिए आवश्यक मॉड्यूलर गुणन की संख्या लॉग है यही कारण है कि [[आरएसए (एल्गोरिदम)]] में प्रयुक्त सार्वेटिक कीज मान e को सामान्यतः कम हैमिंग वेट की संख्या के रूप में चुना जाता है।<ref name="CLNZ"/> | ||
*हैमिंग | *हैमिंग वेट [[कॉर्ड (वितरित हैश तालिका)]] में नोड्स के बीच पथ की लंबाई निर्धारित करता है।<ref name="Stoica_2003" /> | ||
*बायोमेट्रिक डेटाबेस में [[आईरिसकोड]] लुकअप सामान्यतः प्रत्येक संग्रहीत रिकॉर्ड के लिए हैमिंग दूरी की गणना करके कार्यान्वित किया जाता है। | *बायोमेट्रिक डेटाबेस में [[आईरिसकोड]] लुकअप सामान्यतः प्रत्येक संग्रहीत रिकॉर्ड के लिए हैमिंग दूरी की गणना करके कार्यान्वित किया जाता है। | ||
* [[बिटबोर्ड]] प्रतिनिधित्व का उपयोग करने वाले [[कंप्यूटर शतरंज|कंप्यूटर चेस]] प्रोग्राम में, बिटबोर्ड का हैमिंग | * [[बिटबोर्ड]] प्रतिनिधित्व का उपयोग करने वाले [[कंप्यूटर शतरंज|कंप्यूटर चेस]] प्रोग्राम में, बिटबोर्ड का हैमिंग वेट खेल में शेष दिए गए प्रकार के टुकड़ों की संख्या, या खिलाड़ी के टुकड़ों द्वारा नियंत्रित बोर्ड के वर्गों की संख्या देता है, और इसलिए यह महत्वपूर्ण योगदान है किसी पद के मूल्य के लिए शब्द का उपयोग किया जाता है। | ||
* हैमिंग वेट का उपयोग पहचान एफएफएस ffs(x) = pop(x ^ (x - 1)) का उपयोग करके पहले सेट को कुशलतापूर्वक खोजने के लिए किया जा सकता है। यह [[SPARC|स्पार्क]] जैसे प्लेटफ़ॉर्म पर उपयोगी है जिसमें हार्डवेयर हैमिंग वेट निर्देश हैं किन्तु कोई हार्डवेयर पहले सेट निर्देश नहीं खोजता है।<ref name="SPARC_1992" /><ref name="Warren_2013" /> | * हैमिंग वेट का उपयोग पहचान एफएफएस ffs(x) = pop(x ^ (x - 1)) का उपयोग करके पहले सेट को कुशलतापूर्वक खोजने के लिए किया जा सकता है। यह [[SPARC|स्पार्क]] जैसे प्लेटफ़ॉर्म पर उपयोगी है जिसमें हार्डवेयर हैमिंग वेट निर्देश हैं किन्तु कोई हार्डवेयर पहले सेट निर्देश नहीं खोजता है।<ref name="SPARC_1992" /><ref name="Warren_2013" /> | ||
*हैमिंग वेट ऑपरेशन की व्याख्या यूनरी अंक प्रणाली से [[बाइनरी संख्या]]ओं में रूपांतरण के रूप में की जा सकती है।<ref name="Blaxell_1978" /> | *हैमिंग वेट ऑपरेशन की व्याख्या यूनरी अंक प्रणाली से [[बाइनरी संख्या]]ओं में रूपांतरण के रूप में की जा सकती है।<ref name="Blaxell_1978" /> | ||
| Line 49: | Line 49: | ||
== कुशल कार्यान्वयन == | == कुशल कार्यान्वयन == | ||
क्रिप्टोग्राफी और अन्य अनुप्रयोगों में बिट सरणी की जनसंख्या गणना की अधिकांशतः आवश्यकता होती है। दो शब्दों a और b की हैमिंग दूरी की गणना a एक्स या b के हैमिंग | क्रिप्टोग्राफी और अन्य अनुप्रयोगों में बिट सरणी की जनसंख्या गणना की अधिकांशतः आवश्यकता होती है। दो शब्दों a और b की हैमिंग दूरी की गणना a एक्स या b के हैमिंग वेट के रूप में की जा सकती है।<ref name="Warren_2013"/> | ||
इसे कुशलतापूर्वक कैसे कार्यान्वित किया जाए इसकी समस्या का व्यापक अध्ययन किया गया है। इस प्रकार गणना के लिए एकल ऑपरेशन, या बिट वैक्टर पर समानांतर संचालन प्रोसेसर समर्थन हैं। जिन प्रोसेसरों में उन सुविधाओं की कमी है, उनके लिए ज्ञात सर्वोत्तम समाधान ट्री पैटर्न में गिनती जोड़ने पर आधारित हैं। उदाहरण के लिए, 16-बिट बाइनरी संख्या a = 0110 1100 1011 1010 में 1 बिट की संख्या गिनने के लिए, ये ऑपरेशन किए जा सकते हैं: | इसे कुशलतापूर्वक कैसे कार्यान्वित किया जाए इसकी समस्या का व्यापक अध्ययन किया गया है। इस प्रकार गणना के लिए एकल ऑपरेशन, या बिट वैक्टर पर समानांतर संचालन प्रोसेसर समर्थन हैं। जिन प्रोसेसरों में उन सुविधाओं की कमी है, उनके लिए ज्ञात सर्वोत्तम समाधान ट्री पैटर्न में गिनती जोड़ने पर आधारित हैं। उदाहरण के लिए, 16-बिट बाइनरी संख्या a = 0110 1100 1011 1010 में 1 बिट की संख्या गिनने के लिए, ये ऑपरेशन किए जा सकते हैं: | ||
| Line 230: | Line 230: | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
यदि अधिक मेमोरी उपयोग की अनुमति है, जिससे हम उपरोक्त विधियों की तुलना में हैमिंग | यदि अधिक मेमोरी उपयोग की अनुमति है, जिससे हम उपरोक्त विधियों की तुलना में हैमिंग वेट की तेजी से गणना कर सकते हैं। असीमित मेमोरी के साथ, हम आसानी से प्रत्येक 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 258: | Line 258: | ||
मुला एट अल.<ref name="Mula_2018"/> दिखाया गया है कि पॉपकाउंट 64b का वेक्टरकृत संस्करण समर्पित निर्देशों (उदाहरण के लिए, x64 प्रोसेसर पर पॉपसीएनटी) की तुलना में तेजी से चल सकता है। | मुला एट अल.<ref name="Mula_2018"/> दिखाया गया है कि पॉपकाउंट 64b का वेक्टरकृत संस्करण समर्पित निर्देशों (उदाहरण के लिए, x64 प्रोसेसर पर पॉपसीएनटी) की तुलना में तेजी से चल सकता है। | ||
==न्यूनतम | ==न्यूनतम वेट== | ||
[[त्रुटि-सुधार कोड]] या त्रुटि-सुधार कोडिंग में, न्यूनतम हैमिंग | [[त्रुटि-सुधार कोड]] या त्रुटि-सुधार कोडिंग में, न्यूनतम हैमिंग वेट, जिसे सामान्यतः न्यूनतम वेट ''w<sub>min</sub>'' कहा जाता है कोड का वेट सबसे कम वेट वाले गैर-शून्य कोड शब्द का होता है। किसी कोड शब्द का भार w शब्द में 1s की संख्या है। उदाहरण के लिए, शब्द 11001010 का भार 4 है। | ||
एक [[रैखिक ब्लॉक कोड]] में न्यूनतम वेट भी [[न्यूनतम हैमिंग दूरी]] (d<sub>min</sub>) है और कोड की त्रुटि सुधार क्षमता को परिभाषित करता है। यदि w<sub>min</sub>= n, फिर d<sub>min</sub>= n और कोड d<sub>min</sub>/2 त्रुटियाँ तक सही हो जाता है.<ref>Stern & Mahmoud, ''Communications System Design'', [[Prentice Hall]], 2004, p 477ff.</ref> | |||
== भाषा समर्थन == | == भाषा समर्थन == | ||
कुछ सी कंपाइलर आंतरिक कार्य प्रदान करते हैं जो बिट गिनती की सुविधा प्रदान करते हैं। उदाहरण के लिए, [[जीएनयू कंपाइलर संग्रह]] (अप्रैल 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"/> | ||
| Line 271: | Line 269: | ||
जावा में, बढ़ने योग्य बिट-सरणी डेटा संरचना {{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 में जारी पायथन 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>, गैर- | [[पायथन (प्रोग्रामिंग भाषा)]] में, <code>int</code> प्रकार में है <code>bit_count()</code> सेट बिट्स की संख्या गिनने की विधि यह कार्यक्षमता अक्टूबर 2021 में जारी पायथन 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 बिट्स की संख्या लौटाता है।) किसी भी स्थिति में पूर्णांक बिग्नम हो सकता है। | ||
[[ग्लासगो हास्केल कंपाइलर]] 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> पूर्णांक (या पूर्णांक सरणी) के | [[फोरट्रान 2008]] में मानक, आंतरिक, मौलिक कार्य है <code>popcnt</code> पूर्णांक (या पूर्णांक सरणी) के अन्दर गैर-शून्य बिट्स की संख्या वापस करता है।<ref name="Metcalf_2011"/> | ||
कुछ प्रोग्रामयोग्य वैज्ञानिक पॉकेट कैलकुलेटर सेट बिट्स की संख्या की गणना करने के लिए विशेष कमांड की सुविधा देते हैं, उदाहरण के लिए <code>#B</code> [[HP-16C|एचपी-16सी]] पर <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|एचपी-16सी]] पर <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"/> | ||
[[फ्रीपास्कल]] संस्करण 3.0 से पॉपसीएनटी प्रयुक्त करता है।<ref name="FPC docs"/> | [[फ्रीपास्कल]] संस्करण 3.0 से पॉपसीएनटी प्रयुक्त करता है।<ref name="FPC docs"/> | ||
== प्रोसेसर समर्थन == | == प्रोसेसर समर्थन == | ||
* 1960 के दशक में [[IBM STRETCH|आईबीएम स्ट्रेच]] कंप्यूटर ने सभी तार्किक परिचालनों के उप-उत्पाद के रूप में सेट बिट्स की संख्या के साथ-साथ अग्रणी शून्य की संख्या की गणना की थी।<ref name="Warren_2013"/> | * 1960 के दशक में [[IBM STRETCH|आईबीएम स्ट्रेच]] कंप्यूटर ने सभी तार्किक परिचालनों के उप-उत्पाद के रूप में सेट बिट्स की संख्या के साथ-साथ अग्रणी शून्य की संख्या की गणना की थी।<ref name="Warren_2013"/> | ||
| Line 289: | Line 285: | ||
* [[नियंत्रण डेटा निगम]] (सीडीसी) की [[सीडीसी 6000 श्रृंखला]] और सीडीसी साइबर या साइबर 70/170 श्रृंखला की मशीनों में जनसंख्या गणना निर्देश सम्मिलित हैं; 60-बिट मशीनों के लिए कम्पास में, इस निर्देश को इस प्रकार <code>CXi</code>. कोडित किया गया था | * [[नियंत्रण डेटा निगम]] (सीडीसी) की [[सीडीसी 6000 श्रृंखला]] और सीडीसी साइबर या साइबर 70/170 श्रृंखला की मशीनों में जनसंख्या गणना निर्देश सम्मिलित हैं; 60-बिट मशीनों के लिए कम्पास में, इस निर्देश को इस प्रकार <code>CXi</code>. कोडित किया गया था | ||
* 64-बिट स्पार्क संस्करण 9 आर्किटेक्चर परिभाषित करता है <code>POPC</code> निर्देश,<ref name="SPARC_1992" /><ref name="Warren_2013" /> किन्तु अधिकांश कार्यान्वयन इसे प्रयुक्त नहीं करते हैं, जिसके लिए ऑपरेटिंग सिस्टम द्वारा इसका अनुकरण करना आवश्यक होता है।<ref name="JDK_BitCount" /> | * 64-बिट स्पार्क संस्करण 9 आर्किटेक्चर परिभाषित करता है <code>POPC</code> निर्देश,<ref name="SPARC_1992" /><ref name="Warren_2013" /> किन्तु अधिकांश कार्यान्वयन इसे प्रयुक्त नहीं करते हैं, जिसके लिए ऑपरेटिंग सिस्टम द्वारा इसका अनुकरण करना आवश्यक होता है।<ref name="JDK_BitCount" /> | ||
*[[डोनाल्ड नुथ]] का मॉडल कंप्यूटर <nowiki>[[एमएमआईएक्स]]</nowiki> जो अपनी पुस्तक [[कंप्यूटर प्रोग्रामिंग की कला]] में एमआएक्स का स्थान लेने जा रहा है, उसमें है <code>SADD</code> 1999 से | *[[डोनाल्ड नुथ]] का मॉडल कंप्यूटर <nowiki>[[एमएमआईएक्स]]</nowiki> जो अपनी पुस्तक [[कंप्यूटर प्रोग्रामिंग की कला]] में एमआएक्स का स्थान लेने जा रहा है, उसमें है <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"/> | * [[एनालॉग डिवाइस]] के [[ Blackfin |ब्लैकफ़िन]] प्रोसेसर की सुविधा है <code>ONES</code> 32-बिट जनसंख्या गणना करने का निर्देश होता है।<ref name="AD_2001"/> | ||
*[[AMD|एएमडी]] के [[AMD K10|एएमडी K10]] आर्किटेक्चर ने उन्नत बिट मैनिपुलेशन (एबीएम) [[ निर्देश समुच्चय |निर्देश समुच्चय]] की प्रारंभ की <code>POPCNT</code> 2007 में [[SSE4a]] एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया है। | *[[AMD|एएमडी]] के [[AMD K10|एएमडी K10]] आर्किटेक्चर ने उन्नत बिट मैनिपुलेशन (एबीएम) [[ निर्देश समुच्चय |निर्देश समुच्चय]] की प्रारंभ की <code>POPCNT</code> 2007 में [[SSE4a|एसएसई4ए]] एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया है। | ||
* [[ इण्टेल कोर | इण्टेल कोर]] प्रोसेसर प्रस्तुत किया गया <code>POPCNT</code> | * [[ इण्टेल कोर | इण्टेल कोर]] प्रोसेसर प्रस्तुत किया गया <code>POPCNT</code> एसएसई4.2 इंस्ट्रक्शन सेट एक्सटेंशन के साथ निर्देश, पहली बार नेहलेम (माइक्रोआर्किटेक्चर)-आधारित [[कोर i7]] प्रोसेसर में उपलब्ध है, जो नवंबर 2008 में जारी किया गया था। | ||
* [[एआरएम वास्तुकला|एआरएम आर्किटेक्चर]] की प्रारंभ की गई <code>VCNT</code> [[एआरएम एडवांस्ड SIMD|एआरएम एडवांस्ड सिमड]] (नियोन (निर्देश सेट) एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया जाता है। | * [[एआरएम वास्तुकला|एआरएम आर्किटेक्चर]] की प्रारंभ की गई <code>VCNT</code> [[एआरएम एडवांस्ड SIMD|एआरएम एडवांस्ड सिमड]] (नियोन (निर्देश सेट) एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया जाता है। | ||
* [[ RISC-वी | आरआईएससी-वी]] | * [[ RISC-वी | आरआईएससी-वी]] आर्किटेक्चर की प्रारंभ की गई <code>PCNT</code> बिट मैनिपुलेशन (b) एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया जाता है।<ref name="RISC-V-B" /> | ||
== यह भी देखें == | == यह भी देखें == | ||
* दो पूरक | * दो पूरक | ||
| Line 352: | Line 346: | ||
<ref name="RISC-V-B">{{cite web |title=RISC-V "B" Bit Manipulation Extension for RISC-V, Draft v0.37 |date=2019-03-22 |author-last=Wolf |author-first=Claire |website=Github |url=https://github.com/riscv/riscv-bitmanip/blob/master/bitmanip-draft.pdf}}</ref> | <ref name="RISC-V-B">{{cite web |title=RISC-V "B" Bit Manipulation Extension for RISC-V, Draft v0.37 |date=2019-03-22 |author-last=Wolf |author-first=Claire |website=Github |url=https://github.com/riscv/riscv-bitmanip/blob/master/bitmanip-draft.pdf}}</ref> | ||
}} | }} | ||
==अग्रिम पठन== | ==अग्रिम पठन== | ||
* {{cite book |title=HAKMEM |title-link=HAKMEM |author-first1=Michael |author-last1=Beeler |author-first2=Ralph William |author-last2=Gosper |author-link2=Bill Gosper |author-first3=Richard C. |author-last3=Schroeppel |author-link3=Richard C. Schroeppel |contribution=compilation |contributor-first1=Richard C. |contributor-last1=Schroeppel |contributor-link1=Richard C. Schroeppel |contributor-last2=Orman |contributor-first2=Hilarie K. |date=1972-02-29 |publisher=[[MIT AI Lab|Artificial Intelligence Laboratory]], [[Massachusetts Institute of Technology]], Cambridge, Massachusetts, USA |id=MIT AI Memo 239 |type=report}} ([http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item169 Item 169]: Population count assembly code for the PDP/6-10.) | * {{cite book |title=HAKMEM |title-link=HAKMEM |author-first1=Michael |author-last1=Beeler |author-first2=Ralph William |author-last2=Gosper |author-link2=Bill Gosper |author-first3=Richard C. |author-last3=Schroeppel |author-link3=Richard C. Schroeppel |contribution=compilation |contributor-first1=Richard C. |contributor-last1=Schroeppel |contributor-link1=Richard C. Schroeppel |contributor-last2=Orman |contributor-first2=Hilarie K. |date=1972-02-29 |publisher=[[MIT AI Lab|Artificial Intelligence Laboratory]], [[Massachusetts Institute of Technology]], Cambridge, Massachusetts, USA |id=MIT AI Memo 239 |type=report}} ([http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item169 Item 169]: Population count assembly code for the PDP/6-10.) | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
* [http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count) Aggregate Magic Algorithms]. Optimized population count and other algorithms explained with sample code. | * [http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count) Aggregate Magic Algorithms]. Optimized population count and other algorithms explained with sample code. | ||
| Line 364: | Line 354: | ||
* [https://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer/ Best algorithm to count the number of set bits in a 32-bit integer?] - Stackoverflow | * [https://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer/ Best algorithm to count the number of set bits in a 32-bit integer?] - Stackoverflow | ||
{{DEFAULTSORT:Hamming Weight}} | {{DEFAULTSORT:Hamming Weight}} | ||
[[Category: | [[Category:CS1|Hamming Weight]] | ||
[[Category:Created On 10/07/2023]] | [[Category:Created On 10/07/2023|Hamming Weight]] | ||
[[Category:Lua-based templates|Hamming Weight]] | |||
[[Category:Machine Translated Page|Hamming Weight]] | |||
[[Category:Pages with reference errors|Hamming Weight]] | |||
[[Category:Pages with script errors|Hamming Weight]] | |||
[[Category:Short description with empty Wikidata description|Hamming Weight]] | |||
[[Category:Template documentation pages|Short description/doc]] | |||
[[Category:Templates Vigyan Ready|Hamming Weight]] | |||
[[Category:Templates that add a tracking category|Hamming Weight]] | |||
[[Category:Templates that generate short descriptions|Hamming Weight]] | |||
[[Category:Templates using TemplateData|Hamming Weight]] | |||
Latest revision as of 17:01, 25 July 2023
स्ट्रिंग का हैमिंग वेट (कंप्यूटर विज्ञान) उन प्रतीकों की संख्या है जो प्रयुक्त वर्णमाला के शून्य-प्रतीक से भिन्न होते हैं। इस प्रकार यह समान लंबाई की पूर्ण-शून्य स्ट्रिंग से हैमिंग दूरी के सामान्य है। सबसे विशिष्ट स्थिति के लिए, अंश की स्ट्रिंग, यह स्ट्रिंग में 1 की संख्या है, या किसी दिए गए नंबर की बाइनरी अंक प्रणाली का अंक योग और टैक्सीकैब ज्यामिति या ℓ₁ बिट सदिश का मानदंड इस द्विआधारी स्थिति में, इसे जनसंख्या गणना भी कहा जाता है,[1] पॉपकाउंट, पार्श्व में योग,[2] या बिट योग का उपयोग किया जाता है.[3]
| 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]
हैमिंग वेट का उपयोग सूचना सिद्धांत, कोडिंग सिद्धांत और क्रिप्टोग्राफी सहित कई विषयों में किया जाता है। हैमिंग वज़न के अनुप्रयोगों के उदाहरणों में सम्मिलित हैं:
- वर्ग द्वारा मॉड्यूलर घातांक में, घातांक e के लिए आवश्यक मॉड्यूलर गुणन की संख्या लॉग है यही कारण है कि आरएसए (एल्गोरिदम) में प्रयुक्त सार्वेटिक कीज मान e को सामान्यतः कम हैमिंग वेट की संख्या के रूप में चुना जाता है।[10]
- हैमिंग वेट कॉर्ड (वितरित हैश तालिका) में नोड्स के बीच पथ की लंबाई निर्धारित करता है।[11]
- बायोमेट्रिक डेटाबेस में आईरिसकोड लुकअप सामान्यतः प्रत्येक संग्रहीत रिकॉर्ड के लिए हैमिंग दूरी की गणना करके कार्यान्वित किया जाता है।
- बिटबोर्ड प्रतिनिधित्व का उपयोग करने वाले कंप्यूटर चेस प्रोग्राम में, बिटबोर्ड का हैमिंग वेट खेल में शेष दिए गए प्रकार के टुकड़ों की संख्या, या खिलाड़ी के टुकड़ों द्वारा नियंत्रित बोर्ड के वर्गों की संख्या देता है, और इसलिए यह महत्वपूर्ण योगदान है किसी पद के मूल्य के लिए शब्द का उपयोग किया जाता है।
- हैमिंग वेट का उपयोग पहचान एफएफएस ffs(x) = pop(x ^ (x - 1)) का उपयोग करके पहले सेट को कुशलतापूर्वक खोजने के लिए किया जा सकता है। यह स्पार्क जैसे प्लेटफ़ॉर्म पर उपयोगी है जिसमें हार्डवेयर हैमिंग वेट निर्देश हैं किन्तु कोई हार्डवेयर पहले सेट निर्देश नहीं खोजता है।[12][1]
- हैमिंग वेट ऑपरेशन की व्याख्या यूनरी अंक प्रणाली से बाइनरी संख्याओं में रूपांतरण के रूप में की जा सकती है।[13]
- बिट सरणी और तरंगिका वृक्ष जैसी कुछ संक्षिप्त डेटा संरचनाओं के कार्यान्वयन में किया जाता है।
कुशल कार्यान्वयन
क्रिप्टोग्राफी और अन्य अनुप्रयोगों में बिट सरणी की जनसंख्या गणना की अधिकांशतः आवश्यकता होती है। दो शब्दों a और b की हैमिंग दूरी की गणना a एक्स या b के हैमिंग वेट के रूप में की जा सकती है।[1]
इसे कुशलतापूर्वक कैसे कार्यान्वित किया जाए इसकी समस्या का व्यापक अध्ययन किया गया है। इस प्रकार गणना के लिए एकल ऑपरेशन, या बिट वैक्टर पर समानांतर संचालन प्रोसेसर समर्थन हैं। जिन प्रोसेसरों में उन सुविधाओं की कमी है, उनके लिए ज्ञात सर्वोत्तम समाधान ट्री पैटर्न में गिनती जोड़ने पर आधारित हैं। उदाहरण के लिए, 16-बिट बाइनरी संख्या a = 0110 1100 1011 1010 में 1 बिट की संख्या गिनने के लिए, ये ऑपरेशन किए जा सकते हैं:
| अभिव्यक्ति | बाइनरी | दशमलव | टिप्पणी | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
a
|
01 | 10 | 11 | 00 | 10 | 11 | 10 | 10 | 27834 | मूल क्रमांक |
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 | 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 | a से शेष बिट्स |
c = b0 + b1
|
01 | 01 | 10 | 00 | 01 | 10 | 01 | 01 | 1, 1, 2, 0, 1, 2, 1, 1 | प्रत्येक 2-बिट स्लाइस में 1s की गिनती |
d0 = (c >> 0) & 0011 0011 0011 0011
|
0001 | 0000 | 0010 | 0001 | 1, 0, 2, 1 | सी से हर दूसरी गिनती | ||||
d2 = (c >> 2) & 0011 0011 0011 0011
|
0001 | 0010 | 0001 | 0001 | 1, 2, 1, 1 | शेष की गणना c से की जाती है | ||||
e = d0 + d2
|
0010 | 0010 | 0011 | 0010 | 2, 2, 3, 2 | a के प्रत्येक 4-बिट स्लाइस में 1s की गिनती | ||||
f0 = (e >> 0) & 00001111 00001111
|
00000010 | 00000010 | 2, 2 | e से प्रत्येक अन्य गिनती | ||||||
f4 = (e >> 4) & 00001111 00001111
|
00000010 | 00000011 | 2, 3 | शेष की गिनती e से होती है | ||||||
g = f0 + f4
|
00000100 | 00000101 | 4, 5 | प्रत्येक 8-बिट स्लाइस में 1s की गिनती | ||||||
h0 = (g >> 0) & 0000000011111111
|
0000000000000101 | 5 | g से प्रत्येक अन्य गिनती | |||||||
h8 = (g >> 8) & 0000000011111111
|
0000000000000100 | 4 | शेष की गणना g से की जाती है | |||||||
i = h0 + h8
|
0000000000001001 | 9 | संपूर्ण 16-बिट शब्द में 1s की गिनती | |||||||
यहां, ऑपरेशन सी (प्रोग्रामिंग भाषा) के समान हैं X >> Y का अर्थ है X को Y बिट्स द्वारा दाईं ओर स्थानांतरित करना, X और Y का अर्थ है X और Y का बिटवाइज़, और + सामान्य जोड़ है। इस समस्या के लिए ज्ञात सर्वोत्तम एल्गोरिदम ऊपर चित्रित अवधारणा पर आधारित हैं और यहां दिए गए हैं:[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] दिखाया गया है कि पॉपकाउंट 64b का वेक्टरकृत संस्करण समर्पित निर्देशों (उदाहरण के लिए, x64 प्रोसेसर पर पॉपसीएनटी) की तुलना में तेजी से चल सकता है।
न्यूनतम वेट
त्रुटि-सुधार कोड या त्रुटि-सुधार कोडिंग में, न्यूनतम हैमिंग वेट, जिसे सामान्यतः न्यूनतम वेट wmin कहा जाता है कोड का वेट सबसे कम वेट वाले गैर-शून्य कोड शब्द का होता है। किसी कोड शब्द का भार w शब्द में 1s की संख्या है। उदाहरण के लिए, शब्द 11001010 का भार 4 है।
एक रैखिक ब्लॉक कोड में न्यूनतम वेट भी न्यूनतम हैमिंग दूरी (dmin) है और कोड की त्रुटि सुधार क्षमता को परिभाषित करता है। यदि wmin= n, फिर dmin= n और कोड dmin/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 में जारी पायथन 3.10 में प्रस्तुत की गई थी।[19] सामान्य लिस्प में, फ़ंक्शन logcount, गैर-ऋणात्मक पूर्णांक दिया गया है, इस प्रकार 1 बिट्स की संख्या लौटाता है। (ऋणात्मक पूर्णांकों के लिए यह 2 के पूरक संकेतन में 0 बिट्स की संख्या लौटाता है।) किसी भी स्थिति में पूर्णांक बिग्नम हो सकता है।
ग्लासगो हास्केल कंपाइलर 7.4 से प्रारंभ होकर, हास्केल (प्रोग्रामिंग भाषा) बेस पैकेज में है popCount फ़ंक्शन सभी प्रकार के उदाहरणों पर उपलब्ध है Bits कक्षा (से उपलब्ध है Data.Bits मापांक)।[20]
एसक्यूएल भाषा का मायएसक्यूएल संस्करण प्रदान करता है BIT_COUNT() मानक फ़ंक्शन के रूप में।[21]
फोरट्रान 2008 में मानक, आंतरिक, मौलिक कार्य है popcnt पूर्णांक (या पूर्णांक सरणी) के अन्दर गैर-शून्य बिट्स की संख्या वापस करता है।[22]
कुछ प्रोग्रामयोग्य वैज्ञानिक पॉकेट कैलकुलेटर सेट बिट्स की संख्या की गणना करने के लिए विशेष कमांड की सुविधा देते हैं, उदाहरण के लिए #B एचपी-16सी पर [3][23] और WP 43S,[24][25] #BITS[26][27]या BITSUM [28][29] एचपी-16सी एमुलेटर पर, और nBITS WP 34S पर होता है.[30][31]
फ्रीपास्कल संस्करण 3.0 से पॉपसीएनटी प्रयुक्त करता है।[32]
प्रोसेसर समर्थन
- 1960 के दशक में आईबीएम स्ट्रेच कंप्यूटर ने सभी तार्किक परिचालनों के उप-उत्पाद के रूप में सेट बिट्स की संख्या के साथ-साथ अग्रणी शून्य की संख्या की गणना की थी।[1]
- क्रे सुपरकंप्यूटर में प्रारंभ में जनसंख्या गणना मशीन अनुदेश प्रदर्शित किया गया था, ऐसी अफवाह थी कि क्रिप्ट विश्लेषण अनुप्रयोगों के लिए अमेरिकी सरकार की राष्ट्रीय सुरक्षा एजेंसी द्वारा विशेष रूप से अनुरोध किया गया था।[1]
- नियंत्रण डेटा निगम (सीडीसी) की सीडीसी 6000 श्रृंखला और सीडीसी साइबर या साइबर 70/170 श्रृंखला की मशीनों में जनसंख्या गणना निर्देश सम्मिलित हैं; 60-बिट मशीनों के लिए कम्पास में, इस निर्देश को इस प्रकार
CXi. कोडित किया गया था - 64-बिट स्पार्क संस्करण 9 आर्किटेक्चर परिभाषित करता है
POPCनिर्देश,[12][1] किन्तु अधिकांश कार्यान्वयन इसे प्रयुक्त नहीं करते हैं, जिसके लिए ऑपरेटिंग सिस्टम द्वारा इसका अनुकरण करना आवश्यक होता है।[33] - डोनाल्ड नुथ का मॉडल कंप्यूटर [[एमएमआईएक्स]] जो अपनी पुस्तक कंप्यूटर प्रोग्रामिंग की कला में एमआएक्स का स्थान लेने जा रहा है, उसमें है
SADD1999 से निर्देशSADD a,b,cसभी बिट्स को गिनता है जो b में 1 और c में 0 हैं और परिणाम को a में लिखता है। - 1999 में जारी कॉम्पैक का अल्फा 21264A, पहला अल्फा श्रृंखला सीपीयू डिज़ाइन था जिसमें काउंट एक्सटेंशन था (
CIX). - एनालॉग डिवाइस के ब्लैकफ़िन प्रोसेसर की सुविधा है
ONES32-बिट जनसंख्या गणना करने का निर्देश होता है।[34] - एएमडी के एएमडी K10 आर्किटेक्चर ने उन्नत बिट मैनिपुलेशन (एबीएम) निर्देश समुच्चय की प्रारंभ की
POPCNT2007 में एसएसई4ए एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया है। - इण्टेल कोर प्रोसेसर प्रस्तुत किया गया
POPCNTएसएसई4.2 इंस्ट्रक्शन सेट एक्सटेंशन के साथ निर्देश, पहली बार नेहलेम (माइक्रोआर्किटेक्चर)-आधारित कोर i7 प्रोसेसर में उपलब्ध है, जो नवंबर 2008 में जारी किया गया था। - एआरएम आर्किटेक्चर की प्रारंभ की गई
VCNTएआरएम एडवांस्ड सिमड (नियोन (निर्देश सेट) एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया जाता है। - आरआईएससी-वी आर्किटेक्चर की प्रारंभ की गई
PCNTबिट मैनिपुलेशन (b) एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया जाता है।[35]
यह भी देखें
- दो पूरक
- फैन आउट
संदर्भ
- ↑ 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.
- ↑ 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.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.
- ↑ [1], written in Fōrmulæ. The Fōrmulæ wiki. Retrieved 2019-09-30.
- ↑ A solution to the task Population count. Retrieved 2019-09-30.
- ↑ Rosetta Code. Retrieved 2019-09-30.
- ↑ 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.
- ↑ 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.)
- ↑ 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.
- ↑ 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.
- ↑ 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.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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ Stern & Mahmoud, Communications System Design, Prentice Hall, 2004, p 477ff.
- ↑ "GCC 3.4 Release Notes". GNU Project.
- ↑ "LLVM 1.5 Release Notes". LLVM Project.
- ↑ "What's New In Python 3.10". python.org.
- ↑ "GHC 7.4.1 release notes". GHC documentation.
- ↑ "Chapter 12.11. Bit Functions — MySQL 5.0 Reference Manual".
- ↑ Metcalf, Michael; Reid, John; Cohen, Malcolm (2011). Modern Fortran Explained. Oxford University Press. p. 380. ISBN 978-0-19-960142-4.
- ↑ 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.)
- ↑ 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)
- ↑ 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)
- ↑ 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.)
- ↑ 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.
- ↑ Thörngren, Håkan (2017-01-10). "Ladybug Documentation" (release 0A ed.). Retrieved 2017-01-29. [6]
- ↑ "New HP-41 module available: Ladybug". 2017-01-10. Archived from the original on 2017-01-29. Retrieved 2017-01-29.
- ↑ Dale, Paul; Bonin, Walter (2012) [2008]. "WP 34S Owner's Manual" (PDF) (3.1 ed.). Retrieved 2017-04-27.
- ↑ Bonin, Walter (2015) [2008]. WP 34S Owner's Manual (3.3 ed.). ISBN 978-1-5078-9107-0.
- ↑ "Free Pascal documentation popcnt". Retrieved 2019-12-07.
- ↑ "JDK-6378821: bitCount() should use POPC on SPARC processors and AMD+10h". Java bug database. 2006-01-30.
- ↑ Blackfin Instruction Set Reference (Preliminary ed.). Analog Devices. 2001. pp. 8–24. Part Number 82-000410-14.
- ↑ Wolf, Claire (2019-03-22). "RISC-V "B" Bit Manipulation Extension for RISC-V, Draft v0.37" (PDF). Github.
अग्रिम पठन
- Schroeppel, Richard C.; Orman, Hilarie K. (1972-02-29). "compilation". HAKMEM. By Beeler, Michael; Gosper, Ralph William; Schroeppel, Richard C. (report). Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA. MIT AI Memo 239. (Item 169: Population count assembly code for the PDP/6-10.)
बाहरी संबंध
- Aggregate Magic Algorithms. Optimized population count and other algorithms explained with sample code.
- Bit Twiddling Hacks Several algorithms with code for counting bits set.
- Necessary and Sufficient - by Damien Wintour - Has code in C# for various Hamming Weight implementations.
- Best algorithm to count the number of set bits in a 32-bit integer? - Stackoverflow
