Fastest way to count the number of 1's in a n-bit number

Figure out the fastest way to count the number of 1's in a n-bit number. Also, code it up as part of a function and then call the function on an arbitrary-length number. Assume that each 32bits of the number are stored in an integer array as shown below:

320 bit number is represented as:

int a[10];

a[9] = 0x99999999;
a[8] = 0x88888888;
....
a[0] = 0x0;

So, this number 320-bit number is:

0x9999 9999 8888 8888 7777 7777 ....0000 0000

Bit Twiddling Hacks

You might want to read this link.

The fastest way to do what you want would involve lookup tables and/or specific assumptions/knowledge about relative performance of certain bitwise/numeric operators on your target machine/environment.

The answer depends on the result.
Some of the algorithms have a running time proportional to the number of bits that were set. In those cases they are the fastest algorithm if the number of bits set is below some threshold. Unfortunately if you don't have any idea of the number of bits set in advance then you can't know which algorithm to pick. (Chicken & egg scenario)

The only algorithm that can therefore be considered the fastest is the popcount family of intrinsics, which isn't really an algorithm at all since the hardware just does it for you.

You forgot to ask a question, and do not simply presume to pass your work on to us. We will not do it for you!