Problem 808. Hamming Weight - Fast
The 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.
Solution Stats
Problem Comments
-
1 Comment
Good problem with detailed description!
Solution Comments
Show commentsProblem Recent Solvers17
Suggested Problems
-
3281 Solvers
-
Back to basics 20 - singleton dimensions
268 Solvers
-
Volume difference between Ellipsoid and Sphere
127 Solvers
-
345 Solvers
-
13591 Solvers
More from this Author308
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!