c++ - バイトに設定されたビット数を計算する

Question

この方法でバイトに設定されたビット数を計算する最適な方法であることに興味があります

template< unsigned char byte > class BITS_SET
{
public:
    enum {
     B0 = (byte & 0x01) ? 1:0,
     B1 = (byte & 0x02) ? 1:0,
     B2 = (byte & 0x04) ? 1:0,
     B3 = (byte & 0x08) ? 1:0,
     B4 = (byte & 0x10) ? 1:0,
     B5 = (byte & 0x20) ? 1:0,
     B6 = (byte & 0x40) ? 1:0,
     B7 = (byte & 0x80) ? 1:0
    };
public:
 enum{RESULT = B0+B1+B2+B3+B4+B5+B6+B7};
};

実行時にバイトの値がわかっている場合に最適でしょうか？これをコードで使用することをお勧めしますか？

score 25 · Accepted Answer

1 バイトのデータの場合、速度とメモリ消費の両方を考慮した最適な方法:

uint8_t count_ones (uint8_t byte)
{
  static const uint8_t NIBBLE_LOOKUP [16] =
  {
    0, 1, 1, 2, 1, 2, 2, 3, 
    1, 2, 2, 3, 2, 3, 3, 4
  };


  return NIBBLE_LOOKUP[byte & 0x0F] + NIBBLE_LOOKUP[byte >> 4];
}

for ループからこの関数を呼び出すと、ほとんどのシステムで非常に効率的なプログラムが生成されます。そして、それは非常に一般的です。

score 19 · Accepted Answer

8 ビット値の場合は、256 要素のルックアップテーブルを使用してください。

より大きなサイズの入力の場合、それは少し簡単ではありません。Sean Eron Anderson は、彼のBit Twiddling Hacks ページで、これに対していくつかの異なる機能を提供しており、すべて異なるパフォーマンス特性を備えています。プロセッサの性質 (パイプラインの深さ、分岐予測子、キャッシュサイズなど) と使用しているデータに依存するため、すべてが最速のバージョンは 1 つではありません。

score 11 · Accepted Answer

標準ライブラリを使用しないのはなぜですか? そうすれば、最適な方法は実装によって決定され、実際に記述できる標準準拠のコードよりも優れている可能性があります。たとえば、x86 を使用している場合、これは単一の命令にコンパイルされますが、それをサポートする CPU をターゲットにしている場合のみです。

#include <bitset>
#include <iostream>

int main() {
  unsigned char bitfield = 17;
  std::cout << std::bitset<8>(bitfield).count() <<
    std::endl;
}

score 4 · Accepted Answer

1 バイトの値だけの場合、最も速い方法は、値でインデックスを付けた 256 バイト配列に回答を格納することです。例えば、bits_set[] = {0, 1, 1, 2, ...

score 2 · Accepted Answer

「ビットカウントを行う最速の方法」に対する通常の答えは、「配列内のバイトを検索する」です。そのようなものはバイトに対して機能しますが、実際のメモリアクセスを支払う必要があります。これをたまにしか行わない場合はおそらく最速ですが、たまにしか行わない場合は最速である必要はありません。

頻繁に行う場合は、バイトを単語またはダブルワードにまとめて、これらに対して高速なビットカウント操作を行う方がよいでしょう。配列内の 32 ビット値を実際にルックアップしてそのビット数を取得することはできないため、これらは純粋な算術演算になる傾向があります。代わりに、巧妙な方法でシフトおよびマスキングすることにより、値を結合します。

これを行うための巧妙なトリックの優れた情報源は、Bit Hacksです。

Cで32ビットワードのビットをカウントするために公開されているスキームは次のとおりです。

 unsigned int v; // count bits set in this (32-bit value)
 unsigned int c; // store the total here

 v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
 c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

score 1 · Accepted Answer

左シフトを行い、残りをマスクしてみませんか?

int countBits(unsigned char byte){
    int count = 0;
    for(int i = 0; i < 8; i++)
        count += (byte >> i) & 0x01; // Shift bit[i] to the first position, and mask off the remaining bits.
    return count;
}

これは、カウントされる値に含まれるビット数を計算するだけで、任意のサイズの int を処理するように簡単に適応できます。次に、その値をカウンターループで使用します。これはすべて非常に簡単です。

int countBits(unsigned long long int a){
    int count = 0;
    for(int i = 0; i < sizeof(a)*8; i++)
        count += (a >> i) & 0x01;
    return count;
}

score 1 · Accepted Answer

std::popcountヘッダーから導入された C++20<bit>

std::popcount(0b1101u)3を返します

詳細については、 https://en.cppreference.com/w/cpp/numeric/popcountを参照してください。

score 0 · Accepted Answer

0

int count(int a){ return a == 0 ? 0 : 1 + count(a&(a-1)); }

于 2012-03-30T20:30:21.430 に答える

c++ - バイトに設定されたビット数を計算する

12 に答える 12

Related

Reference