計算無​​符號整數中位轉換次數的最快方法

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

什麼語言？

我會循環64次，然後位移你的數字來檢查位，然後存儲前一位，並將其與當前位進行比較。如果不同，請增加計數。

Answer 3

好，與過渡你的意思是，如果你走過0秒和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 

你可以用shift來替換mod和div。

Answer 4

最快取決於您的場景： 當您將數據類型指定爲常量大小（無符號整數）時，可以使用查找表。但是，只有當您需要此操作時，表初始化的常量開銷太大，儘管如此，通過int掃描+計數仍然快得多。

我想總體上最好的組合是：查找表中的一個字節或單詞（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和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; 
}