Efficient way to find the flags enum length?

Question

Consider this:

[Flags]
enum Colors
{
    Red=1,
    Green=2,
    Blue=4
}

Colors myColor=Colors.Red|Colors.Blue;

Currently, I'm doing it as follows:

int length=myColors.ToString().Split(new char[]{','}).Length;

But I hope there is a more efficient way of finding the length, maybe based on bitset operations.

Please, if possible, provide explanation why and how your solution works.

Also, if this a duplicate, please point to it and I'll delete this question. The only similar questions on SO I've been able to find were concerned about finding the length of all possible combinations of Colors enum, but not of the myColors variable.

UPDATE: I carefully benchmarked every solution (1 000 000 iterations each) and here is the results:

1. Stevo3000 - 8ms
2. MattEvans - 10ms
3. Silky - 34ms
4. Luke - 1757ms
5. Guffa - 4226ms
6. Tomas Levesque - 32810ms

The Stevo3000 is a clear winner (with Matt Evans holding silver medal).

Thank you very much for your help.

UPDATE 2: This solution runs even faster: 41 ms for 100 000 000 iterations (roughly 40 times faster (32bit OS) than Stevo3000)

UInt32 v = (UInt32)co;
v = v - ((v >> 1) & 0x55555555); 
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 
UInt32 count = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; 

Answer 1

The following code will give you the number of bits that are set for a given number of any type varying in size from byte up to long.

public static int GetSetBitCount(long lValue)
{
  int iCount = 0;

  //Loop the value while there are still bits
  while (lValue != 0)
  {
    //Remove the end bit
    lValue = lValue & (lValue - 1);

    //Increment the count
    iCount++;
  }

  //Return the count
  return iCount;
}

This code is very efficient as it only iterates once for each bit rather than once for every possible bit as in the other examples.

Answer 2

Here are a few extension methods to manipulate Flags enumerations :

public static class EnumExtensions
{
    private static void CheckEnumWithFlags<T>()
    {
        if (!typeof(T).IsEnum)
            throw new ArgumentException(string.Format("Type '{0}' is not an enum", typeof(T).FullName));
        if (!Attribute.IsDefined(typeof(T), typeof(FlagsAttribute)))
            throw new ArgumentException(string.Format("Type '{0}' doesn't have the 'Flags' attribute", typeof(T).FullName));
    }

    public static bool IsFlagSet<T>(this T value, T flag) where T : struct
    {
        CheckEnumWithFlags<T>();
        long lValue = Convert.ToInt64(value);
        long lFlag = Convert.ToInt64(flag);
        return (lValue & lFlag) != 0;
    }

    public static IEnumerable<T> GetFlags<T>(this T value) where T : struct
    {
        CheckEnumWithFlags<T>();
        foreach (T flag in Enum.GetValues(typeof(T)).Cast<T>())
        {
            if (value.IsFlagSet(flag))
                yield return flag;
        }
    }

    public static T SetFlags<T>(this T value, T flags, bool on) where T : struct
    {
        CheckEnumWithFlags<T>();
        long lValue = Convert.ToInt64(value);
        long lFlag = Convert.ToInt64(flags);
        if (on)
        {
            lValue |= lFlag;
        }
        else
        {
            lValue &= (~lFlag);
        }
        return (T)Enum.ToObject(typeof(T), lValue);
    }

    public static T SetFlags<T>(this T value, T flags) where T : struct
    {
        return value.SetFlags(flags, true);
    }

    public static T ClearFlags<T>(this T value, T flags) where T : struct
    {
        return value.SetFlags(flags, false);
    }

    public static T CombineFlags<T>(this IEnumerable<T> flags) where T : struct
    {
        CheckEnumWithFlags<T>();
        long lValue = 0;
        foreach (T flag in flags)
        {
            long lFlag = Convert.ToInt64(flag);
            lValue |= lFlag;
        }
        return (T)Enum.ToObject(typeof(T), lValue);
    }
}

In your case you can use the GetFlags method :

int count = myColors.GetFlags().Count();

It's probably not as efficient as Luke's answer, but it's easier to use...

Answer 3

Here's my take on this... it counts the number of set bits in the value

int val = (int)myColor;
int count = 0;

while (val > 0)
{
    if((val & 1) != 0)
    {
        count++;
    }

    val = val >> 1;
}

Answer 4

Here's a reasonably easy way of counting the bits. Each bit is shifted in-turn to the LSB of an Int64 which is AND-ed with 1 (to mask out any of the other bits) and then added to the running total.

int length = Enumerable.Range(0, 64).Sum(x => ((long)myColor >> x) & 1);

Answer 5

A rough approximation will be just counting the number of bits set in myColors, but that will only work if every enumeration members' value is power of 2.

Answer 6

Assuming they are flags, you can just use one of the methods here, to count the number of bits set.

It works because, as long as they are flags, when each one is 'OR'd' on, it sets one bit.

-- Edit

Sample code using one of the methods on that link:

[Flags]
enum Test
{
    F1 = 1,
    F2 = 2,
    F3 = 4
}


class Program
{
    static void Main(string[] args)
    {
        int v = (int) (Test.F1 | Test.F2 | Test.F3); // count bits set in this (32-bit value)
        int c = 0; // store the total here
        int[] S = {1, 2, 4, 8, 16}; // Magic Binary Numbers
        int[] B = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};

        c = v - ((v >> 1) & B[0]);
        c = ((c >> S[1]) & B[1]) + (c & B[1]);
        c = ((c >> S[2]) + c) & B[2];
        c = ((c >> S[3]) + c) & B[3];
        c = ((c >> S[4]) + c) & B[4];

        Console.WriteLine(c);
        Console.Read();
    }
}

Answer 7

I've made a helper method for myself. Maybe it'll be useful for others.

public static class EnumHelper 
{
    public static UInt32 NumFlags(this Enum e)
    {
        UInt32 v = Convert.ToUInt32(e);
        v = v - ((v >> 1) & 0x55555555);
        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
        UInt32 count = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
        return count;
    }
}