给定一个 MATLAB uint32 被解释为一个位串,什么是计算字符串中有多少非零位的高效和简洁的方法?
我有一个可行的、天真的方法,它循环遍历位,但这对我的需要来说太慢了。 (使用 std::bitset count() 的 C++ 实现几乎立即运行)。
我找到了一个非常不错的页面,其中列出了各种位计数技术,但我希望有一种简单的 MATLAB 式方法。
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive
更新#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
这是我迄今为止尝试过的技术的运行时间表。我会在收到更多想法/建议时对其进行更新。
Vectorized Scheiner algorithm => 2.243511 sec Vectorized Naive bitget loop => 7.553345 sec Kernighan algorithm => 17.154692 sec length( find( bitget( val, 1:32 ) ) ) => 67.368278 sec nnz( bitget( val, 1:32 ) ) => 349.620259 sec Justin Scheiner's algorithm, unrolled loops => 370.846031 sec Justin Scheiner's algorithm => 398.786320 sec Naive bitget loop => 456.016731 sec sum(dec2bin(val) == '1') => 1069.851993 sec
Comment: The dec2bin() function in MATLAB seems to be very poorly implemented. It runs extremely slow.
Comment: The "Naive bitget loop" algorithm is implemented as follows:
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 页面上给出的“并行”解决方案。
关于matlab - 在matlab中有效计算汉明权重,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1024904/