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
@SkiFire13 and @CAD97
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.
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.