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
-
22266 Solvers
-
293 Solvers
-
230 Solvers
-
678 Solvers
-
Choose the best fitting dominoes
206 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!