On Oct 18, 9:25 pm, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]>
wrote:
> Hi all:
>
> I met a problem in the programming pearls as follow:
>
> Q: Given a very long sequence(say, billions or trillions) of bytes,
> how would you efficiently count the total number of one bits?
>
> A: The first approach is to count the number of one bits in each
> input unit(perhaps an 8-bit character or perhaps a 32-bit integer),
> and sum them. To find the number of one bits in a 16-bit integer, one
> could look at each bit in order, or iterate through the bits that are
> on, or perform a lookup in a table of. What effect will the cache
> size have on your choice of unit?
>
> The second approach is to count the number of each input unit in
> th input, and then at the end take the sum of that number multiplied
> by the number of one bits in that unit.
>
> My question is, I am puzzled about the solution. What's the
> difference of the two approaches? In the second approach, what are
> multiplied?
You're right. The explanation isn't clear. Suppose a "unit" is a
byte. I think he is saying to count the number of bytes having each
unique value 0, 1, 2, ... 255. This forms a histogram. Then just
multply each count in the histogram by the number of 1's in the bin
number, i.e. 0, 1, 1, 2, 1, 2, 2, 3, ... 8. (These can be precomputed
in a table.) Then add up these products to get the total.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
