using System.Collections.Generic;

public class BitWise
{
    public static int HammingWeight(long x)
    {
        const long h01 = 0x0101010101010101;
        const long m1 = 0x5555555555555555; // 0101...
        const long m2 = 0x3333333333333333; // 00110011..
        const long m4 = 0x0f0f0f0f0f0f0f0f;
        x -= (x >> 1) & m1;             // put count of each 2 bits into those 2 bits
        x = (x & m2) + ((x >> 2) & m2); // put count of each 4 bits into those 4 bits
        x = (x + (x >> 4)) & m4;        // put count of each 8 bits into those 8 bits
        return (int)((x * h01) >> 56);
    }

    /// <summary>
    /// return all the permutation of n choose p, long output are bitflags were 1 bit represent selected.
    /// Exactly n bits are set to 1, among the p first bits.
    /// n parmi p
    /// </summary>
    /// <param name="totalNumberOfElement"></param>
    /// <param name="numberOfElementToSelect"></param>
    /// <returns></returns>
    public static HashSet<long> GetAllPermutation(int numberOfElementToSelect, int totalNumberOfElement)
    {
        HashSet<long> result = new HashSet<long>();
        if (numberOfElementToSelect>totalNumberOfElement)
        {
            return result;
        }        
        if(numberOfElementToSelect == 0)
        {
            result.Add(0);
            return result;
        }

        long v = (1L << numberOfElementToSelect) - 1L;
        long end = 1L << totalNumberOfElement;
        while (v < end)
        {
            result.Add(v);
            long t = (v | (v - 1L)) + 1L;
            v = t | ((((t & -t) / (v & -v)) >> 1) - 1L);
        }

        return result;
    }
}