Problem 810. Hamming Weight - Size Scoring

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> Total 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> Normal Cody Size, while solving multiple cases without timing out</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Examples: Input [7 ; 3], output=[3 ; 2]; [16 32], output [1 ; 1]; [0 4294967295] output [ 0 ; 32] FFFFFFFF Hex = 2^32-1</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Stressing Test vector : 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: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: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: Total number of ones of the binary representationScoring: Normal Cody Size, while solving multiple cases without timing outExamples: Input [7 ; 3], output=[3 ; 2]; [16 32], output [1 ; 1]; [0 4294967295] output [ 0 ; 32] FFFFFFFF Hex = 2^32-1Stressing Test vector : uint32(randi(2^32,[4096*4096,1])-1)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=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.

Solve

Solution Stats

45 Solutions
9 Solvers

Last Solution submitted on Nov 08, 2020

Last 200 Solutions

Problem Comments

Solution Comments

Solution 137474

1 Comment

1 Comment

Tomasz on 11 Jan 2013

hmm, the same one (and similar ones) time out for me :(

Problem Recent Solvers9

Problem Tags

bitand bitshift floor hamming mod uint32

Community Treasure Hunt

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

Start Hunting!

Problem 810. Hamming Weight - Size Scoring

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers9

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Problem 810. Hamming Weight - Size Scoring

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers9

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Players