Problem 808. Hamming Weight - Fast

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Hamming Weight,</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Hamming_weight\"><w:r><w:t>wiki Hamming Weight</w:t></w:r></w:hyperlink><w:r><w:t>, in its most simple form is the number of ones in the binary representation of a value.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The task here is to create a fast Hamming Weight function/method such that processing many 4K x 4K images of 32 bit integer can be evaluated rapidly. Saw this question posed on Stack Overflow.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> Vector of length N of 32 bit integer values.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> Vector of number of ones of the binary representation</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Scoring:</w:t></w:r><w:r><w:t> Time in milliseconds to process a [4096*4096,1] vector</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Examples:</w:t></w:r><w:r><w:t> Input [7 ; 3], output=[3;2]; [16 32], output [1;1]; [0 4294967295] output [0;32]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Timing Test vector:</w:t></w:r><w:r><w:t> uint32(randi(2^32,[4096*4096,1])-1)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Minimum vector length/increment:</w:t></w:r><w:r><w:t> 65536</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Helpful, possibly, global variables.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>b1=uint32(1431655765); b2=uint32(858993459); b3=uint32(252645135) b4=uint32(16711935); b5=uint32(65535);</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Hex: b1=55555555 b2=33333333 b3=0F0F0F0F b4=00FF00FF b5=0000FFFF</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The array num_ones is created for values 0-65535 (0:2^16-1). num_ones(1)=0, num_ones(2)=1, num_ones(3)=1,num_ones(4)=2,...num_ones(65536)=15</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Due to lack of zero indexing num_ones(value+1) is number of ones for value.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Hint: Globals are not good for time performance.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Hint: Segmentation appears to provide significant time optimization potential.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

The Hamming Weight, <a href="http://en.wikipedia.org/wiki/Hamming_weight">wiki Hamming Weight</a>, in its most simple form is the number of ones in the binary representation of a value.The task here is to create a fast Hamming Weight function/method such that processing many 4K x 4K images of 32 bit integer can be evaluated rapidly. Saw this question posed on Stack Overflow.Input: Vector of length N of 32 bit integer values.Output: Vector of number of ones of the binary representationScoring: Time in milliseconds to process a [4096*4096,1] vectorExamples: Input [7 ; 3], output=[3;2]; [16 32], output [1;1]; [0 4294967295] output [0;32]Timing Test vector: uint32(randi(2^32,[4096*4096,1])-1)Minimum vector length/increment: 65536Helpful, possibly, global variables.b1=uint32(1431655765); b2=uint32(858993459); b3=uint32(252645135) b4=uint32(16711935); b5=uint32(65535);Hex: b1=55555555 b2=33333333 b3=0F0F0F0F b4=00FF00FF b5=0000FFFFThe array num_ones is created for values 0-65535 (0:2^16-1).
num_ones(1)=0, num_ones(2)=1, num_ones(3)=1,num_ones(4)=2,...num_ones(65536)=15Due to lack of zero indexing num_ones(value+1) is number of ones for value.Hint: Globals are not good for time performance.Hint: Segmentation appears to provide significant time optimization potential.

The Hamming Weight, <http://en.wikipedia.org/wiki/Hamming_weight wiki Hamming Weight>, in its most simple form is the number of ones in the binary representation of a value.

The task here is to create a fast Hamming Weight function/method such that processing many 4K x 4K images of 32 bit integer can be evaluated rapidly. Saw this question posed on Stack Overflow.

*Input:* Vector of length N of 32 bit integer values.

*Output:* Vector of number of ones of the binary representation

*Scoring:* Time in milliseconds to process a [4096*4096,1] vector

*Examples:* Input [7 ; 3], output=[3;2];  [16 32], output [1;1]; [0 4294967295] output [0;32]

*Timing Test vector:* uint32(randi(2^32,[4096*4096,1])-1)

*Minimum vector length/increment:* 65536

Helpful, possibly, global variables.

b1=uint32(1431655765); b2=uint32(858993459); b3=uint32(252645135) b4=uint32(16711935); b5=uint32(65535);

Hex: b1=55555555 b2=33333333 b3=0F0F0F0F b4=00FF00FF b5=0000FFFF

The array num_ones is created for values 0-65535 (0:2^16-1).
num_ones(1)=0, num_ones(2)=1, num_ones(3)=1,num_ones(4)=2,...num_ones(65536)=15

Due to lack of zero indexing num_ones(value+1) is number of ones for value.

Hint: Globals are not good for time performance.

Hint: Segmentation appears to provide significant time optimization potential.

Solve

Solution Stats

60 Solutions
10 Solvers

Last Solution submitted on Mar 06, 2019

Last 200 Solutions

Solution Comments

Solution 1319034

1 Comment

1 Comment

Shlomo Geva on 29 Oct 2017

1. This solution is much faster on re-invocation than the one without the persistent num_ones variable. Unless of course it is performed on a much larger (than num_ones) array of 32-bit integer.

2. It is essential to have the statement
x= double(x);
The reason for this is that the floor() function has a problem with precision. If can fail with 32-bit integer that are close to 2^32.
For instance, consider this Matlab code and system response:

>> p=uint32(4294946031)

p =

uint32

4294946031

>> floor(p/65536)

ans =

uint32

65536

Problem Recent Solvers10

Problem Tags

bit manipulation bitand bitshift compression floor mod uint32

Community Treasure Hunt

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

Start Hunting!