1

So I wrote an answer here: https://stackoverflow.com/a/56569397/2642059 which strives to compute log2 at compile time like so:

template <unsigned int x>
constexpr enable_if_t<x != 0U, int> log2 = 1 + log2<x / 2U>;

template <>
constexpr int log2<1U> = 0;

This works fine but I didn't feel like I should have had to specialize:

template <unsigned int x>
constexpr enable_if_t<x != 0U, int> log2 = x < 4U ? 1 : 1 + log2<x / 2U>;

But this gives me the error:

In substitution of template<bool _Cond, class _Tp> using enable_if_t = typename std::enable_if::type [with bool _Cond = (0u != 0u); _Tp = int]:
prog.cpp:7:61: recursively required from constexpr std::enable_if_t<true, int> log2<4u>
prog.cpp:7:61: required from constexpr std::enable_if_t<true, int> log2<8u>
prog.cpp:10:11: required from here /usr/include/c++/6/type_traits:2523:61: error: no type named type in struct std::enable_if<false, int>

Is there a way I can prevent the compiler from unrolling the recursion too far?

Jonathan Mee
  • 37,899
  • 23
  • 129
  • 288
  • 1
    _Is there a way I can prevent the compiler from unrolling the recursion too far?_ Yes, by adding a specialization for the base case that doesn't do a recursive instantiation. – Miles Budnek Jun 12 '19 at 20:14
  • @MilesBudnek I *don't* want this to be defined for `log2<0>` are you saying there's a better way to do this? – Jonathan Mee Jun 12 '19 at 20:26
  • 1
    Never mind, I misread the base case as 0. The `enable_if` makes sense. – Miles Budnek Jun 12 '19 at 20:27
  • 1
    Your template is recursive. For any recursion in our life we need a leaf case. In TMP the only way to provide a leaf case is with specialization. If you replace your TMP with constexpr function and constexpr if, you would be able to avoid specialization. – SergeyA Jun 12 '19 at 20:35
  • @SergeyA that's a clever solution. I should tinker with that some. – Jonathan Mee Jun 12 '19 at 20:45
  • 1
    @JonathanMee posted an answer to the same effect with some code. – SergeyA Jun 12 '19 at 20:53

1 Answers1

2

You use recursion to calculate log2. Each and every recursive operation in our life needs the leaf case.

In case of recursive leaf functions, the leaf case can be provided with non-recursive returns. However, with template variables the only way to provide the leaf case would be with specialization, there is no other way at all.

I believe, that you can achieve the very same goals with constexpr function and no TMP:

#include <type_traits>

constexpr int log2(int arg) {
    if (arg == 0) return 0;
    if (arg == 1) return 0;
    return 1 + log2(arg / 2u);
}

constexpr std::integral_constant<int, log2(16)> z; // z.value == 4

This works with both run-time and compile-time arguments and generally should be preferred over pure TMP solution, except for educational purposes.

For educational or other undisclosed purposes, you can use exclusive compile-time like that:

#include <type_traits>

template<int arg>
constexpr int log2(std::integral_constant<int, arg> ) {
    static_assert(arg > 0, "Bad arg to log2!");
    if constexpr (arg == 1) {
        return 0;
    } else {
        return 1 + log2(std::integral_constant<int, arg / 2> {});
    }
}

int k = log2(std::integral_constant<int, 16>{});
SergeyA
  • 61,605
  • 5
  • 78
  • 137
  • So I do love your `log2` function there, but what if I wanted to prevent this from being called at runtime? – Jonathan Mee Jun 12 '19 at 21:05
  • @JonathanMee the first one? None from the function itself. The second one is naturally compile-time only. – SergeyA Jun 12 '19 at 21:20