findbit.hh

#ifndef __DUNE_ACFEM_COMMON_FINDBIT_HH__
#define __DUNE_ACFEM_COMMON_FINDBIT_HH__
 
#include "types.hh"
 
namespace Dune {
 
  namespace ACFem {
 
    namespace {
      template<class T, T val, bool isZero = val == 0, std::size_t N = std::numeric_limits<T>::digits/2, class SFINAE = void>
      struct FindMostSignificantBitHelper;
 
      // Bits only in lower half
      template<class T, T val, bool isZero, std::size_t N>
      struct FindMostSignificantBitHelper<T, val, isZero, N, std::enable_if_t<!isZero && (N > 0) && 0 == (val & (std::numeric_limits<T>::max() << N))> >
      {
        static constexpr std::size_t value = FindMostSignificantBitHelper<T, val, val == 0, N/2>::value;
      };
 
      // Bits in upper half
      template<class T, T val, bool isZero, std::size_t N>
      struct FindMostSignificantBitHelper<T, val, isZero, N, std::enable_if_t<!isZero && (N > 0) && 0 != (val & (std::numeric_limits<T>::max() << N))> >
      {
        static constexpr std::size_t value = N + FindMostSignificantBitHelper<T, (val >> N), (val >> N) == 0, N/2>::value;
      };
 
      // recursion end-point / optimization
      template<class T, T V, std::size_t N>
      struct FindMostSignificantBitHelper<T, V, true, N>
      {
        static constexpr std::size_t value = -1;
      };
 
      // recursion end-point / failsafe
      template<class T, T V, bool isZero>
      struct FindMostSignificantBitHelper<T, V, isZero, 0>
      {
        static constexpr std::size_t value = 0;
      };
    }
 
    template<class T, T V>
    constexpr std::size_t findMostSignificantBit(Constant<T, V>&&)
    {
      return FindMostSignificantBitHelper<T, V>::value;
    }
 
    template<std::size_t mask>
    using FindMostSignificantBit = IndexConstant<FindMostSignificantBitHelper<std::size_t, mask>::value>;
 
    namespace {
      template<class T, T val, bool isZero = val == 0, std::size_t N = std::numeric_limits<T>::digits/2, class = void>
      struct FindLeastSignificantBitHelper;
 
      // Bits in lower half
      template<class T, T val, bool isZero, std::size_t N>
      struct FindLeastSignificantBitHelper<T, val, isZero, N, std::enable_if_t<!isZero && (N > 0) && 0 != (val & ~(std::numeric_limits<T>::max() << N))> >
      {
        static constexpr std::size_t value = FindLeastSignificantBitHelper<T, val, val == 0, N/2>::value;
      };
 
      // Bits only in upper half
      template<class T, T val, bool isZero, std::size_t N>
      struct FindLeastSignificantBitHelper<T, val, isZero, N, std::enable_if_t<!isZero && (N > 0) && 0 == (val & ~(std::numeric_limits<T>::max() << N))> >
      {
        static constexpr std::size_t value = N + FindLeastSignificantBitHelper<T, (val >> N), (val >> N) == 0, N/2>::value;
      };
 
      // recursion end-point / optimization
      template<class T, T V, std::size_t N>
      struct FindLeastSignificantBitHelper<T, V, true, N>
      {
        static constexpr std::size_t value = -1;
      };
 
      // recursion end-point / failsafe
      template<class T, T V, bool isZero>
      struct FindLeastSignificantBitHelper<T, V, isZero, 0>
      {
        static constexpr std::size_t value = 0;
      };
    }
 
    template<class T, T V>
    constexpr std::size_t findLeastSignificantBit(Constant<T, V>&&)
    {
      return FindLeastSignificantBitHelper<T, V>::value;
    }
 
    template<std::size_t mask>
    using FindLeastSignificantBit = IndexConstant<FindLeastSignificantBitHelper<std::size_t, mask>::value>;
 
    template<class T, T V>
    constexpr std::size_t findFirstZeroBit(Constant<T, V>&&)
    {
      return FindLeastSignificantBitHelper<T, ~V>::value;
    }
 
    template<std::size_t mask>
    using FindFirstZeroBit = IndexConstant<FindLeastSignificantBitHelper<std::size_t, ~mask>::value>;
 
 
 
  } // ACFem::
 
} // Dune::
 
#endif // __DUNE_ACFEM_COMMON_FINDBIT_HH__