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

41 Solutions
8 Solvers

Last Solution submitted on Oct 17, 2019

Last 200 Solutions

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 Solvers8

Problem Tags

bitand bitshift floor hamming mod uint32

Problem 810. Hamming Weight - Size Scoring

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers8

Suggested Problems

More from this Author236

Problem Tags

Problem 810. Hamming Weight - Size Scoring

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers8

Suggested Problems

More from this Author236

Problem Tags

Players