7

char配列として表されるビットセット間のハミング距離を計算する必要があります。これはコア操作であるため、できるだけ高速にする必要があります。私はこのようなものを持っています:

const int N = 32; // 32 always

// returns the number of bits that are ones in a char
int countOnes_uchar8(unsigned char v);

// pa and pb point to arrays of N items
int hamming(const unsigned char *pa, const unsigned char *pb)
{
  int ret = 0;
  for(int i = 0; i < N; ++i, ++pa, ++pb)
  {
    ret += countOnes_uchar8(*pa ^ *pb);
  }
  return ret;
}

プロファイリングを行った後、 s を操作する方が高速であることに気付いたintので、次のように書きました。

const int N = 32; // 32 always

// returns the number of bits that are ones in a int of 32 bits
int countOnes_int32(unsigned int v);

// pa and pb point to arrays of N items
int hamming(const unsigned char *pa, const unsigned char *pb)
{
  const unsigned int *qa = reinterpret_cast<const unsigned int*>(pa);
  const unsigned int *qb = reinterpret_cast<const unsigned int*>(pb);

  int ret = 0;
  for(int i = 0; i < N / sizeof(unsigned int); ++i, ++qa, ++qb)
  {
    ret += countOnes_int32(*qa ^ *qb);
  }
  return ret;
}

質問

1) それはセーフからキャストさunsigned char *れますか?unsigned int *

2) 私は 32 ビット マシンで作業していますが、コードを 64 ビット マシンで動作させたいと考えています。両方のマシンで 4 を返しますかsizeof(unsigned int)、それとも 64 ビットのマシンでは 8 ですか?

3) sizeof(unsigned int)64 ビット マシンで 4 が返された場合、どうすれば 64 ビット タイプを操作できlong longますか?

4

2 に答える 2

11

それは安全にキャストされunsigned char *ていますか？unsigned int *

正式には、未定義の動作をします。実際には、ポインタが適切に配置されていればunsigned int、ほぼすべてのプラットフォームで動作します。一部のプラットフォームでは、位置合わせが間違っていると、失敗したり、パフォーマンスが低下したりする場合があります。

両方のマシンで 4 を返しますかsizeof(unsigned int)、それとも 64 ビットのマシンでは 8 ですか?

場合によります。一部のプラットフォームには 64 ビットintがあり、一部には 32 ビットがあります。uint64_tプラットフォームに関係なく使用することはおそらく理にかなっています。32 ビット プラットフォームでは、効果的にループをアンロールし (反復ごとに 2 つの 32 ビット値を処理する)、わずかな改善が得られる可能性があります。

どうすれば 64 ビット型を操作できlong longますか?

uint64_t、C++11 または C99 ライブラリがある場合。long long少なくとも 64 ビットですが、2011 年より前の実装には存在しない可能性があります。

于 2013-09-06T13:18:20.563 に答える
2

1) いいえ、安全/移植可能ではありません。未定義の動作です。charが1 バイトより大きいシステムがあり、char ポインタが適切にアラインされているという保証はありません。

2)sizeof(int)理論上は、64 ビット マシンでは何でもかまいません。実際には、4 または 8 になります。

3) 64 ビットである可能性long longが最も高いですが、そこにも保証はありません。保証が必要な場合は、 を使用してuint64_tください。sizeof()ただし、特定のアルゴリズムでは、データチャンクが重要になる理由がわかりません。

代わりに stdint.h の型を使用することを検討してください。それらは移植可能なコードにはるかに適しています。char、int、または long long の代わりに、 を使用しますuint_fast8_t。これにより、移植可能な方法でコンパイラが最速の整数を選択できるようになります。

補足として、システムに最適なものに応じて、4、8、または 32 ビット レベルで動作する "countOnes" をルックアップ テーブルとして実装することを検討する必要があります。これにより、プログラムのサイズは大きくなりますが、実行時間は短縮されます。に依存する何らかの形式の適応ルックアップ テーブルを実装してみてくださいsizeof(uint_fast8_t)。

于 2013-09-06T14:03:04.803 に答える