ベース4の一致する数字の数を数える最速の方法は何ですか？

Question

2つの符号なし整数を指定すると、ベース4表現の一致する数字の数を数える最速の方法は何ですか？

例1：

A = 13 =（31）、ベース4

B = 15 =（33）におけるベース4

にベース4に一致する桁数は1です。

例2：

A = 163 =（223）ベースの4

B = 131 =（203）、ベース4に

ベース4に一致する桁数がらしい2

最初のステップは、我々は00の数をカウントする必要があり、二つの整数のビット単位のXORを計算することですペア？それを行う最も効率的な方法は何ですか？

注：AとBは4桁の固定桁数、たとえば正確に16桁とします。

Answer 1

あなたのintはそれぞれ4バイトです。 32ビット。

より理解しやすい方法：
ヘルプ定数配列：

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

その後、検査のために、cは、ビット単位のXOR後の整数の場合：

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^10（非常に多くの機能を使用する必要がある場合）times、count 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 intの配列はすべてプロセッサの現金（3番目のレベル）になります。だから、スピードは本当に素晴らしいでしょう。

Answer 2

解決策の1つは、Oliが提案したように、セットビットカウントアルゴリズムを使用することです。しかしそれを基底4に適合させるために、例えば以下を行うことができる。

d = x^y;

d =（d |（d >> 1））& 1431655765; // 1431655765 =（01010101010101010101010101010101）を基底2に入れます。

次に、dの設定ビット数をカウントします。これは不一致の数を与える。

これは最も効果的な方法ですか？