什么是在四进制下计算匹配数字数量的最快方法？

Question

什么是在四进制下计算匹配数字数量的最快方法？

calgorithmoptimizationintegerbit-manipulation

4

给定两个无符号整数，最快的方法是什么来计算它们在四进制表示中匹配数字的数量？

例子1：

A= 13 = (31) 在四进制下

B= 15 = (33) 在四进制下

在四进制下匹配数字的数量为1。

例子2：

A= 163 = (223) 在四进制下

B= 131 = (203) 在四进制下

在四进制下匹配数字的数量为2。

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

注意：假设A和B在四进制下有固定的数字位数，比如恰好16位。

- mghandi

2

强制链接：http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive。 - Oliver Charlesworth

@OliCharlesworth：感谢链接。我们如何将其适应于基数为4的情况？ - mghandi

1

163在4进制下等于2203，131在4进制下等于2003。如果您感兴趣，我可以发布C代码 :-) - bitfox

你似乎需要数字在位置和数量上匹配。如果是这样的话，我认为你应该在问题中明确说明。 - undefined

2个回答

0

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

d = x^y;

d = (d | (d>>1))& 1431655765; //1431655765=(01010101010101010101010101010101)在二进制中

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

但这是最有效的方法吗？

- mghandi

d=(d& 1431655765)|(d&(1431655765<<1)>>1) 这应该是正确的第二行，对吧？ - Gangnus

@Gangnus 我猜两个版本都可以正常工作。 - undefined

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gangnus · Accepted Answer

假设，您的整数每个都是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个整数的数组将全部存储在处理器缓存中（第三级缓存），因此速度非常快。