8 बिट पूर्णांक में बिटवाई संक्रमणों की संख्या निर्धारित करना संभव है?

Question

मुझे इस पर कोई जादू नहीं लग रहा है, इसलिए मैं उम्मीद कर रहा था कि अगर कोई भी संभव हो तो यहां कोई भी हल्का प्रकाश डालने में सक्षम हो सकता है।

मैं 8 बिट पूर्णांक में बिटवाइज़ संक्रमण की संख्या को खोजने की कोशिश कर रहा हूं (पूर्णांक वास्तव में 32 बिट पूर्णांक है, लेकिन मैं केवल पहले 8 बिट्स का उपयोग कर रहा हूं) यह निर्धारित करने के लिए कि 8 बिट्स एक समान हैं (2 या कम संक्रमण)।

उदाहरण के लिए:

00100000 - two transitions - uniform 
00100001 - three transitions - not uniform 
10101010 - seven transitions - not uniform 
00000000 - no transitions - uniform 

वहाँ एक तेज़ तरीका प्रत्येक बिट के माध्यम से पाशन के अलावा अन्य संक्रमण की संख्या को खोजने के लिए है (वर्तमान में केवल समाधान मैं के साथ आ सकते हैं प्रत्येक बिट के माध्यम से पाशन है)?

Answer 1

आप x-या मान के साथ मान को एक बिट द्वारा स्थानांतरित कर सकते हैं और फिर परिणाम में 1 की संख्या गिन सकते हैं।

unsigned v = (x^(x>>1)) & 0x7F; 
unsigned count = 0; 
while (v) { 
    count++; 
    v &= (v - 1); 
} 

यह भी ध्यान रखें एक बाइट केवल 256 विन्यास हो सकता है, इसलिए गणना एक बार किया जा सकता है और 256 बाइट्स का एक बहुत छोटा तालिका में डाल दिया।

तुम सिर्फ यह जानना चाहते हैं वहाँ 2 या उससे कम परिवर्तन पाश unrolled किया जा सकता है चाहते हैं:

unsigned v = (x^(x >> 1)) & 0x7F; 
v &= v - 1; 
v &= v - 1; 
uniform = (v == 0); 

ध्यान दें कि यह गणना कैसे बड़ी संख्या है और आप उदाहरण के लिए सीधे एक का उपयोग कर सकते पर स्वतंत्र है 32-बिट अहस्ताक्षरित संख्या

Answer 2

वर्दी की अपनी परिभाषा के लिए (केवल एक चीज है कि बदलता है मुखौटा कि 0x7FFFFFFF हो जाता है), संख्या के रूप 00011111 या 11110000 में हो गया है। पूर्व पर विचार करें (शून्य के बाद शून्य)।

मूल्य में जोड़ें। यदि यह वर्दी है, तो इसका मतलब वास्तव में 1 बिट होगा, जिसका अर्थ है 2.

यह जांचने के लिए कि कोई मान दो की शक्ति है या नहीं, (x & (x - 1)) == 0 का उपयोग करें। कोड को छोटा करने के लिए हमें पिछले चरण में एक को जोड़ने की आवश्यकता नहीं है। इसके बजाए हम (x & (x + 1)) == 0

प्रारंभिक मान को न छोड़कर और उपरोक्त प्रक्रिया को दोहराकर अन्य मामले में इसे लागू करें।

#include <cstdio> 
bool isuniform(unsigned char x) { 
    unsigned char y = ~x; 
    return (x & (x + 1)) == 0 || (y & (y + 1)) == 0; 
} 
int main() { 
    printf("%d\n", isuniform(0)); // 00000000 
    printf("%d\n", isuniform(1)); // 00000001 
    printf("%d\n", isuniform(3)); // 00000011 
    printf("%d\n", isuniform(7)); // 00000111 
    printf("%d\n", isuniform(15)); // 00001111 
    printf("%d\n", isuniform(31)); // 00011111 
    printf("%d\n", isuniform(63)); // 00111111 
    printf("%d\n", isuniform(127)); // 01111111 
    printf("%d\n", isuniform(255)); // 11111111 
    printf("%d\n", isuniform(254)); // 11111110 
    printf("%d\n", isuniform(252)); // 11111100 
    printf("%d\n", isuniform(248)); // 11111000 
    printf("%d\n", isuniform(240)); // 11110000 
    printf("%d\n", isuniform(224)); // 11100000 
    printf("%d\n", isuniform(192)); // 11000000 
    printf("%d\n", isuniform(128)); // 10000000 
    //---------- 
    printf("%d\n", isuniform(2)); 
    printf("%d\n", isuniform(4)); 
    printf("%d\n", isuniform(50)); 
    printf("%d\n", isuniform(123)); 
    printf("%d\n", isuniform(129)); 
    printf("%d\n", isuniform(253)); 
    return 0; 
}