Самый быстрый способ подсчитать количество битовых переходов в беззнаковом int

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

В 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 3

Скорость зависит от вашего сценария: Поскольку вы указали тип данных как постоянный размер (unsigned int), это возможно с помощью таблицы поиска. Но когда вам нужна эта операция только один раз, когда постоянные издержки для инициализации таблицы слишком велики, и сканирование + подсчет через int намного быстрее, несмотря на это.

Полагаю, что в целом лучше всего было бы использовать комбинацию: найдите в таблице байт или слово (256 или 64k записей не так уж много), а затем объедините байты / слова по их последнему / первому биту.

Answer 4

Вот код с использованием арифметического shift + 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 5

Какой язык?

Я зациклился бы 64 раза, а затем сдвинул бит по вашему номеру для проверки битов, затем сохранил предыдущий бит и сравнил его с текущим. Если это не так, увеличьте счет.

Answer 6

Хорошо, с переходами, которые вы имеете в виду, проходя через строки 0 и 1, вы считаете, что 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

вы можете заменить мод и div на сдвиги.