c - 计算基数 4 中匹配数字数量的最快方法是什么？

Question

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

示例 1:

A= 13 = (31) 以 4 为基数

B= 15 = (33) 以 4 为基数

以 4 为基数的匹配数字个数为 1。

示例 2:

A= 163 = (223) 以 4 为基数

B= 131 = (203) 以 4 为基数

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

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

注意:假设 A 和 B 在基数 4 中有固定的数字位数，正好是 16 位数字。

Answer 1

假设，您的整数每个都是 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 整数数组将全部在处理器现金中(尽管是第三级)。所以，速度会非常快。