c - unsignedintのビット遷移の数をカウントする最速の方法

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

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

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 4

わかりました。トランジションでは、0-sと1-sの文字列をウォークスルーすると、0が1の後に続く、または1が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をshiftsに置き換えることができます。

Answer 5

何語？

私は64回ループし、次にビットをビットシフトしてビットを検査し、前のビットを保存して現在のビットと比較します。異なる場合は、カウントを増やしてください。