Check Parity of a uint32 Without Converting to a Binary String?

Question

David 2013-2-28

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/65419-check-parity-of-a-uint32-without-converting-to-a-binary-string

In the simplest form, my task is to count the number of ones in a 32 bit unsigned integer. To do this, I am currently converting the integers to binary strings with “dec2bin”. The problem is I need to count the ones in millions of 32 bit data words, and the binary strings take up too much space, so I’m forced to do small chunks at a time. Is there a way to do this without converting from the uint32 class?

Thanks

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Cedric 2013-3-1

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/65419-check-parity-of-a-uint32-without-converting-to-a-binary-string#answer_76952

编辑：Cedric 2013-3-1

在 MATLAB Online 中打开

http://www.mathworks.com/matlabcentral/fileexchange/21025-count-on-off-or-calculate-simple-parity-bits-of-input

But if I had 30s to find a solution for doing it "by hand" in MATLAB, I would build something like that:

 >> a = uint32(31) ; sum(bitand(a, uint32(2.^(0:31)))~=0)
 ans =
        5

Cheers,

Cedric

EDIT: or, to operate on an array of uint32's:

 >> data   = uint32(1:16) ;
 >> masks  = uint32(2.^(0:31)) ;
 >> counts = arrayfun(@(d)sum(bitand(d, masks)~=0), data)
 counts =
       1   1   2   1   2   2   3   1   2   2   3   2   3   3   4   1

EDIT2: or even faster:

 >> data   = uint32(1:1e6) ;  % Example with 1 million uint32's.
 >> counts = sum( bitand(repmat(data(:), 1, 32), ...
                         repmat(uint32(2.^(0:31)), numel(data), 1)) ~= 0, ...
                  2 ) ;

8 个评论
显示 6更早的评论隐藏 6更早的评论

David 2013-3-1

编辑：David 2013-3-1

在 MATLAB Online 中打开

Thanks Cedric and James,

IT frowns upon downloading any old file from the internet without their blessing. That's a simple idea with the bit masks. I'm going to try a variation on your first edit. The "repmat(data(:), 1, 32)" part of the second edit looks like it would take up more space than the binary string.

EDIT: I forgot about arrayfun. That gave me the power to do it a way I was trying to origionally. It's just a little bit faster than your mask method.

MATLAB code
data = uint32(1:1e6);
>> masks = uint32(2.^(0:31));
>> tic
counts = arrayfun(@(d)sum(bitand(d, masks)~=0), data);
toc
Elapsed time is 6.807613 seconds.
>> tic
counts2 = arrayfun(@(d)sum(bitget(d,24:-1:1)),data);
toc
Elapsed time is 6.707375 seconds.

EDIT2: That first comparison on execution time wasnt apples to apples. I only did 24 bits for the bitget instead of 32...

MATLAB code
>> tic
counts2 = arrayfun(@(d)sum(bitget(d,32:-1:1)),data);
toc
Elapsed time is 6.743967 seconds.

James Tursa 2013-3-2

编辑：James Tursa 2013-3-2

在 MATLAB Online 中打开

For 64-bit installations I guess I can empathize ... but for 32-bit installations MATLAB comes with the lcc compiler already pre-installed. Given the types of memory and speed advantages that can be gained with mex routines, particularly when one is working with very large arrays, IMO it is worth it to invest a little time in learning how to use the mex stuff. Heck, just how hard is it to type this at the command line:

mex onbits.c

(Comments not directed at you personally Cedric ... just a side rant on my part)

Cedric 2013-3-2

编辑：Cedric 2013-3-2

I completely understand, James. As I wrote above, I've been trying to push people around me quite a bit on related topics, for years, and without any success!

请先登录，再进行评论。

Answer 2

James Tursa 2013-3-1

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/65419-check-parity-of-a-uint32-without-converting-to-a-binary-string#answer_76951

编辑：James Tursa 2013-3-1

See this FEX submission:

http://www.mathworks.com/matlabcentral/fileexchange/21025-count-on-off-or-calculate-simple-parity-bits-of-input

Should be pretty fast for your application, but I will warn you that it does not use the fastest C algorithm. I know of faster algorithms but haven't updated this submission yet. I also haven't updated it yet to be self-building, so you will have to manually build the C mex routine (see the instructions).