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

Question

Я ищу самый быстрый способ подсчета числа бит-переходов в unsigned int.

Если INT содержит: 0b00000000000000000000000000001010

Количество переходов: 4

Если INT содержит: 0b00000000000000000000000000001001

Количество переходов: 3

Язык С.

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

Какой язык?

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

Answer 3

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

Answer 4

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

Я думаю, что наилучшим вариантом будет комбинация: Look up table for byte или word (256 или 64k записей не так много), а затем объедините байты/слова по их последнему/первому биту.

Answer 5

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

Вот код, используя арифметический сдвиг + 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; 
}