जावा में यह बिट हेरफेर कैसे काम करता है?

Question

मैं देख रहा था कि जावा कैसे int की बिट्स सेट करता है।
मैंने अपना इरादा कुछ इस तरह सरल में था (जो मुझे लगता है कि सही है):

public static int bitCount(int number){ 
     final int MASK = 0x1; 
     int count = 0; 

     for(int i = 0; i < 32; i++){ 
      if(((number >>> i) & MASK) == MASK){ 
       count++; 
      } 
     } 
     return count; 
    } 

इसके बजाय मैं एक विधि है कि मैं बिल्कुल पता नहीं क्या कर रहा है है पाया (मेरे लिए जादू की तरह लगता है):

i = i - ((i >>> 1) & 0x55555555); 
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); 
i = (i + (i >>> 4)) & 0x0f0f0f0f; 
i = i + (i >>> 8); 
i = i + (i >>> 16); 
return i & 0x3f; 

क्या कोई यह समझने में सहायता कर सकता है कि यह क्या करता है और एक साधारण कार्य जैसा कि मैंने पहली बार सोचा था कि यह बुरा विचार हो सकता है?

Answer 1

ज़रूर

i = i - ((i >>> 1) & 0x55555555); 

5 के बिट पैटर्न 0101 (चार बिट) है, इसलिए मुखौटा बिट पैटर्न 01 सोलह गुना की पुनरावृत्ति है। यह पंक्ति संख्या की प्रत्येक दो-बिट जोड़ी में बिट्स की संख्या की गणना करती है। यदि आप दो-बिट जोड़े पर विचार करते हैं, तो (i >>> 1) & 0x1 निम्न-आदेश स्थिति में उच्च-आदेश बिट प्राप्त करता है। अब, वहाँ चार संभावित दो-बिट पैटर्न

00 ~> 00 - 00 = 00 
01 ~> 01 - 00 = 01 
10 ~> 10 - 01 = 01 
11 ~> 11 - 01 = 10 

हैं और प्रत्येक दो-बिट जोड़ी अब बिट्स मूल उन स्थितियों में किया था की संख्या में शामिल है।

i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); 

अगला, हम प्रत्येक चार-बिट समूह (उर्फ निबल) में मौजूद बिट्स को गिनते हैं। 0x3 = 0011(b) के साथ एक नींबू को मास्क करके, हमें निचले क्रम में बिट्स की गिनती मिलती है, और (i >>> 2) & 0x3 को निबेल के दो बिट्स उच्च क्रम से गिनती मिलती है। ये गणना अब जोड़ दी गई है। चूंकि प्रत्येक गिनती 2 से अधिक थी, इसलिए योग अधिकतम 4 है, इसलिए नींबू नहीं छोड़ता है।

i = (i + (i >>> 4)) & 0x0f0f0f0f; 

अब प्रत्येक ऑक्टेट में बिट्स गिना जाता है। प्रत्येक निबल में उस स्थान पर मूल में सेट बिट्स की गिनती होती है। चार बिट्स द्वारा दाएं स्थानांतरित करने से प्रत्येक स्थान पर निचले क्रम में निबेल के उच्च क्रम से गिनती होती है, ये जोड़े जाते हैं। फिर हमने निचले क्रम के निचले भाग के निचले क्रम में निचले क्रम में निगलना को भी स्थानांतरित कर दिया, जिसे & 0x0f0f0f0f द्वारा मुखौटा किया गया है। चूंकि प्रत्येक ऑक्टेट में अधिकतम आठ बिट सेट हो सकते हैं, इसलिए गिनती ऑक्टेट के निचले क्रम को नुकीले नहीं छोड़ती है।

i = i + (i >>> 8); 

अब हम आसन्न ऑक्टेट्स के जोड़े की गणना जोड़ते हैं।

i = i + (i >>> 16); 

अब हम उच्च क्रम में दो ऑक्टेक्ट्स और कम ऑर्डर दो में गणना के योग जोड़ते हैं।

return i & 0x3f; 

अंत में, सबसे कम क्रम ओकटेट को छोड़कर सभी ओक्टेट्स, बाहर से छुपाया जाता है के बाद से उच्च आदेश ओक्टेट्स अभी भी मध्यवर्ती मायने रखता है निहित।

आपके सरल कार्यान्वयन को खराब क्यों माना जा सकता है इसका कारण प्रदर्शन है। घुलनशील बिट-हैक कम परिचालनों और कोई शाखाओं का उपयोग नहीं करता है, इसलिए यह तेज़ है। हालांकि, यह गलत होने के लिए कहीं अधिक आसान है।

एक int (या long) में सेट बिट्स गिनती करने के लिए एक और साफ रास्ता

public static int bitCount(int n) { 
    int count = 0; 
    while(n != 0) { 
     ++count; 
     n = n & (n-1); 
    } 
    return count; 
} 

काम करता है ऐसा इसलिए है क्योंकि n = n & (n-1)n में अंतिम सेट बिट को साफ करता है और बाकी अछूता सब कुछ छोड़ देता है। n के बिट पैटर्न

...100...0 

साथ समाप्त होता है तो n-1 के बिट पैटर्न

...011...1 

है और n में पिछले 1-बिट से पहले बिट्स ही हैं। जावा में, यह नकारात्मक संख्याओं के लिए भी काम करने की गारंटी है क्योंकि पूर्णांक ओवरफ़्लो में लपेटने वाले अर्थशास्त्र हैं, इसलिए n = Integer.MIN_VALUE, बिट पैटर्न 100...0 और n - 1Integer.MAX_VALUE बिट पैटर्न 011...1 के साथ Integer.MAX_VALUE बन जाता है।

Answer 2

कूल विधि केवल तभी काम करती है जब कंप्यूटर के पास int के मानों की सीमित सीमा होती है। यह अनंत सीमा (जैसे BigInteger) के लिए इतनी आसानी से काम नहीं करेगा (और इसलिए अन्य शांत बिट्स एल्गोरिदम) क्योंकि आपको गणना से पहले सभी आवश्यक मास्कों को जानने की आवश्यकता है।

किसी भी मामले में

, आप पढ़ सकते हैं कि यह कैसे के माध्यम से काम करता है: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

यह इस अध्याय के नीचे स्थित है।