केवल बिटवाउंट ऑपरेटरों का उपयोग करके बिटकाउंट को कैसे कार्यान्वित करें?

Question

कार्य केवल बिटवाई ऑपरेटरों का उपयोग करके थोड़ा गिनती तर्क लागू करना है। मुझे यह ठीक काम कर रहा है, लेकिन मुझे आश्चर्य है कि कोई और अधिक सुरुचिपूर्ण दृष्टिकोण सुझा सकता है।

केवल बिटवाई ऑप्स की अनुमति है। नहीं "अगर", "के लिए" आदि

int x = 4; 

printf("%d\n", x & 0x1); 
printf("%d\n", (x >> 1) & 0x1); 
printf("%d\n", (x >> 2) & 0x1); 
printf("%d\n", (x >> 3) & 0x1); 

धन्यवाद।

Answer 1

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel से

unsigned int v; // count bits set in this (32-bit value) 
unsigned int c; // store the total here 

c = v - ((v >> 1) & 0x55555555); 
c = ((c >> 2) & 0x33333333) + (c & 0x33333333); 
c = ((c >> 4) + c) & 0x0F0F0F0F; 
c = ((c >> 8) + c) & 0x00FF00FF; 
c = ((c >> 16) + c) & 0x0000FFFF; 

संपादित: यह सच है कि यह थोड़ा अनुकूलित जो यह मुश्किल पढ़ा जा सकता है है। यह रूप में पढ़ने के लिए आसान है:

c = (v & 0x55555555) + ((v >> 1) & 0x55555555); 
c = (c & 0x33333333) + ((c >> 2) & 0x33333333); 
c = (c & 0x0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F); 
c = (c & 0x00FF00FF) + ((c >> 8) & 0x00FF00FF); 
c = (c & 0x0000FFFF) + ((c >> 16)& 0x0000FFFF); 

इन पाँच में से हर कदम, पड़ोसी बिट्स एक साथ विधि विभाजन में स्थित है और जीत है कहते हैं 1 के समूहों, तो 2 में और फिर 4 आदि ।

पहले चरण में हम बिट्स 0 और 1 जोड़ते हैं और परिणाम को दो बिट सेगमेंट 0-1 में डालते हैं, बिट्स 2 और 3 जोड़ते हैं और परिणाम को दो-बिट सेगमेंट 2-3 आदि में डाल देते हैं ...

दूसरे चरण में हम दो-बिट 0-1 और 2-3 जोड़ते हैं और परिणाम को चार-बिट 0-3 में डालते हैं, दो-बिट 4-5 और 6-7 जोड़ते हैं और परिणाम डालते हैं चार-बिट में 4-7 आदि ...

उदाहरण:

So if I have number 395 in binary 0000000110001011 (0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1) 
After the first step I have:  0000000101000110 (0+0 0+0 0+0 0+1 1+0 0+0 1+0 1+1) = 00 00 00 01 01 00 01 10 
In the second step I have:  0000000100010011 (00+00 00+01 01+00 01+10) = 0000 0001 0001 0011 
In the fourth step I have:  0000000100000100 ( 0000+0001  0001+0011 ) = 00000001 00000100 
In the last step I have:   0000000000000101 (  00000001+00000100  ) 

जो जो सही परिणाम है 5 के बराबर है,

Answer 2

कई दिलचस्प समाधान here।

समाधान के ऊपर भी बोरिंग कर रहे हैं, यहाँ एक सी पुनरावर्ती हालत परीक्षण या पाश की छूट दी गई है संस्करण है:

int z(unsigned n, int count); 
    int f(unsigned n, int count); 

    int (*pf[2])(unsigned n, int count) = { z,f }; 

    int f(unsigned n, int count) 
    { 
    return (*pf[n > 0])(n >> 1, count+(n & 1)); 
    } 

    int z(unsigned n, int count) 
    { 
    return count; 
    } 

    ... 
    printf("%d\n", f(my_number, 0)); 

Answer 3

मैं पूर्व परिकलित सरणी

uint8_t set_bits_in_byte_table[ 256 ]; 

का प्रयोग करेंगे i - इस तालिका में वें प्रविष्टि बाइट i में सेट बिट्स की संख्या संग्रहीत करती है, उदाहरण के लिए set_bits_in_byte_table[ 100 ] = 3 क्योंकि दशमलव 100 (= 0x64 = 0110-0100) के द्विआधारी प्रतिनिधित्व में 3 1 बिट्स हैं।

तब मैं कोशिश करेगा

size_t count_set_bits(uint32_t x) { 
    size_t count = 0; 
    uint8_t * byte_ptr = (uint8_t *) &x; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    return count; 
} 

Answer 4

यहाँ answer के लिए एक सरल उदाहरण दिया गया है:

a b c d  0 a b c  0 b 0 d  
&    &    + 
0 1 0 1  0 1 0 1  0 a 0 c 
-------  -------  ------- 
0 b 0 d  0 a 0 c  a+b c+d 

इसलिए हम वास्तव में 2 बिट्स स्टोर करने के लिए ए + बी और दुकान सी + डी के लिए 2 बिट्स की है। ए = 0, 1 इत्यादि, इसलिए 2 बिट्स जो हमें उनकी राशि को स्टोर करने की आवश्यकता है। अगले चरण में हमारे पास 2-बिट मानों को संग्रहीत करने के लिए 4 बिट होंगे।