計算基數4中匹配數字的最快方式是什麼？

給定兩個無符號整數，計算其基數4表示中匹配數字數的最快方法是什麼？在基座4計算基數4中匹配數字的最快方式是什麼？

的匹配位數在鹼的數量圖4是1個鹼基4

B = 15 =（33）

A = 13 =（31）：

實施例1。

例2：

A = 163 =在基座（223）4

B = 131 =（203）在基體4

的匹配位數基座4的數量是2。

第一步我想是計算兩個整數的按位XOR，那麼我們有計算的00號對？什麼是最有效的方式？

注意：假設A和B在基座4具有固定的位數，準確地說16位。

來源

2012-02-11 mghandi

強制鏈接：http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive。 – 2012-02-11 21:47:42

@OliCharlesworth：感謝您的鏈接。我們如何才能適應基數4的情況呢？ – mghandi 2012-02-11 22:15:46

163 = 2203在基數4中，131 = 2003在基數4中。如果您有興趣我可以發佈C代碼:-) – bitfox 2012-02-12 00:12:13

假設你的整數是4個字節。 32位。

更容易理解的方式：
幫助常量數組：

h[0]=3; 
for (int i=1; i<7; i++){ 
    h[i]=h[i-1]*4; 
}

後來，在檢查時，如果c是按位異或後的整數

int count=0; 
for (int i=0; i<7; i++){ 
    if(c&h[i]==0)count++; 
}

其他的解決方案。顯然，速度更快，但少了幾分理解：

int h[4]={1,0,0,0} 

int count=0; 
for (int i=0; i<15; i++){ 
    count+=h[c&3]; 
    c=c>>2; 
}

而且qickening：

count= h[c&3] + h[(c=>>2)&3] + h[(c=>>2)&3] + h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3] + h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c>>2)&3];

更進一步：

int h[16]={2,1,1,1, 1,0,0,0, 1,0,0,0, 1,0,0,0}; 
count= h[c&15] + h[(c=>>4)&15] + h[(c=>>4)&15] + h[(c=>>4)&15] + h[(c=>>4)&15] + h[(c=>>4)&15] + h[(c=>>4)&15]+ h[(c>>4)&15];

如果你確實需要使用的功能這麼多（10^）時間，數量H [256]（你已經抓到，怎麼樣），並使用：

count= h[c&255] + h[(c=>>8)&255] + h[(c=>>8)&255] + h[(c>>8)&255] ;

我認爲，幫助數組h [256 * 256]也可以使用。然後

count= h[c&255] + h[(c>>16)&(256*256-1)];

2^16個整數的數組將全部在處理器現金（儘管是第三級）。所以，速度會非常棒。

來源

2012-02-11 22:15:32 Gangnus

這是一個正確的解決方案。我想知道是否存在更有效的方法。謝謝反正 – mghandi 2012-02-11 22:18:33

看第二個解決方案的編輯答案 – Gangnus 2012-02-11 22:29:37

最快速的解決方案將使用一個巨大的數組，這將使計數對於每一個可能的c。 – Gangnus 2012-02-11 22:30:48

一種解決方案是使用由奧利作爲建議的組比特計數算法。但以使其適應於基座4，我們可以例如做：

d = X ^ÿ;

d =（d |（d >> 1））& 1431655765; //在鹼1431655765 =（01010101010101010101010101010101）2

然後計數在d組的位的數目。這給出了不匹配的數量。

儘管這是最有效的方法嗎？

來源

2012-02-11 22:14:20 mghandi

d =（d＆1431655765）|（d＆（1431655765 <<1)>> 1）將是正確的第二行，是不是？ – Gangnus 2012-02-12 00:24:48

計算基數4中匹配數字的最快方式是什麼？

回答

相關問題