在Matlab中有效计算汉明重量

[poster]

给定MATLAB uint32被解释为位字符串，计算该字符串中有多少个非零位的有效而简洁的方法是什么？

我有一种可行的，幼稚的方法，可以遍历所有位，但是对于我的需求来说太慢了。 （使用std :: bitset count（）的C ++实现几乎立即运行）。

我找到了一个不错的页面，其中列出了各种位计数技术，但是我希望有一种简单的MATLAB风格的方法。

http://graphics.stanford.edu/~seande...ntBitsSetNaive


更新＃1

刚刚实现了Brian Kernighan算法，如下所示：

w = 0; while ( bits > 0 ) bits = bitand( bits, bits-1 ); w = w + 1; end 性能仍然很糟糕，仅需10秒即可计算4096 ^ 2重量计算。我的C ++代码使用std :: bitset中的count（）可以在不到一秒钟的时间内完成此操作。


更新＃2

这是到目前为止我尝试过的技术的运行时间表。我会在收到其他想法/建议时对其进行更新。

向量化Scheiner算法=> 2.243511秒向量化的朴素Bitget循环=> 7.553345秒Kernighan算法=> 17.154692秒length（find（bitget（val，1:32）））=> 67.368278秒nnz（bitget（val，1:32））=> 349.620259秒贾斯汀·席纳（Justin Scheiner）的算法，展开循环=> 370.846031秒贾斯汀·席纳（Justin Scheiner）的算法=> 398.786320秒天真的bitget循环=> 456.016731秒sum（dec2bin（val）=='1'）=> 1069.851993秒


评论 ：MATLAB中的dec2bin（）函数似乎实现得很差。它运行非常慢。

评论 ：“朴素的bitget循环”算法实现如下：

w=0; for i=1:32 if bitget( val, i ) == 1 w = w + 1; end end 评论 ：Scheiner算法的循环展开版本如下所示：

function w=computeWeight( val ) w = val; w = bitand(bitshift(w, -1), uint32(1431655765)) + ... bitand(w, uint32(1431655765)); w = bitand(bitshift(w, -2), uint32(858993459)) + ... bitand(w, uint32(858993459)); w = bitand(bitshift(w, -4), uint32(252645135)) + ... bitand(w, uint32(252645135)); w = bitand(bitshift(w, -8), uint32(16711935)) + ... bitand(w, uint32(16711935)); w = bitand(bitshift(w, -16), uint32(65535)) + ... bitand(w, uint32(65535));
回答：
我很想知道这个解决方案有多快：

function r = count_bits(n) shifts = [-1, -2, -4, -8, -16]; masks = [1431655765, 858993459, 252645135, 16711935, 65535]; r = n; for i=1:5 r = bitand(bitshift(r, shifts(i)), masks(i)) + ... bitand(r, masks(i)); end 回过头来，我看到这是在bithacks页面上给出的“并行”解决方案。



更多&回答...