在MATLAB计算效率重量海明 [英] Calculating Hamming weight efficiently in matlab

问题描述

给定一个MATLAB UINT32是PTED作为一个位串间$ P $，什么是计算有多少非零位字符串中的高效和简洁的方式？

我有哪些循环在位的工作，天真的做法，但是这是我的需求太慢。 （使用的std :: bitset的数（）A C ++实现运行几乎是瞬间）。

我已经找到了pretty不错页面列出了多种位计算技术，但我希望有一个简单的MATLAB的去年秋季的方式。

<一个href=\"http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive\">http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

更新＃1

刚刚实施的布莱恩Kernighan的算法如下：

  W = 0;
而（比特0）
    位= BITAND（比特，比特-1）;
    W = W + 1;
结束
 

表现依然糟糕，在10秒内只计算4096平方公尺重量计算。我的C ++ code使用count（）从和std :: bitset这是否在一秒时间。

更新＃2

下面是迄今我已经试过了技术运行时间的表。我得到更多的想法/建议，我将更新它。

矢量算法沙伊纳=> 2.243511秒
矢量天真bitget循环=> 7.553345秒
Kernighan的算法=> 17.154692秒
长度（找到（bitget（VAL，1:32）））=> 67.368278秒
NNZ（bitget（VAL，1:32））=> 349.620259秒
贾斯汀·沙伊纳的算法，展开循环=> 370.846031秒
贾斯汀·沙伊纳算法=> 398.786320秒
天真bitget循环=> 456.016731​​秒
总和（DEC2BIN（VAL）=='1'）=> 1069.851993秒

注释：在MATLAB中DEC2BIN（）函数似乎很差实施。它运行极其缓慢。

注释：以朴素bitget循环的算法实现如下：

  W = 0;
对于i = 1：32
   如果bitget（VAL，I）== 1
       W = W + 1;
   结束
结束
 

注释：
沙伊纳算法的循环展开版本看起来如下：

 函数w = computeWeight（VAL）
W = VAL;
W = BITAND（bitshift（重量，-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））;
 

解决方案

我很想看到这个解决方案是如何快速：

 函数r = count_bits（N）偏移= [-1，-2，-4，-8，-16];
口罩= [1431655765，858993459，252645135，16711935，65535]。R = N;
对于i = 1：5
   R = BITAND（bitshift（R，班次（I）），防毒面具（I））+ ...
      BITAND（R，口罩（ⅰ））;
结束
 

要返回去，我看，这是bithacks页上给出的'水货'的解决方案。

Given a MATLAB uint32 to be interpreted as a bit string, what is an efficient and concise way of counting how many nonzero bits are in the string?

I have a working, naive approach which loops over the bits, but that's too slow for my needs. (A C++ implementation using std::bitset count() runs almost instantly).

I've found a pretty nice page listing various bit counting techniques, but I'm hoping there is an easy MATLAB-esque way.

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Update #1

Just implemented the Brian Kernighan algorithm as follows:

w = 0;
while ( bits > 0 )
    bits = bitand( bits, bits-1 );
    w = w + 1;
end

Performance is still crappy, over 10 seconds to compute just 4096^2 weight calculations. My C++ code using count() from std::bitset does this in subsecond time.

Update #2

Here is a table of run times for the techniques I've tried so far. I will update it as I get additional ideas/suggestions.

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

Comment: The loop unrolled version of Scheiner's algorithm looks as follows:

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));

解决方案

I'd be interested to see how fast this solution is:

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

Going back, I see that this is the 'parallel' solution given on the bithacks page.

这篇关于在MATLAB计算效率重量海明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！