符号なし整数でビット遷移の数をカウントする最速の方法

Question

unsigned intのビット遷移の数をカウントする最速の方法を探しています。

intに次が含まれる場合：0b00000000000000000000000000001010

遷移の数は4です

intに次が含まれる場合：0b00000000000000000000000000001001

遷移の数は3です

言語はCです。

Answer 1

int numTransitions(int a)
{
  int b = a >> 1; // sign-extending shift properly counts bits at the ends
  int c = a ^ b;  // xor marks bits that are not the same as their neighbors on the left
  return CountBits(c); // count number of set bits in c
}

CountBits の効率的な実装については、 http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Answer 2

最速はシナリオによって異なります： データ型を定数サイズ（unsigned int）として指定したため、ルックアップテーブルで可能です。しかし、テーブルを初期化するための一定のオーバーヘッドが大きすぎる場合にのみこの操作が必要な場合、intのスキャン+カウントはそれでもはるかに高速です。

全体的な最善の組み合わせは次のとおりだと思います：バイトまたはワード（256または64kエントリはそれほど多くありません）のテーブルを検索し、最後の/最初のビットでバイト/ワードを結合します。

Answer 3

C / C ++では、次のことを行います。

unsigned int Transitions(unsigned int value)
{
    unsigned int result = 0;

    for (unsigned int markers = value ^ (value >> 1); markers; markers = markers >> 1)
    {
        if (markers & 0x01) result++;
    }

    return result;
}

Answer 4

算術シフト+ xorとKernighanのビットカウント方法を使用したコードは次のとおりです。

int count_transitions(int x)
{
    assert((-1 >> 1) < 0); // check for arithmetic shift
    int count = 0;
    for(x ^= (x >> 1); x; x &= x - 1)
        ++count;
    return count;
}

Answer 5

どの言語ですか？

64回ループした後、番号をビットシフトしてビットを検査し、前のビットを保存して現在のビットと比較します。異なる場合は、カウントを増やします。

Answer 6

0

これは、ビットをシフトアウトし、変更をカウントすることで簡単です：

transitions(n)
  result = 0
  prev = n mod 2
  n = n div 2
  while n<>0 
    if n mod 2 <> prev then
      result++
      prev = n mod 2
    fi
    n = n div 2
  elihw
  return result

modとdivをシフトに置き換えることができます。