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

62 Solutions
12 Solvers

Last Solution submitted on May 30, 2023

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Arunika Oyshi on 30 May 2023 at 4:50

Good problem with detailed description!

Solution Comments

Show comments

Problem Recent Solvers12

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 808. Hamming Weight - Fast

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers12

Suggested Problems

More from this Author260

Problem Tags

Community Treasure Hunt

Problem 808. Hamming Weight - Fast

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers12

Suggested Problems

More from this Author260

Problem Tags

Community Treasure Hunt

Players