fork download
copy 
  1. #include <iostream>
  2. #include <type_traits>
  3. #include <array>
  4.  
  5. namespace impl {
  6.     /// @brief Generates 0b1...1 with @tparam n ones
  7.     template <class T, unsigned n>
  8.     using n_ones = std::integral_constant<T, (~static_cast<T>(0) >> (sizeof(T) * 8 - n))>;
  9.  
  10.  
  11.     /// @brief Performs `@tparam input | (@tparam input << @tparam width` @tparam repeat times.
  12.     ///@{
  13.     template <class T, T input, unsigned width, unsigned repeat>
  14.     struct lshift_add :
  15.         public lshift_add<T, lshift_add<T, input, width, 1>::value, width, repeat - 1> {
  16.     };
  17.     /// @brief Specialization for 1 repetition, just does the shift-and-add operation.
  18.     template <class T, T input, unsigned width>
  19.     struct lshift_add<T, input, width, 1> : public std::integral_constant<T,
  20.         (input & n_ones<T, width>::value) | (input << (width < sizeof(T) * 8 ? width : 0))> {
  21.     };
  22.     /// @brief Specialization for 0 repetitions (just in case).
  23.     template <class T, T input, unsigned width>
  24.     struct lshift_add<T, input, width, 0> :
  25.         public std::integral_constant<T, static_cast<T>(0)> {
  26.     };
  27.     ///@}
  28.  
  29.  
  30.     /// @brief Recursively computes the integral log in base 2 of @tparam arg (as a constexpr).
  31.     ///@{
  32.     template <unsigned arg>
  33.     struct log2 : public std::integral_constant<unsigned, log2<(arg >> 1)>::value + 1> {};
  34.     /// @brief Specialization for `arg=1` to interrupt recursion.
  35.     template <>
  36.     struct log2<1u> : public std::integral_constant<unsigned, 0u> {};
  37.     /// @brief The domain of log(x) is {x>0}
  38.     template <>
  39.     struct log2<0u> {};
  40.     ///@}
  41.  
  42.  
  43.     /** @brief Generates the masks necessary for deinterleaving Morton numbers
  44.      * @tparam step 0-based index of the step; this corresponds to a rshift of
  45.      *         `(@tparam dimensions - 1) * 2^@tparam step`.
  46.      * @tparam dimensions how many values are interleaved, default 2.
  47.      *
  48.      * This fills a T type with adjacent patterns of the type 0...01...1 where the number of ones is `2^@tparam step`
  49.      * and the total width is `@tparam dimensions * 2^@tparam step`; i.e. for `@tparam dimensions = 2`, we have
  50.      *   0. 0b...01010101
  51.      *   1. 0b...00110011
  52.      *   2. 0b...00001111
  53.      */
  54.     template <class T, unsigned step, unsigned dimensions = 2u>
  55.     using mask = lshift_add<T, n_ones<T, 1 << step>::value, dimensions * (1 << step), sizeof(T) * 8 / (2 << step)>;
  56.  
  57.  
  58.     /** @brief Recursively defines a function that deinterleaves @tparam dimensions-dimensional Morton numbers.
  59.      * @note This extracts only the first bit. Rshift the argument once to get the next bit and so on.
  60.      * @tparam step Step of the deinterleave algorithm. Each of it corresponds to a rshift and a bitwise and with one of
  61.      *         the masks defined in @see masks.
  62.      * @tparam dimensions Number of coordinates packed into the Morton number.
  63.      */
  64.     ///@{
  65.     template <class T, unsigned step, unsigned dimensions>
  66.     struct deinterleave {
  67.         static T work(T input) {
  68.             input = deinterleave<T, step - 1, dimensions>::work(input);
  69.             return (input | (input >> ((dimensions - 1) * (1 << (step - 1))))) & mask<T, step, dimensions>::value;
  70.         }
  71.     };
  72.     /// @brief Specialization for step 0, where there is just a bitwise and
  73.     template <class T, unsigned dimensions>
  74.     struct deinterleave<T, 0u, dimensions> {
  75.         static T work(T input) {
  76.             return input & mask<T, 0u, dimensions>::value;
  77.         }
  78.     };
  79.     ///@}
  80.  
  81.  
  82.     /// @brief Helper constexpr which returns the number of steps needed to fully interleave a type @tparam T.
  83.     template <class T, unsigned dimensions>
  84.     using num_steps = std::integral_constant<unsigned, log2<sizeof(T) * 8 / dimensions>::value + 1>;
  85.  
  86.  
  87.     /// @brief Helper function which combines @see deinterleave and @see num_steps into a single call.
  88.     template <class T, unsigned dimensions>
  89.     T deinterleave_first(T n) {
  90.         return deinterleave<T, num_steps<T, dimensions>::value - 1, dimensions>::work(n);
  91.     }
  92.  
  93.  
  94.     /// @brief Helper class which recursively packs an array by de-interleaving one coordinate at a time
  95.     ///@{
  96.     template <class T, unsigned dimensions, unsigned idx>
  97.     struct deinterleave_array {
  98.         static void work(T &n, std::array<T, dimensions> &tuple) {
  99.             std::get<idx>(tuple) = deinterleave_first<T, dimensions>(n);
  100.             deinterleave_array<T, dimensions, idx - 1>::work(n >>= 1, tuple);
  101.         }
  102.     };
  103.     /// @brief Specialization to stop the recursion.
  104.     template <class T, unsigned dimensions>
  105.     struct deinterleave_array<T, dimensions, 0> {
  106.         static void work(T &n, std::array<T, dimensions> &tuple) {
  107.             std::get<0>(tuple) = deinterleave_first<T, dimensions>(n);
  108.         }
  109.     };
  110.     ///@}
  111. }
  112.  
  113.  
  114. /// @brief Extract the first coordinate from a Morton number
  115. template <class T, unsigned dimensions = 2>
  116. T deinterleave_one(T n) {
  117.     return impl::deinterleave_first<T, dimensions>(n);
  118. }
  119.  
  120. /// @brief Extract @tparam dimensions coordinates from a Morton number
  121. template <class T, unsigned dimensions = 2>
  122. std::array<T, dimensions> deinterleave_all(T n) {
  123.     std::array<T, dimensions> retval;
  124.     impl::deinterleave_array<T, dimensions, dimensions - 1>::work(n, retval);
  125.     return retval;
  126. }
  127.  
  128. int main() {
  129.     unsigned n = 0;
  130.     std::cin >> n;
  131.     std::array<unsigned, 2> coords = deinterleave_all(n);
  132.     std::cout << coords[0] << "\t" << coords[1] << std::endl;
  133.     return 0;
  134. }
  135.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
403
stdout
copy 
9	21
https://ideone.com/nhA470
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!