3 ms·
"how do you count the bits most efficiently?" What does this even mean?
by sonoffett 10y ago
"how do you count the bits most efficiently?"
What does this even mean?
- UK-AL 10y agoWhat i think he means is counting the amount of set(1) bits in the array,
- sonoffett 10y agoThanks, the question makes more sense now :)
- dekhn 10y agoIf you have a collection of data, and you want to know the number of 1 bits, and you want to do it with a minimum of resources... what is the process? For example, standard bit-shifting and masking the lowest bit to set a counter is one way to do this. Possibly there are other, faster ways, such as using a lookup table (a byte or more can be "counted" at a time). Of course, because so many people were doing this, intel added a popcnt instruction which probably is more efficient (faster) than either of the above, at the expense of more CPU real estate, heat, etc. Turns out counting 1 bits in a dataset is a super-important problem that shows up in a lot of situations.