Bitswap समारोह टेम्पलेट metaprogramming

Question

का उपयोग कर bit twiddling hacks वेबसाइट बिट्स उल्टा करने के लिए निम्नलिखित बहुत ही कुशल समारोह का प्रस्ताव:

// Bitswap: reverse the bits of the value of unsigned integral type T 
template <class T> 
constexpr T bitswap(T src) 
{ 
    constexpr std::size_t char_bit = std::numeric_limits<unsigned char>::digits; 
    constexpr std::size_t digits = sizeof(T) * char_bit; 
    std::size_t size = digits; 
    T mask = ~T();   
    while ((size >>= 1) > 0) { 
     mask ^= (mask << size); 
     src = ((src >> size) & mask) | ((src << size) & ~mask); 
    } 
    return src; 
} 

• वहाँ टेम्पलेट metaprogramming प्रत्यावर्तन का उपयोग कर पाश उतारना करने के द्वारा इस समारोह में तेजी लाने के कोई तरीका है?
• क्या इसे __uint128_t जैसे विस्तारित प्रकारों के साथ काम करने का कोई तरीका है? (मूल संस्करण __uint128_t के साथ काम करता है)
• क्या यह कार्य सैद्धांतिक रूप से दो बिट्स की गैर-शक्ति वाले प्रकारों के बिट्स को उलट करने के लिए काम करता है यदि digits सही संख्या में बिट्स की सही संख्या में प्रारंभ किया गया है? (उदाहरण के लिए एक हाइपोथिकल uint41_t)।

Answer 1

यह एक छोटे उपयोगिता समारोह देता है कि आप है

:

template<class=void, std::size_t...Is> 
constexpr auto indexer(std::index_sequence<Is...>) { 
    return [](auto&& f) { 
    using discard=int[]; 
    (void)discard{0,(void(
     f(std::integral_constant<std::size_t, Is>{}) 
    ),0)...}; 
    }; 
} 
template<std::size_t N> 
constexpr auto indexer() { 
    return indexer(std::make_index_sequence<N>{}); 
} 

अगला हम एक संकलन समय लॉग समारोह की जरूरत है: खोल पैरामीटर सी ++ 14 में एक लैम्ब्डा में इनलाइन पैक

हम फिर एक साथ इन डाल:

template <class T> 
constexpr T bitswap(T src) 
{ 
    constexpr std::size_t char_bit = std::numeric_limits<unsigned char>::digits; 
    static_assert(char_bit == 8); 
    constexpr std::size_t digits = sizeof(T) * char_bit; 
    T mask = ~T();   

    auto expand = indexer<ct_log_2(digits)-1>(); 
    expand([&](auto i){ 
    constexpr auto size = digits >> (i+1); 
    mask ^= (mask << size); 
    src = ((src >> size) & mask) | ((src << size) & ~mask); 
    }); 

    return src; 
} 

दुर्भाग्य से यह constexpr lambdas की एक सी ++ 17 सुविधा की आवश्यकता है। हालांकि सूचकांक कार्य को वर्बोज़ मैन्युअल कार्यान्वयन में बदल दिया जा सकता है।

template<std::size_t digits, std::size_t I> 
constexpr auto size_calc = (digits >> (I+1)); 

साथ expand अनुभाग बदलें::

एक constexpr आकार कैलकुलेटर बनाएं

using discard=int[]; 
    (void)discard{0,(void((
    void(mask ^= (mask << size_calc<digits, Is>)), 
    void(src = ((src >> size_calc<digits, Is>) & mask) | ((src << size_calc<digits, Is>) & ~mask)), 
    0 
)),0)...}; 

जहां हम स्वयं का विस्तार किया है क्या expand हमारे लिए करता है (बदसूरत है ना?), तो एक-तर्क संस्करण कॉल करें:

return bitswap(src, std::make_index_sequence< ct_log_2(digits)-1 >{}); 

सही सूचकांक अनुक्रम।

परिणाम समकक्ष होना चाहिए।

Live example।

कुछ कंपाइलर्स गहरी रिकर्सिव कॉल को रेखांकित करने का विरोध करते हैं। यहां रिकर्सन गहराई 1 से 3 है (पैरामीटर पैक वृद्धि प्राप्त करने के लिए)। अब एक बेवकूफ रिकर्सिव समाधान केवल लॉग_2 (128) या 6 है, इसलिए यह अधिक हो सकता है।

Answer 2

आप कर सकते हैं नहीं टेम्प्लेट की गई कॉल बाहर चल लागू है, लेकिन मौके, यह एक अनुकूलित निर्माण में एक ही inlined समारोह में खत्म हो जाएगा:

#include <iostream> 
#include <limits> 
#include <iomanip> 

template <class T, int size = ((std::numeric_limits<unsigned char>::digits 
           * sizeof(T)) >> 1)> 
struct Swap 
{ 
    static constexpr T bitswap(T src, T mask = ~T()) 
    { 
     mask ^= (mask << size); 
     src = ((src >> size) & mask) | ((src << size) & ~mask); 
     return Swap<T, (size >> 1)>::bitswap(src, mask); 
    } 
}; 

template <class T> 
struct Swap<T, 0> 
{ 
    static constexpr T bitswap(T src, T mask) 
    { 
     return src; 
    } 
}; 

template <class T> 
constexpr T bitswap(T src) 
{ 
    return Swap<T>::bitswap(src); 
} 

int main() { 
    std::cout << std::hex << bitswap(0x12345678l); 
}