C++ - 通用编程 - 类型选择

Question

以下片段返回 T 类型整数（假定无符号）的下一个最高的 2 次幂。它通过重复移位位来实现此目的。

出于所有意图和目的，位移循环中使用的无符号类型 i 足够大，足以表示（名义上）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;
...

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

换句话说：

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

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

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

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

也许这是 YABL（Yet Another Boost Library）的工作！

[抱歉跑题了]

Answer 1

您可以使用元编程：

template <bool g, typename T, typename E>
struct IF {
    typedef T RET;
};

template < typename T, typename E>
struct IF<false, T, E> {
    typedef E RET;
};

// if sizeof(int) < sizeof(long) then use long else use int
IF< sizeof(int)<sizeof(long), long, int>::RET i;

Answer 2

这可以使用特征实现来完成。 像这样的事情：

// base type for template
template <class T>
struct counter_type
{
};

// specialisation for unsigned integer
template <>
struct  counter_type <unsigned>
{
  typedef unsigned long long value_type; // or whatever
};

template <class T>
T supremum_2(T k) {
  if (k == T(0)) return T(1);
  k--;
  /* Determined by repeated bit shifting. */
  for (counter_type<T>::value_type i=1; i<sizeof(T)*8; i<<=1) k = k | k >> i;
  return k+1;
}

如果我的语法错误，请原谅我，我总是必须查找模板语法。 总体思路就在这里。

Answer 3

我相信您想将循环编写为

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 来实现。

Answer 4

事实上，你是对的。

但实际上，如果你的 T 是 128 位，则移位操作的最高数量将是 127，恰好适合 char...

所以你是不是有点过度设计了循环变量类型？ （可能是由于移位运算符 iso plain 增量，如 litb 所指出的）

Answer 5

检查静态断言，这可能是解决您的问题。

#include <climits>
#include <cwchar>
#include <limits>
#include <boost/static_assert.hpp>

namespace my_conditions {

   BOOST_STATIC_ASSERT(std::numeric_limits<int>::digits >= 32);
   BOOST_STATIC_ASSERT(WCHAR_MIN >= 0);

} // namespace my_conditions