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

10 views (last 30 days)
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

Accepted Answer

Cedric
Cedric on 1 Mar 2013
Edited: Cedric on 1 Mar 2013
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 Comments
James Tursa
James Tursa on 2 Mar 2013
Edited: James Tursa on 2 Mar 2013
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
Cedric on 2 Mar 2013
Edited: Cedric on 2 Mar 2013
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!

Sign in to comment.

More Answers (1)

James Tursa
James Tursa on 1 Mar 2013
Edited: James Tursa on 1 Mar 2013
See this FEX submission:
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).

Categories

Find more on Mix Analog and Digital Signals in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!