14

给定要解释为位字符串的 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

性能仍然很糟糕，仅计算 4096^2 权重计算需要超过 10 秒。我的 C++ 代码使用 std::bitset 中的 count() 可以在亚秒时间内完成。


更新#2

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

矢量化 Scheiner 算法 => 2.243511 秒
矢量化 Naive bitget 循环 => 7.553345 秒
Kernighan 算法 => 17.154692 秒
长度（查找（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() 函数似乎实现得很差。它运行非常缓慢。

评论：“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));
4

9 回答 9

9

我很想看看这个解决方案有多快：

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

于 2009-06-22T01:23:47.693 回答
5

编辑：新解决方案

您似乎想对 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

它很慢，但很容易。=)

于 2009-06-21T23:49:56.993 回答
5

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

于 2009-06-22T00:24:53.117 回答
5

从顶部的斯坦福链接实现了“最佳 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
于 2012-07-01T16:24:24.550 回答
1

在 Matlab Cody 上做了一些时序比较。确定分段修改矢量化 Scheiner 可提供最佳性能。

对于 L=4096*4096 向量，基于 Cody 1.30 秒到 0.60 秒的变化，时间减少 >50%。

function w = Ham(w)
% Input uint32
% Output vector of Ham wts

 b1=uint32(1431655765); % evaluating saves 15% of time 1.30 to 1.1 sec
 b2=uint32(858993459);
 b3=uint32(252645135);
 b4=uint32(16711935);
 b5=uint32(65535);

 for i=1:4096:length(w)
  w(i:i+4095)=Ham_seg(w(i:i+4095),b1,b2,b3,b4,b5);
 end
end

% Segmentation reduced time by 50%

function w=Ham_seg(w,b1,b2,b3,b4,b5)
 % Passing variables or could evaluate b1:b5 here


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

end





vt=randi(2^32,[4096*4096,1])-1;
% for vt being uint32 the floor function gives unexpected values
tic
v=num_ones(mod(vt,65536)+1)+num_ones(floor(vt/65536)+1); % 0.85 sec
toc
% a corrected method is
v=num_ones(mod(vt,65536)+1)+num_ones(floor(double(vt)/65536)+1);
toc
于 2012-07-01T06:12:16.327 回答
1

一种快速的方法是使用查找表计算每个字节中的位，然后将这些值相加；实际上，这是问题中给出的网页上建议的方法之一。这种方法的好处是，查找和求和都是 MATLAB 中的矢量化操作，因此您可以对这种方法进行矢量化，并同时非常快速地计算大量位串的汉明权重/设置位数。这种方法在 MATLAB File Exchange 上的bitcount提交中实现。

于 2013-11-27T11:34:38.310 回答
0

尝试将工作分成更小的部分。我的猜测是，如果您想一次处理所有数据，matlab 会尝试在执行连续步骤之前对所有整数执行每个操作，并且处理器的缓存在每个步骤中都会失效。

for i=1:4096,
    «process bits(i,:)»
end
于 2009-06-22T01:35:36.733 回答
0

我在这里恢复了一个旧线程，但我遇到了这个问题，我为此写了一点代码：

distance = sum(bitget(bits, 1:32));

看起来很简洁，但我害怕bitget在 O(n)bitshift操作中实现。该代码适用于我的工作，但我的问题集不依赖于汉明权重。

于 2012-02-29T06:07:50.017 回答
0 
num_ones=uint8(zeros(intmax('uint32')/2^6,1));
% one time load of array not implemented here
tic
for i=1:4096*4096
 %v=num_ones(rem(i,64)+1)+num_ones(floor(i/64)+1); % 1.24 sec
 v=num_ones(mod(i,64)+1)+num_ones(floor(i/64)+1); % 1.20 sec
end
toc
tic
num_ones=uint8(zeros(65536,1));
for i=0:65535
 num_ones(i+1)=length( find( bitget( i, 1:32 ) ) ) ;
end
toc
% 0.43 sec to load
% smaller array to initialize
% one time load of array
tic
for i=1:4096*4096
 v=num_ones(mod(i,65536)+1)+num_ones(floor(i/65536)+1); %  0.95 sec
 %v=num_ones(mod(i,65536)+1)+num_ones(bitshift(i,-16)+1); % 16 sec for 4K*1K
end
toc
%vectorized
tic
num_ones=uint8(zeros(65536,1));
for i=0:65535
 num_ones(i+1)=length( find( bitget( i, 1:32 ) ) ) ;
end % 0.43 sec
toc
vt=randi(2^32,[4096*4096,1])-1;
tic
v=num_ones(mod(vt,65536)+1)+num_ones(floor(vt/65536)+1); % 0.85 sec
toc
于 2012-06-29T14:09:38.540 回答