赞
踩
给定一个MATLAB uint32被解释为一个位串,什么是有效和简明的方式来计算字符串中有多少个非零位?
我有一个工作,天真的方法,循环了这些位,但是对我的需求来说太慢了. (使用std :: bitset count()的C实现几乎立即运行).
我发现一个漂亮的页面列出了各种计数技术,但我希望有一个简单的MATLAB-esque方式.
更新#1
刚刚实现了Brian Kernighan算法如下:
w = 0;
while ( bits > 0 )
bits = bitand( bits, bits-1 );
w = w + 1;
end
性能仍然很糟糕,超过10秒计算只有4096 ^ 2的重量计算.来自std :: bitset的使用count()的C代码在第二时间内完成.
更新#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
评论:MATLAB中的dec2bin()函数似乎执行得很差.它运行非常慢
评论:“Naive bitget loop”算法实现如下:
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));
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。