0

以下片段返回 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;
...

基于以下讨论，我决定添加以下上下文。

换一种方式：

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

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

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

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

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

【抱歉乱说】

4

5 回答 5

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如果您的编译器中恰好有该类型可用，您也可以这样做。

于 2009-06-24T09:36:34.163 回答
1

事实上，你是对的。

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

那么你是不是过度设计了循环变量类型？（可能是由于移位运算符 iso 普通增量，正如 litb 所指出的那样）

于 2009-06-24T11:24:26.003 回答
0

检查static asserts，这可能是您问题的解决方案。

#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
于 2009-06-24T09:09:42.983 回答
0

您可以使用元编程：

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;
于 2009-06-24T09:10:06.573 回答
0

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

// 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;
}

如果我弄错了语法，请原谅我，我总是要查找模板语法。大体思路在这里。

于 2009-06-24T09:10:25.620 回答