10,000 16-bit integers is a very small number of integers to process. You can just go through all of the numbers and add up each set bit.
count = 0
for (x in numbers)
for (bit in 0 to 15)
count += (x >> bits) & 1
If you had, say, 10 billion integers, you could do clever things like precomputing the # of set bits in ever possible 16-bit integer. That would mean 2^16 computations at the beginning, and then you would only have to add 10 billion numbers instead of 16 * 10 billion numbers. In this case, since you only have 10,000 numbers, that kind of optimization is pointless.
You can go halfway and precompute the number of bits in all 8-bit combinations, then add up 10,000 pairs of counts.
precomputed = int[256]
for (num in 0 to 255)
precomputed[num] = the number of set bits in num
count = 0
for (x in numbers)
count += precomputed[x & 0xFF] + precomputed[(x >> 8) & 0xFF]
But again, with 10,000 numbers, these kind of optimizations won't have any appreciable difference.
No matter what, your runtime will be O(n), but these kinds of optimizations will let you lower the constant term by a little bit.
Read full article from (4) What is the fastest way to count the total number of set bits in an array of a ten thousand 16 bit integers? - Quora
No comments:
Post a Comment