BitCounter

BitCounter.cs

// code from https://en.wikipedia.org/wiki/Hamming_weight
    public static class BitCounter
    {
        /// <summary>
        /// Count the number of bits set to 1 in a given value
        /// </summary>
        public static int BitCount(this int value)
        {
            return BitCount((UInt64)(value & UInt32.MaxValue));
        }
        /// <summary>
        /// Count the number of bits set to 1 in a given value
        /// </summary>
        public static int BitCount(this long value)
        {
            return BitCount((UInt64)value);
        }
        /// <summary>
        /// Count the number of bits set to 1 in a given value
        /// </summary>
        /// <remarks>
        /// This uses fewer arithmetic operations than any other known  
        /// implementation on machines with fast multiplication.
        /// This algorithm uses 12 arithmetic operations, one of which is a multiply.
        /// </remarks>
        public static int BitCount(this UInt64 value)
        {
            const UInt64 m1 = 0x5555555555555555UL; //binary: 0101...
            const UInt64 m2 = 0x3333333333333333UL; //binary: 00110011..
            const UInt64 m4 = 0x0f0f0f0f0f0f0f0fUL; //binary:  4 zeros,  4 ones ...
            const UInt64 h01 = 0x0101010101010101UL; //the sum of 256 to the power of 0,1,2,3...

            UInt64 result = value - ((value >> 1) & m1);
            result = (result & m2) + ((result >> 2) & m2);
            return (int)((((result + (result >> 4)) & m4) * h01) >> 56);
        }
        /// <summary>
        /// Count the number of bits set to 1 in a given value
        /// </summary>
        /// <remarks>
        /// This is better when most bits in x are 0
        /// This is algorithm works the same for all data sizes.
        /// This algorithm uses 3 arithmetic operations and 1 comparison/branch per "1" bit in x.
        /// </remarks>
        public static int BitCountWegner(this UInt64 value)
        {
            var x = value;
            int count = 0;
            for (count = 0; x > 0; count++)
                x &= x - 1;
            return count;
        }
    }