汉明重量只写二进制运算？
汉明重量只写二进制运算？
提问于 2012-03-30 15:35:36
我只需要用二进制操作(&，^，>>)来编写一个字节Hamming重量的表达式；没有任何循环，只有一个公式。
我知道有很多算法，允许计算Hamming重量，但它们都使用算术运算或循环。
如果我们从http://en.wikipedia.org/wiki/Hamming_weight中取一个算法，那么第一个和D=B+C可以写成D= B^C^(B&C << 1)，但是下面两个和要复杂得多。
有人有线索吗？
更新:谢谢你们的帮助。实际上，我需要这样的东西：
int popcount_1(unsigned char in){
unsigned char m1 = 0x55;
unsigned char m2 = 0x33;
unsigned char m4 = 0x0f;
unsigned char B,C = 0;
unsigned char x = in;
x = (x & (x << 1) & (m1 << 1)) | (m1 & (x ^ (x >> 1)));
B = x & m2;
C = (x >> 2) & m2;
x = B ^ C ^ ((B & C) << 1);
B = (x & m4 ) ^ ((x >> 4) & m4);
C = (x & ((x >> 4) & m4)) << 1;
x = B ^ C ^ ((B & C) << 1);
return x;
}此代码将导致汉明重量的变量。它不包含任何+，-或比较指令，它可以工作在8位微控制器。然而，与大多数其他解决方案相比，它需要更多的操作。现在，我试着简化它。
UPDATE2:另一种基于64位寄存器的解决方案是由@Evgeny提出的
回答 2
Stack Overflow用户
回答已采纳
发布于 2012-03-30 16:54:17
我不确定这是否是您要搜索的内容，但这里只是一个只使用移位和按位排列的公式，并且：
int weight(unsigned char x)
{
return ((0x876543210 >>
(((0x4332322132212110 >> ((x & 0xF) << 2)) & 0xF) << 2)) >>
((0x4332322132212110 >> (((x & 0xF0) >> 2)) & 0xF) << 2))
& 0xf;
}在这里，移位操作被两次用作数组索引的替代(查找4位hamming重量)。另外一个shift操作使用数组索引来执行加法。
Stack Overflow用户
发布于 2012-03-30 17:43:57
我认为你能做的最好的就是O(log )。下面是32位整数弹出计数的代码(以Go为单位)。如果需要的话，将其扩展到64位应该是显而易见的，希望注释能够清楚地说明实际发生了什么：
func popCount(n uint32) int {
// each bit in n is a one-bit integer that indicates how many bits are set
// in that bit.
n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555)
// Now every two bits are a two bit integer that indicate how many bits were
// set in those two bits in the original number
n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333)
// Now we're at 4 bits
n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F)
// 8 bits
n = ((n & 0xFF00FF00) >> 8) + (n & 0x00FF00FF)
// 16 bits
n = ((n & 0xFFFF0000) >> 16) + (n & 0x0000FFFF)
// kaboom - 32 bits
return int(n)
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/9946115
复制相关文章
相似问题
腾讯云开发者
