计算 4 进制匹配数字的最快方法是什么？

Question

给定两个无符号整数，计算其以 4 为基数的表示形式中匹配数字的数量的最快方法是什么？

示例 1：

A= 13 = (31)（基数为 4）

B= 15 =（33）（基数为 4）

基数为 4 的匹配位数为 1。

示例 2：

A= 163 =（2203）（基数为 4）

B= 131 = (2003) 以 4 为基数，

以 4 为基数的匹配位数为 3。

我猜第一步是计算两个整数的按位异或，那么我们必须数一下 00 对的数量？最有效的方法是什么？

注意：假设 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是按位异或后的整数：

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;
}   

进一步加速：

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）次，计算 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 整数的数组将全部在处理器现金中（尽管是第三级）。所以，速度会非常快。

Answer 2

一种解决方案是使用 Oli 建议的设置位数计数算法。但要使其适应基数 4，我们可以这样做：

d = x^y;

d=(d|(d>>1))& 1431655765； //1431655765=(01010101010101010101010101010101) 以 2 为基数

，然后计算 d 中设置的位数。这给出了不匹配的数量。

这是最有效的方法吗？