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

44.94% Correct | 55.06% Incorrect
Last Solution submitted on Dec 07, 2023

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers17

Suggested Problems

More from this Author294

Community Treasure Hunt

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

Start Hunting!