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.

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

Problem 808. Hamming Weight - Fast

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers10

Suggested Problems

More from this Author236

Problem Tags

Problem 808. Hamming Weight - Fast

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers10

Suggested Problems

More from this Author236

Problem Tags

Players