Counting bits in a ulong

[ketmar]

H. S. Teoh wrote:

> The third alternative is known as Kernighan's trick, which involves a
> loop that executes exactly as many times as the number of 1 bits:
>
>         uint count;
>         for (count = 0; val; count++)
>         {
>             val &= val - 1;
>         }
>         return count;
>
> (How it does this is left as an exercise for the reader. It's really
> quite clever.)  This comes with the advantage of a very low instruction
> count, but it does have a branch that isn't easily predictable, so
> actual execution time is marginally slower.

actually, that branch has very good prediction rate. it should be predicted 
most of the time, and when predictor failed, it is mostly doesn't matter, 
because we're done with the loop. coincidentally, this is what your 
benchmarking results demonstrates. ;-)