C++ - 泛型编程 - 类型选择

Question

以下片段返回 T 类型(假设无符号)整数的下一个最高次幂。它通过重复移动位来实现。

出于所有意图和目的，我在位移循环中使用的无符号类型足够大以表示(标称的)65536 位数。因此，实际上保持“原样”是可以的。

template <class T>
T supremum_2(T k) {
  if (k == T(0)) return T(1);
  k--;  
  for (int i=1; i<sizeof(T)*8; i++) k |= k >> i;
  return k+1;
}

做一个专业的工作，应该在编译时选择循环计数器的类型，以保证能够跨越 sizeof(T)*8 而不会溢出。

这可以在编译时使用 std::numeric_traits 完成吗？如果是怎么办？

从概念上讲，我希望能够编写如下内容:

typedef unsigned_type_that_can_represent<sizeof(T)*8> counter_type;

...
...

for (counter_type i(1); i<sizeof(T)*8; i<<=1) k = k | k >> i;
...

根据下面的讨论，我决定添加以下上下文。

换句话说:

我们如何保证在编译时为模板代码的内部工作选择高效(只需要多大)和合适的类型？如果我们发现自己在模板代码中使用具体类型，我们可能会通过潜在不透明的途径无意中对模板的类型做出假设。

例如，如果我们坚持使用(比方说)一个整数作为计数器，一切都会正常工作，直到有人将模板代码与他们的 bigint 库一起使用。这可以表示具有比 int 可以表示的更多二进制数字的整数。因此，我们应该使类型为 unsigned long long 吗？当然这只是延迟了问题(尽管很长一段时间)？关于此解决方案，有“640K - 对每个人都足够大”或静态数组大小的说法。

在这种情况下，显而易见但有些低效的选择是将计数器的类型设置为与数字 k 的类型相同。它(原则上)效率低下，因为我们只要求计数器能够表示与 k 的位数相对应的数字。对于其他情况，这可能是错误的假设。

一般情况呢？看起来元编程是一种合适的方法。如何保持这种“理智”？也许，形式上，要求是编译时函数将(可能派生的)抽象类型要求映射到类型。

也许这是 YABL(Yet Another Boost Library)的工作!

[抱歉乱七八糟]

Answer 1

我相信你想把你的循环写成

for (int i=1; i<sizeof(T)*8; i++) k |= k >> i;
return k+1;

一个 int 至少可以存储 2^15-1 的值，这已经足够了。尽管如此，这就是我的做法

template<int N, bool B8  = (N>8), 
                bool B16 = (N>16), 
                bool B32 = (N>32)>
struct select_t;

template<int N>
struct select_t<N, false, false, false> { typedef unsigned char type; };

template<int N>
struct select_t<N, true, false, false> { typedef unsigned short type; };

template<int N>
struct select_t<N, true, true, false> { typedef unsigned long type; };

int main() { select_t<32>::type i = 0; } // unsigned long

你也可以用 unsigned long long 来做，如果你的编译器恰好有那个类型。