Assuming that they want the number of 1 bits (the question asked for the number of bits, not the number of 1 bits--hence my answer), it is not obvious to me that a lookup table is the fastest.
Given an unsigned 32-bit value, v, this well-known bit hack [1] counts the number of 1 bits:
v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
count = ((v + (v >> 4) & 0x0F0F0F0F) * 0x01010101) >> 24;
If you can treat the 10000 16-bit values as 5000 32-bit values, applying the above 5000 times might be as fast or faster than applying the table lookup method to 20000 bytes. It will depend on precise details of the particular computer on which it is run.
Given an unsigned 32-bit value, v, this well-known bit hack [1] counts the number of 1 bits:
If you can treat the 10000 16-bit values as 5000 32-bit values, applying the above 5000 times might be as fast or faster than applying the table lookup method to 20000 bytes. It will depend on precise details of the particular computer on which it is run.[1] http://graphics.stanford.edu/~seander/bithacks.html