ग्रे कोड वृद्धि फ़ंक्शन

Question

किसी बाहरी काउंटर या अन्य राज्य का उपयोग किए बिना, मैं कुशल फ़ंक्शन ढूंढ रहा हूं जो एक एन-बिट मान (32 बिट्स या वहां) लेता है और बाद में मान Gray code में देता है।

यही कारण है:

int fn(int x) 
{ 
    int y = gray_to_binary(x); 
    y = y + 1; 
    return binary_to_gray(y); 
} 

लेकिन जब binary_to_gray() समारोह तुच्छ है (x^(x >> 1)), इसी gray_to_binary() (log(n) पुनरावृत्तियों की एक पाश) सब पर इतना तुच्छ नहीं है।

शायद संचालन का एक और अधिक कुशल अनुक्रम है? या तो मानक प्रतिबिंबित ग्रे कोड के लिए, या इस समस्या के अनुरूप चुने गए किसी अन्य ग्रे कोड के लिए। (या एक अधिक कुशल रूपांतरण प्रदर्शन करने के लिए एक एक कोड आसान है कि द्विआधारी कन्वर्ट करने के लिए और फार्म ऊपर दिए गए उपयोग करने के लिए चयन करने के लिए है - मैं इस समस्या में दो संभव समाधान प्रकार भी देखें:

---

एक तरफ प्रतिबिंबित कोड के लिए बाइनरी), और दूसरा बाइनरी में रूपांतरण को स्थगित करना और एक विधि उत्पन्न करना है जो बाइनरी वृद्धि के उपयोग के बिना ग्रे कोड के माध्यम से चलता है।

बाद के मामले में, परिणामस्वरूप कोड को बाइनरी में परिवर्तित करना विशेष रूप से कठिन हो सकता है। यह व्यावहारिक शर्तों में नीचे की तरफ है, लेकिन यह अभी भी देखना दिलचस्प बात होगी।

---

अद्यतन: के बाद से यह बताया गया है कि ग्रे डिकोड केवल log(n) परिचालन (दो विभिन्न तकनीकों का उपयोग करने वाली) है, मैं यह पता लगाने की है कि अगर कितनी दूर पर एक सख्त सीमा है की कोशिश कर कुछ समय बिताया चीजों को सरल बनाया जा सकता है। प्रदर्शन करने के लिए अगले ऑपरेशन का निर्धारण करते समय सभी बिट्स पर विचार किया जाना चाहिए, अन्यथा 'माना' बिट्स बदलने में असफल हो जाएंगे और फ़ंक्शन दो मानों के बीच आ जाएगा। प्रदर्शन करने के लिए अगले ऑपरेशन को निर्धारित करने के लिए इनपुट को किसी भी तरह से एक प्रबंधित पैमाने पर संपीड़ित किया जाना चाहिए।

यह log(n-k) संचालन करने के लिए, एक 2 ^{कश्मीर} -entry lut (एक टिप्पणी से पता चलता है k=32) लघु कटौती पिछले k संचालन के लिए इस्तेमाल किया जा सकता है।

एक और तकनीक जो दिमाग में आई थी जो अक्सर चीजों को बहुत जल्दी कम कर सकती है गुणा और बिटमैस्क का संयोजन है। उदाहरण के लिए, समानता-आधारित एल्गोरिदम लागू करने के लिए parity की गणना करने के लिए।

गुणा-और-बिटमास्क दृष्टिकोण से, ऐसा लगता है कि ग्रे कोड का आविष्कार करने के लिए जगह हो सकती है जो संचालन के सेट को और भी सरल बनाता है ... लेकिन मुझे कल्पना नहीं है कि ऐसा कोई कोड ज्ञात है।

Answer 1

एक ग्रे कोड बढ़ाने के लिए एक सरल एल्गोरिथ्म:

gray_inc(x): 
    if parity of x is even: 
    return x xor 1 
    if parity of x is odd: 
    let y be the rightmost 1 bit in x 
    return x xor (y leftshift 1) 

एक्स की समता ढूँढना हे (लॉग (के)), जहां कश्मीर एक्स के bitlength है लेता है। हालांकि, उपरोक्त एल्गोरिदम में प्रत्येक चरण समानता बदलता है, इसलिए एक लूप में आप केवल विषम समानता संचालन को वैकल्पिक कर सकते हैं। (बेशक, वह ओपी आवश्यकता को विफल करता है जिसे कोई राज्य नहीं रखा जाता है, इसके लिए एक बिट राज्य की आवश्यकता होती है। इसके अलावा, नीचे देखें।)

वाई ढूँढना वाई (1) मानक बिट-हैक का उपयोग कर रहा है: y = x&-x, जहां - 2 पूरक पूरक ऑपरेटर है; आप इसे y = x and not (x - 1) के रूप में भी लिख सकते हैं।

आप समानता-वर्धित ग्रे कोड का उपयोग करने में भी सक्षम हो सकते हैं, जो एक विपरीत विपरीत बिट बिट के साथ ग्रे ग्रे कोड है (ताकि उन्नत कोड की समानता हमेशा विषम हो)। उस मामले में आप निम्नलिखित हे (1) एल्गोरिथ्म का उपयोग कर सकते हैं:

parity_gray_increment(x): 
    let y be the rightmost bit in x 
    return x xor ((y leftshift 1) or 1) 

उपरोक्त दोनों एल्गोरिदम में, मैं स्पष्टता के लिए अतिप्रवाह जांच बाहर छोड़ दिया गया है। ओवरफ्लो पर कोड चक्र बनाने के लिए y leftshift 1 if y is not the high-order bit, else y के साथ प्रतिस्थापित करें। (अधिकांश आर्किटेक्चर पर, परीक्षण if y leftshift 1 is not 0 हो सकता है।) वैकल्पिक रूप से, आप अपवाद फेंक सकते हैं या उस स्थिति में एक त्रुटि लौटा सकते हैं जब y बाईं ओर स्थानांतरित करने के लिए बहुत बड़ा है।

Answer 2

आपके द्वारा किए जाने वाले कार्यों के आधार पर मैं इसके साथ तीन तरीकों से जाऊंगा।

1) एक आम कार्य: एक ऐसा फ़ंक्शन लिखें जो व्यापक संभव ग्रेकोड मान को प्रबंधित करने के लिए आपको आवश्यक है।

inline UInt16 graycodeToBinary(UInt16 value) 
{ 
    value ^= (value >> 1); 
    value ^= (value >> 2); 
    value ^= (value >> 4); 
    value ^= (value >> 8); 
    return value; 
} 

इनपुट डेटा प्रकार और बदलाव के रूप में अगली शिफ्ट राशि जब तक जरूरत के बराबर या डेटा बिट्स की संख्या को पार कर जाएगा विस्तार: विधि है कि @harold कभी अधिक से अधिक परिवर्तन और xors का उपयोग कर सुझाव का पालन करें। इन निर्देशों को चलाने से भी एक लूप सेट अप करना और परीक्षण करना कम कुशल होगा। यह एक लुकअप विधि से थोड़ा धीमा होगा।

2) दो की प्रति शक्ति फ़ंक्शन ऊपर जैसा ही है लेकिन ग्रेकोड ToBinary_8, _16, _32 संस्करणों के साथ। अगर आप लॉट छोटे रूपांतरणों और कभी-कभी बहुत बड़े होते हैं तो लाभ का लाभ हो सकता है। यदि सी ++ ओवरलोडिंग का उपयोग स्वचालित रूप से आपके लिए उपयुक्त संस्करण चुन सकता है (और आप इसे कुछ टेम्पलेट मेटाप्रोग्रामिंग के साथ हास्यास्पद बना सकते हैं)।

3) लुकअप टेबल: यह तब तक एक अच्छा विचार प्रतीत होता है जब तक आप कैश व्यवहार पर विचार नहीं करते। यदि आप लुकअप टेबल का उपयोग अक्सर नहीं कर रहे हैं, तो यह उपर्युक्त विधि बनाम जटिल रूप से जटिल है। यदि आप लुकअप टेबल का उपयोग कर रहे हैं तो अक्सर यह आपके कैश व्यवहार को खराब कर देगा (बहुत सारे बिखरे हुए स्मृति के बड़े क्षेत्र में पढ़ते हैं)। अनुप्रयोगों का एक छोटा सा टुकड़ा है जहां यह बहुत तेज़ हो जाएगा। साथ ही, आपको लुकअप टेबल बनाना होगा, इसलिए आपके पास पहले से उपलब्ध ग्रेकोड_to_बिनरी के लिए फ़ंक्शन होने की संभावना है।

अंत में मुझे शायद ही कभी कुछ भी विकल्प के लिए उपयोग मिला है लेकिन विकल्प 1)। मैंने एक एम्बेडेड एप्लिकेशन देखा है जो लुकअप टेबल को इसके रोम में हार्ड-कोड किया गया है। यह ठीक था क्योंकि प्रोसेसर के पास कैश नहीं था।

सबसे पहले आप पूर्णांक की समता की जरूरत है:

Answer 3

मैं सी # में एक एल्गोरिथ्म काम करने के लिए लगता है कि क्रियान्वित किया है। मैं इसे एक ulong (64-बिट) के लिए लागू किया गया है, लेकिन आप आसानी से किसी भी वांछित उत्पादन के लिए इसे संशोधित कर सकते हैं:

public static ulong GetParity (ulong value) { 
    value ^= value >> 0x20; 
    value ^= value >> 0x10; 
    value ^= value >> 0x08; 
    value ^= value >> 0x04; 
    value &= 0x0f; 
    return (0x6996UL >> (int)value) & 0x01; 
} 

इसके बाद आप अगर समता भी है जांच करने की आवश्यकता (सेट बिट्स की संख्या भी है , यदि यह मामला है, तो आप बस अंतिम बिट स्वैप करें)। यदि समानता अजीब है, तो आप आमतौर पर कम से कम महत्वपूर्ण सेट बिट के बाईं ओर बिट को स्वैप करते हैं।यह निम्नलिखित विधि के साथ गणना की जा सकती:

public static ulong LeastSignificantBit (ulong value) { 
    return value&((~value)+0x01); 
} 

वहाँ एक सीमा मामला है: यदि कम से कम महत्वपूर्ण सेट बिट, अपने ग्रे कोड का सबसे बड़ा सा है यदि यह मामला है, तो आप निश्चित रूप से अदला-बदली नहीं कर सकते बाएं बिट, और आप बस अपना काउंटर शून्य पर सेट करते हैं।

संक्षेप में, आप निम्नलिखित कोड का उपयोग कर सकते हैं:

public static ulong GrayIncrement (ulong original, int bits = 0x40) { 
    ulong last = 0x01UL << (bits - 0x01); 
    if (GetParity (original) == 0x00) { 
     return original^0x01UL;//even parity: swap least significant bit 
    } else { 
     ulong lbm = LeastSignificantBit(original); 
     if (lbm < last) { 
      return original^(lbm << 0x01);//otherwise swap the bit left to the least significant set bit 
     } else { 
      return 0x00;//wrap around 
     } 
    } 
} 

Answer 4

विकि (http://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code)

/* 
    The purpose of this function is to convert an unsigned 
    binary number to reflected binary Gray code. 

    The operator >> is shift right. The operator^is exclusive or. 
*/ 
unsigned int binaryToGray(unsigned int num) 
{ 
     return (num >> 1)^num; 
} 

/* 
     The purpose of this function is to convert a reflected binary 
     Gray code number to a binary number. 
*/ 
unsigned int grayToBinary(unsigned int num) 
{ 
    unsigned int mask; 
    for (mask = num >> 1; mask != 0; mask = mask >> 1) 
    { 
     num = num^mask; 
    } 
    return num; 
}