funkcja Bitswap użyciu szablonu metaprogramowanie

Question

bit twiddling hacks strona zaproponować następującą bardzo wydajną funkcję odwrócenia bitów:

// 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; 
} 

• Czy istnieje jakiś sposób, aby przyspieszyć tę funkcję przy użyciu szablonu METAPROGRAMOWANIE rekursji rozwinąć pętlę?
• Czy istnieje sposób, aby działał z rozszerzonymi typami, takimi jak __uint128_t? (oryginalna wersja działa z __uint128_t)
• Czy ta funkcja działa teoretycznie, aby odwrócić bity typów przy braku mocy dwóch bitów, jeśli digits jest poprawnie zainicjalizowany do poprawnej liczby bitów? (na przykład hipotermiczny uint41_t).

Answer 1

Ta funkcja jest trochę narzędzie, które pozwala rozpakować parametr pakuje inline do lambda w C++ 14:

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>{}); 
} 

Następnie musimy funkcję kompilacji dziennika czas:

constexpr std::size_t ct_log_2(std::size_t N) { 
    return (N>1)?1+ct_log_2(N>>1):0; 
} 

możemy następnie umieścić je razem:

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; 
} 

Niestety wymaga to C++ 17 cechę constexpr lambda. Jednak praca indeksatora może zostać przekształcona w pełną manualną implementację.

Tworzenie kalkulator constexpr:

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

zastąpić moduł expand z:

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)...}; 

gdzie mamy ręcznie rozszerzony co expand robi dla nas (nie to jest brzydkie?), A następnie mieć jednoargumentową wersję:

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

z prawidłowa sekwencja indeksu.

Wynik powinien być równoważny.

Live example.

Niektóre kompilatory są odporne na wywoływanie głębokich wywołań rekursywnych. Głębokość rekursji wynosi od 1 do 3 (aby uzyskać wzrost pakietu parametrów). Teraz naiwne rozwiązanie rekurencyjne to log_2 (128) lub 6, więc może to być przesada.

Answer 2

Nie można wymusić toczenia się na matrycy połączeń, ale są szanse, to skończy się w jednej funkcji inlined w zoptymalizowanej produkcji:

#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); 
}