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

Revision as of 15:17, 19 July 2023

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

उदाहरण
स्ट्रिंग	हैमिंग वजन
11101	4
11101000	4
00000000	0
678012340567	10

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

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

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

वर्ग द्वारा मॉड्यूलर घातांक में, घातांक e के लिए आवश्यक मॉड्यूलर गुणन की संख्या लॉग है यही कारण है कि आरएसए (एल्गोरिदम) में प्रयुक्त सार्वजनिक कीज मान e को सामान्यतः कम हैमिंग वजन की संख्या के रूप में चुना जाता है।^[7]
हैमिंग वजन कॉर्ड (वितरित हैश तालिका) में नोड्स के बीच पथ की लंबाई निर्धारित करता है।^[8]
बायोमेट्रिक डेटाबेस में आईरिसकोड लुकअप सामान्यतः प्रत्येक संग्रहीत रिकॉर्ड के लिए हैमिंग दूरी की गणना करके कार्यान्वित किया जाता है।
बिटबोर्ड प्रतिनिधित्व का उपयोग करने वाले कंप्यूटर चेस प्रोग्राम में, बिटबोर्ड का हैमिंग वजन खेल में शेष दिए गए प्रकार के टुकड़ों की संख्या, या खिलाड़ी के टुकड़ों द्वारा नियंत्रित बोर्ड के वर्गों की संख्या देता है, और इसलिए यह महत्वपूर्ण योगदान है किसी पद के मूल्य के लिए शब्द का उपयोग किया जाता है।
हैमिंग वेट का उपयोग पहचान एफएफएस ffs(x) = pop(x ^ (x - 1)) का उपयोग करके पहले सेट को कुशलतापूर्वक खोजने के लिए किया जा सकता है। यह स्पार्क जैसे प्लेटफ़ॉर्म पर उपयोगी है जिसमें हार्डवेयर हैमिंग वेट निर्देश हैं किन्तु कोई हार्डवेयर पहले सेट निर्देश नहीं खोजता है।^[9]^[1]
हैमिंग वेट ऑपरेशन की व्याख्या यूनरी अंक प्रणाली से बाइनरी संख्याओं में रूपांतरण के रूप में की जा सकती है।^[10]
बिट सरणी और तरंगिका वृक्ष जैसी कुछ संक्षिप्त डेटा संरचनाओं के कार्यान्वयन में किया जाता है।

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

क्रिप्टोग्राफी और अन्य अनुप्रयोगों में बिट सरणी की जनसंख्या गणना की अधिकांशतः आवश्यकता होती है। दो शब्दों 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 में वर्णित किया था,^[11] 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;
    }
}

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

न्यूनतम वजन

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

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

भाषा समर्थन

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

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 में प्रस्तुत की गई थी।^[16] सामान्य लिस्प में, फ़ंक्शन logcount, गैर-ऋणात्मक पूर्णांक दिया गया है, इस प्रकार 1 बिट्स की संख्या लौटाता है। (ऋणात्मक पूर्णांकों के लिए यह 2 के पूरक संकेतन में 0 बिट्स की संख्या लौटाता है।) किसी भी स्थिति में पूर्णांक बिग्नम हो सकता है।

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

एसक्यूएल भाषा का मायएसक्यूएल संस्करण प्रदान करता है BIT_COUNT() मानक फ़ंक्शन के रूप में।^[18]

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

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

फ्रीपास्कल संस्करण 3.0 से पॉपसीएनटी प्रयुक्त करता है।^[29]

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

1960 के दशक में आईबीएम स्ट्रेच कंप्यूटर ने सभी तार्किक परिचालनों के उप-उत्पाद के रूप में सेट बिट्स की संख्या के साथ-साथ अग्रणी शून्य की संख्या की गणना की थी।^[1]
क्रे सुपरकंप्यूटर में प्रारंभ में जनसंख्या गणना मशीन अनुदेश प्रदर्शित किया गया था, ऐसी अफवाह थी कि क्रिप्ट विश्लेषण अनुप्रयोगों के लिए अमेरिकी सरकार की राष्ट्रीय सुरक्षा एजेंसी द्वारा विशेष रूप से अनुरोध किया गया था।^[1]
नियंत्रण डेटा निगम (सीडीसी) की सीडीसी 6000 श्रृंखला और सीडीसी साइबर या साइबर 70/170 श्रृंखला की मशीनों में जनसंख्या गणना निर्देश सम्मिलित हैं; 60-बिट मशीनों के लिए कम्पास में, इस निर्देश को इस प्रकार CXi. कोडित किया गया था
64-बिट स्पार्क संस्करण 9 आर्किटेक्चर परिभाषित करता है POPC निर्देश,^[9]^[1] किन्तु अधिकांश कार्यान्वयन इसे प्रयुक्त नहीं करते हैं, जिसके लिए ऑपरेटिंग सिस्टम द्वारा इसका अनुकरण करना आवश्यक होता है।^[30]
डोनाल्ड नुथ का मॉडल कंप्यूटर [[एमएमआईएक्स]] जो अपनी पुस्तक कंप्यूटर प्रोग्रामिंग की कला में एमआएक्स का स्थान लेने जा रहा है, उसमें है SADD 1999 से निर्देश SADD a,b,c सभी बिट्स को गिनता है जो b में 1 और c में 0 हैं और परिणाम को a में लिखता है।
1999 में जारी कॉम्पैक का अल्फा 21264A, पहला अल्फा श्रृंखला सीपीयू डिज़ाइन था जिसमें काउंट एक्सटेंशन था (CIX).
एनालॉग डिवाइस के ब्लैकफ़िन प्रोसेसर की सुविधा है ONES 32-बिट जनसंख्या गणना करने का निर्देश होता है।^[31]
एएमडी के एएमडी K10 आर्किटेक्चर ने उन्नत बिट मैनिपुलेशन (एबीएम) निर्देश समुच्चय की प्रारंभ की POPCNT 2007 में एसएसई4ए एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया है।
इण्टेल कोर प्रोसेसर प्रस्तुत किया गया POPCNT एसएसई4.2 इंस्ट्रक्शन सेट एक्सटेंशन के साथ निर्देश, पहली बार नेहलेम (माइक्रोआर्किटेक्चर)-आधारित कोर i7 प्रोसेसर में उपलब्ध है, जो नवंबर 2008 में जारी किया गया था।
एआरएम आर्किटेक्चर की प्रारंभ की गई VCNT एआरएम एडवांस्ड सिमड (नियोन (निर्देश सेट) एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया जाता है।
आरआईएससी-वी आर्किटेक्चर की प्रारंभ की गई PCNT बिट मैनिपुलेशन (b) एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया जाता है।^[32]

यह भी देखें

दो पूरक
फैन आउट

संदर्भ

↑ ^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.
↑ 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."
↑ ^9.0 ^9.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. [1] [2] (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. [3] [4] (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. [5]
↑ "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.

Cite error: <ref> tag with name "Rosetta_1" defined in <references> is not used in prior text.
Cite error: <ref> tag with name "Rosetta_2" defined in <references> is not used in prior text.

Cite error: <ref> tag with name "Rosetta_3" defined in <references> is not used in prior text.

अग्रिम पठन

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

[Warren_2013-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.

[Knuth_2009-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.)

[HP-16C_1982-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.

[Thompson_1983-4] 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_1899-5] 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_1954-6] 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.

[CLNZ-7] 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_2003-8] 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."

[SPARC_1992-9] 9.0 ^9.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_1978-10] 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_1960-11] 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.

[Mula_2018-12] 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.

[13] Stern & Mahmoud, Communications System Design, Prentice Hall, 2004, p 477ff.

[GCC-14] "GCC 3.4 Release Notes". GNU Project.

[LLVM-15] "LLVM 1.5 Release Notes". LLVM Project.

[16] "What's New In Python 3.10". python.org.

[GHC-17] "GHC 7.4.1 release notes". GHC documentation.

[MySQL_50-18] "Chapter 12.11. Bit Functions — MySQL 5.0 Reference Manual".

[Metcalf_2011-19] Metcalf, Michael; Reid, John; Cohen, Malcolm (2011). Modern Fortran Explained. Oxford University Press. p. 380. ISBN 978-0-19-960142-4.

[Schwartz_Grevelle_2003-20] 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_2019_OG-21] 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. [1] [2] (314 pages)

[Bonin_2019_RG-22] 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. [3] [4] (271 pages)

[Martin_McClure_2015-23] 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_2015-24] 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_2017-25] Thörngren, Håkan (2017-01-10). "Ladybug Documentation" (release 0A ed.). Retrieved 2017-01-29. [5]

[Thörngren_2017_2-26] "New HP-41 module available: Ladybug". 2017-01-10. Archived from the original on 2017-01-29. Retrieved 2017-01-29.

[Bonin_2012-27] Dale, Paul; Bonin, Walter (2012) [2008]. "WP 34S Owner's Manual" (PDF) (3.1 ed.). Retrieved 2017-04-27.

[Bonin_2015-28] Bonin, Walter (2015) [2008]. WP 34S Owner's Manual (3.3 ed.). ISBN 978-1-5078-9107-0.

[FPC_docs-29] "Free Pascal documentation popcnt". Retrieved 2019-12-07.

[JDK_BitCount-30] "JDK-6378821: bitCount() should use POPC on SPARC processors and AMD+10h". Java bug database. 2006-01-30.

[AD_2001-31] Blackfin Instruction Set Reference (Preliminary ed.). Analog Devices. 2001. pp. 8–24. Part Number 82-000410-14.

[RISC-V-B-32] Wolf, Claire (2019-03-22). "RISC-V "B" Bit Manipulation Extension for RISC-V, Draft v0.37" (PDF). Github.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 15:17, 19 July 2023

Contents

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

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

न्यूनतम वजन

भाषा समर्थन

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

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Revision as of 13:47, 19 July 2023 (view source) alpha>Manjuu No edit summary ← Older edit	Revision as of 15:17, 19 July 2023 (view source) alpha>Abhishek m (Abhishek moved page हथौड़ा चलाना वजन to हैमिंग वेट without leaving a redirect) Newer edit →
(No difference)

<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>

Anonymous

Search

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

Revision as of 15:17, 19 July 2023

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

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

न्यूनतम वजन

भाषा समर्थन

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

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories