डी-इंटरलीव बिट्स (UnMortonizing?)

32 बिट int से डी-इंटरलीव बिट्स का सबसे प्रभावी तरीका क्या है? इस विशेष मामले के लिए, मैं केवल अजीब बिट्स के बारे में चिंतित हूं, हालांकि मुझे यकीन है कि दोनों सेटों के किसी भी समाधान को सामान्य बनाना सामान्य है।डी-इंटरलीव बिट्स (UnMortonizing?)

उदाहरण के लिए, मैं 0b01000101 को 0b1011 में परिवर्तित करना चाहता हूं। सबसे तेज़ तरीका क्या है?

संपादित करें:

इस आवेदन में, मैं गारंटी ले सकते हैं कि यहां तक कि बिट्स सब शून्य है। क्या मैं गति को सुधारने या अंतरिक्ष को कम करने के लिए उस तथ्य का लाभ उठा सकता हूं?

स्रोत

2010-06-29 AShelly

को देखते हुए क्या आप जानते हैं कि आपके आवेदन में 0 है कि हर दूसरे बिट, आप इसे इस तरह से कर सकते हैं:

0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p x 
| 00a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0 x >> 1 
    -------------------------------- 
= 0aabbccddeeffgghhiijjkkllmmnnoop x | (x >> 1) 
& 00110011001100110011001100110011 0x33333333 
    -------------------------------- 
= 00ab00cd00ef00gh00ij00kl00mn00op (x | (x >> 1)) & 0x33333333

फिर दूसरे चरण के लिए:

x = (x | (x >> 1)) & 0x33333333; 
x = (x | (x >> 2)) & 0x0f0f0f0f; 
x = (x | (x >> 4)) & 0x00ff00ff; 
x = (x | (x >> 8)) & 0x0000ffff;

पहला कदम इस तरह दिखता है एक समय में दो बिट्स के साथ काम करता है, और इसी तरह।

स्रोत

2010-07-12 23:54:19

अच्छा। यह वास्तव में मेरी तरह की चीज है। – AShelly

यह मेरे पीसी पर 32 प्रविष्टि तालिका से तेज़ परीक्षण करता है। – AShelly

... और यदि आप नहीं जानते कि विषम बिट्स शून्य हैं, तो पहले से 'x & = 0x55555555' करें – Bergi

गति के मामले में, एक लुकअप टेबल 16 बिट्स 2^32 प्रविष्टियों के साथ चौड़ा होना मुश्किल होगा! लेकिन यदि आपके पास अतिरिक्त स्मृति नहीं है, तो 256-प्रविष्टि तालिका में चार लुकअप, प्लस कुछ बदलाव और एंड्स उन्हें एक साथ सिलाई करने के लिए, बेहतर विकल्प हो सकता है। या शायद मीठा स्थान कहीं के बीच में है ... यह आपके द्वारा उपलब्ध संसाधनों पर निर्भर करता है, और लुकअप टेबल को प्रारंभ करने की लागत को देखने के लिए आपको आवश्यक लुकअप की संख्या पर कैसे बढ़ाया जाएगा।

स्रोत

2010-06-29 01:52:36

मेरे पास निश्चित रूप से अतिरिक्त स्मृति नहीं है - मैं एक एम्बेडेड प्लेटफ़ॉर्म को लक्षित कर रहा हूं। 256 प्रविष्टि तालिका काम कर सकती है। मुझे अभी भी एक एल्गोरिदमिक विधि में रूचि है। – AShelly

@AShelly: एक प्रारंभिक बिंदु यह सोचने के लिए होगा कि प्रत्येक संभावित एक-बिट को नई स्थिति में "स्थानांतरित" (शिफ्ट) कितनी स्थिति होगी। उदाहरण के लिए, बिट 6 को 3 स्थानों, सीधे 4 से 2 स्थानों, बिट 2 से 1 स्थानों पर स्थानांतरित किया जाएगा, और 0 0 स्थानांतरित किए बिना थोड़ा स्थानांतरित किया जाएगा। फिर, बाइनरी संख्या में उन शिफ्ट राशियों को विघटित करें। यह काम करता है क्योंकि कहता है, 3 स्थान 2 से स्थानांतरित होते हैं और फिर 1 से 2 के समान होते हैं। बिट्स का चयन करने के लिए थोड़ा मास्क का उपयोग करें जिन्हें स्थानांतरित करने की आवश्यकता है। हालांकि, यह दृष्टिकोण एक छोटी लुकअप टेबल की तुलना में अधिक महंगा हो सकता है। एम्बेडेड प्लेटफॉर्म पर – rwong

, एक 16-एंट्री टेबल आज़माएं और एक समय में 4-बिट्स को संसाधित करें। – rwong

मुझे यकीन है कि यह कैसे त्वरित होगा नहीं कर रहा हूँ, लेकिन आप की तरह

int a = 0b01000101; 
int b = 0; 
int i = 0; 
while (a > 0) { 
    b |= (a & 1) << i; 
    a >>= 2; 
}

कुछ कर सकते हैं जो एक के बंद सभी विषम बिट्स खींच और ख पर डाल होगा।

स्रोत

2010-06-29 22:56:57

आपको कहीं कहीं i ++ की आवश्यकता है। – AShelly

डी-इंटरलीव बिट्स (UnMortonizing?)

उत्तर

संबंधित मुद्दे