汉明权重只用二进制操作编写吗? [英] Hamming weight written only in binary operations?
问题描述
我只需要根据二进制运算(&,^,>>)来写一个字节汉明权重的表达式;没有任何循环,只是一个公式.
I need to write an expression of one byte Hamming weight in terms of binary operations only (&, ^, >>); without any loop, just a formula.
我知道有很多算法可以计算汉明权重,但是它们都使用算术运算或循环运算.
I know that there are plenty algorithms, that allow computing Hamming weight, but all of them use arithmetical operations or looping.
如果我们采用 http://en.wikipedia.org/wiki/Hamming_weight http://en.wikipedia.org/wiki/Hamming_weight ,那么第一个和D = B + C可以写成D = B ^ C ^(B& C << 1),但随后的两个和更复杂.
If we take an algorithm from http://en.wikipedia.org/wiki/Hamming_weight, then the first sum D=B+C can be written as D = B^C^(B&C << 1), but two following sums are more complicated.
有人暗示吗?
更新: 谢谢你们的帮助.实际上,我需要以下内容:
UPDATE: Thank you for help guys. Actually, I needed something like following:
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;
}
此代码将导致汉明权重为变量 in .它不包含任何+,-或比较指令,并且可以在8位微控制器上工作. 但是,与大多数其他解决方案相比,它需要更多的操作.现在,我正在尝试简化它.
This code will result in Hamming weight of variable in. It does not contain any +, -, or comparison instructions and it can work on 8bits microcontrollers. Nevertheless, it takes more operations than most of other solutions. Now, I am trying to simplify it.
UPDATE2:@Evgeny Kluev提出了另一种基于64位寄存器的解决方案
UPDATE2: Another solution, based on 64 bits registers, is proposed by @Evgeny Kluev
推荐答案
我不确定这是否是您要搜索的内容,但这只是一个仅使用移位和按位运算的公式:
I'm not sure if this is what you search for, but here is just a formula using only shifts and bitwise and:
int weight(unsigned char x)
{
return ((0x876543210 >>
(((0x4332322132212110 >> ((x & 0xF) << 2)) & 0xF) << 2)) >>
((0x4332322132212110 >> (((x & 0xF0) >> 2)) & 0xF) << 2))
& 0xf;
}
这里的移位操作两次被用来代替数组索引(查找4位汉明权重).还有另一种移位操作使用数组索引执行加法.
Here shift operation is twice used as a substitute for array indexing (to find 4-bit hamming weights). And one more shift operation uses array indexing to perform addition.
这篇关于汉明权重只用二进制操作编写吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!