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.