我只需要用二进制运算(&,^,>>)来写一个汉字加权一个字节的表达式; 没有任何循环,只是一个公式。
我知道有很多算法可以计算汉明重量,但所有算法都使用算术运算或循环。
如果我们从https://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))); B = x & m2; C = (x >> 2) & m2; x = B ^ C ^ ((B & C) <> 4) & m4); C = (x & ((x >> 4) & m4)) << 1; x = B ^ C ^ ((B & C) << 1); return x; }
此代码将导致汉明重量变量。 它不包含任何+, – 或比较指令,它可以在8位微控制器上工作。 然而,它需要比大多数其他解决方案更多的操作。 现在,我正在努力简化它。
UPDATE2:基于64位寄存器的另一种解决方案由@Evgeny Kluev提出
我不确定这是否是您搜索的内容,但这里只是一个仅使用shift和bitwise的公式:
int weight(unsigned char x) { return ((0x876543210 >> (((0x4332322132212110 >> ((x & 0xF) << 2)) & 0xF) << 2)) >> ((0x4332322132212110 >> (((x & 0xF0) >> 2)) & 0xF) << 2)) & 0xf; }
这里使用移位操作两次作为数组索引的替代(以找到4位汉明权重)。 还有一个移位操作使用数组索引来执行加法。
我认为你能做的最好的是O(log n)。 这是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) }
以上就是c/c++开发分享汉明重量只写在二元运算中?相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/559853.html