在matlab中有效地计算汉明重量

Question

鉴于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重量计算.使用std :: bitset中的count()的我的C++代码在亚秒时间内执行此操作.

更新#2

这是我迄今为止尝试过的技术的运行时间表.我会在获得更多想法/建议时更新它.

矢量化Scheiner算法=> 2.243511秒
矢量化朴素bitget loop => 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秒
天真的比特环= = 456.016731秒
sum(dec2bin(val)=='1')=> 1069.851993秒

注释: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));

Answer 1

我有兴趣看看这个解决方案有多快:

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页面上给出的"并行"解决方案.

Answer 2

编辑:新解决方案

您似乎想要重复4096×4096 UINT32值数组中每个元素的计算.如果这是你正在做的事情,我认为在MATLAB中最快的方法是使用BITGET设计用于操作值矩阵的事实.代码如下所示:

numArray = ...your 4096-by-4096 matrix of uint32 values...
w = zeros(4096,4096,'uint32');
for iBit = 1:32,
  w = w+bitget(numArray,iBit);
end

如果你想制作一些其他算法的矢量化版本,我相信BITAND也可以在矩阵上运行.

旧解决方案......

我能想到的最简单的方法是使用DEC2BIN函数,该函数为您提供非负整数的二进制表示(作为字符串):

w = sum(dec2bin(num) == '1');  % Sums up the ones in the string

它很慢,但很容易.=)

Answer 3

除非这是一个MATLAB实现练习,否则您可能只想采用快速C++实现并将其编译为mex函数,每个目标平台一次.

Answer 4

从顶部的斯坦福链接实现了"最佳32位算法".改进的算法将处理时间缩短了6%.还优化了分段大小,发现32K稳定,比4K时间缩短了15%.预计4Kx4K时间为矢量化Scheiner算法的40%.

function w = Ham(w)
% Input uint32
% Output vector of Ham wts
 for i=1:32768:length(w)
  w(i:i+32767)=Ham_seg(w(i:i+32767));
 end
end

% Segmentation gave reduced time by 50%

function w=Ham_seg(w)
 %speed
 b1=uint32(1431655765); 
 b2=uint32(858993459);
 b3=uint32(252645135);
 b7=uint32(63); % working orig binary mask

 w = bitand(bitshift(w, -1), b1) + bitand(w, b1);
 w = bitand(bitshift(w, -2), b2) + bitand(w, b2);
 w =bitand(w+bitshift(w, -4),b3);
 w =bitand(bitshift(w,-24)+bitshift(w,-16)+bitshift(w,-8)+w,b7);

end