# Making a type level type function with `typenum` crate

Here's a very nice blog post:

The same blog has some other great posts on type level meta-programming in Rust, but this is a good general overview of (advanced) techniques.

1 Like

For my solution I focused on just getting a "nice" mathematic formula. I first noticed you can divide the problem in two steps:

• determine how many bits are needed to represent the given value;
• round that number up to a power of two.

The first step is just a floored base-2 logarithm plus 1 (the important insight is that it is a base-2 logarithm, to understand whether it is floored or ceiled, or you need to add/subtract 1 or do nothing else can be understood by looking at a couple of examples). Luckly `typenum` already provides a floored base-2 logarithm so everything is good.

For the second step I noticed that any positive number is equal to `2 ^ log_2(n)` and since we want the next power of two we only need to find the first integer number bigger than or equal to `log_2(n)` (if it wasn't integer it wouldn't be a power of 2, and if it was smaller than `log_2(n)` it wouldn't be rounding up our number to a power of 2). Computing `2 ^ x` can be done as simply `1 << x` (this is a common trick/optimizations in programming), while the first integer bigger than or equal to `log_2(n)` is the ceiled base-2 logarithm, which unfortunately we don't have (`typenum` only has a floored one). Lucklily we can use the floored one to get the ceiled one: you can notice that adding 1 to it works in almost every case, except when `n` is already a power of 2 (that is, when `log_2(n)` is already an integer). To fix this edge case you can subtract 1 from `n` before taking the logarithm: this will change the result only in those cases where `log_2(n)` was a perfect integer, making it 1 less than before, which will then be compensated by adding 1. These are quite similar techniques to the ones used for doing ceiled integer division, if you ever used them. After some time they become quite intuitive so you immediately think of them when you recognize the problem.

Finally, how does this translate into code? The first step becomes a `Add1<Log2<N>>`. You can only see the `Log2<N>` inside the `CalcMinUIntType<N>`, because this is passed to the second step, which immediately subtracts 1 from it (so I just removed the `Add1` in order to do that). The rest of the second step is in the `NextPow2<N>` type alias. Translated literally it would just be `Shleft<U1, Add1<Log2<N>>>`, but this has an edge case when `N` is `0` (that is, for `U1`), so I fixed it by changing `N` in `Maximum<U1, N>`. Finally, the smallest integer type you can use is `u8`, so I wrapped `CalcMinUIntType` with a `Maximum<U8, ...>`.

3 Likes

Thank you both for your very kind, informative and elaborate exposition on my question.

This is a prime example of the kind of help we get within the Rust community and how we are always happy to see others succeeding in their engineering work.