0

次のフラグメントは、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 で表現できるよりも多くの 2 進数で整数を表すことができます。したがって、型を unsigned 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...

ループ変数の型を少しオーバーエンジニアリングしていませんか? （litbで指摘されているように、シフト演算子のisoプレーンインクリメントが原因である可能性があります）

于 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 に答える