How to pick bitflag values?

https://stackoverflow.com/questions/513656

21-08-2019
|

Question

I have a set of options, some orthogonal (can be combined in any combination), some exclusive (only one from the set is allowed), and need to pick a set of enum values so that they can be combined with bit-wise or and extracted with bit-wise and. I would prefer that or-ing invalid combination would be detectable.

Are there any tools for generating enums like this?

Edit for clarity

I'm looking for something that can leverage the fact that some flags are invalid in combination to reduce the number of bits used. The requirement that I be able to detect errors is soft. I don't need to be able to tell what was used if things are mucked up.

I'm using C#, but any solution should be helpful.

An example pattern would be:

that gets 6 exclusive flags and an orthogonal pair of 2 into 6 bits

a quick test show that 5-bits gives 9 values, 6-bits give 20,...

Solution

To represent an "exclusive" set of n options (i.e. exactly one must be chosen), we require at least ceil(log2(n)) bits. For example, option k can be represented by the number k in base-2.

To represent an "orthogonal" set of n options (i.e. any combination of size 0, 1, ..., n can be chosen), we require at least n bits. For example, options k0, k1, k2 could be represented by the binary number whose bits are zero except for bits 0, 1, 2.

So, to represent multiple option sets simultaneously, we add up the number of bits required for each option set (depending on whether it is "exclusive" or "orthogonal") to get the total number of bits required.

In short, to pick the enum values,

"exclusive" option k uses k << r
"orthogonal" option k0, k1, ..., k{n-1} uses 0x1 << r, 0x1 << (r+1), ..., 0x1 << (r+n-1)

where offset r is the number of bits used by the preceding option sets.

Example of how to automate this construction, in Java:

/**
 * Construct a set of enum values, for the given sizes and types 
 * (exclusive vs orthogonal) of options sets.
 *
 * @param optionSetSizes
 *     number of elements in each option set
 * @param isOptionSetExclusive
 *     true if corresponding option set is exclusive, false if
 *     orthogonal
 * @returns
 *     array of m elements representing the enum values, where 
 *     m is the sum of option set sizes. The enum values are 
 *     given in the order of the option sets in optionSetSizes 
 *     and isOptionSetExclusive.
 */ 
int[] constructEnumValues(
        int[] optionSetSizes, 
        boolean[] isOptionSetExclusive)
{
    assert optionSetSizes.length == isOptionSetExclusive.length;

    // determine length of the return value
    int m = 0; 
    for (int i = 0; i < optionSetSizes.length; i++) m += optionSetSizes[i];
    int[] vals = new int[m];

    int r = 0; // number of bits used by the preceding options sets
    int c = 0; // counter for enum values used 

    for (int i = 0; i < optionSetSizes.length; i++)
    {
        // size of this option set
        int n = optionSetSizes[i];                   

        // is this option set exclusive?
        boolean exclusive = isOptionSetExclusive[i]; 

        for (int k = 0; k < n; k++)
        {
            vals[c] = (exclusive) ? (k << r) : (0x1 << (r + k));
            c++;
        }

        r += (exclusive) ? (int) Math.ceil(Math.log(n)/Math.log(2)) : n; 
    } 

    return vals;
}

OTHER TIPS

The best general method I'm aware of for doing this isn't so much a tool as a convention: defining lists of bitflags like this:

FLAG_1                    0x00000001
FLAG_2                    0x00000002
FLAG_3                    0x00000004
FLAG_4                    0x00000008
FLAG_5                    0x00000010
FLAG_6                    0x00000020

It's easy to work with because the numbers continue on that 1, 2, 4, 8 pattern moving left.

EDIT: Responding to comment. Well, if you really want a combination of bitflags with exclusive enumerations, what you basically have to do is segment out portions of the bit list to be treated as a numeric space. So you can take the two bits 0x1 and 0x2 and now you can represent 0-3 using those two bits. Something like:

OPT_1_VAL_1               0x00000000
OPT_1_VAL_2               0x00000001
OPT_1_VAL_3               0x00000002
OPT_1_VAL_4               0x00000003
FLAG_1                    0x00000004
FLAG_2                    0x00000008
FLAG_3                    0x00000010
FLAG_4                    0x00000020

The masking logic you use then has to be more complex. For looking up the flags, you can do if(settings & FLAG_1), but for the option spaces you have to do if((settings & OPT_1_VAL_3) == OPT_1_VAL_3).

I don't know of a tool, but here's a trick to make unique-bit enums marginally easier to produce:

public enum Critters
{
   Amorphous = 0,
   Sloth =     1 << 0,
   Armadillo = 1 << 1,
   Weasel =    1 << 2,
   Crab =      1 << 3,
   Partridge = 1 << 4,
   Parakeet =  1 << 5,
   Rhino =     1 << 6
};

... need to pick a set of enum values so that they can be combined ...

Do you really need to pick them manually? Java, for instance, has EnumSet which does the dirty work for you and presents you with a Set interface for manipulating these flags.

Use powers of two so that each flag corresponds to a single bit position.

You can use standard enums (in C#) for that purpose. To accomplish this, you need to set the FlagsAttribute, and then specifically number the values. The code would look something like this:

[Flags]
public enum AvailableColours {
    black = 1,
    red = 2,
    green = 4,
    blue = 8,
    white = 16,
}

And then, the standard bitwise operators will work as expected.

[Edit] Um, OK, you want to generate possible combinations, right? Your requirements are very specific, so I would be very surprised if there were any tool that came close to what you want. I think you're going to have to roll your own. I'm assuming you want these as strings, correct? Here is some utility code to at least get you started:

public const int BITS_IN_BYTE = 8;
public const int BYTES_IN_INT = sizeof(int);
public const int BITS_IN_INT = BYTES_IN_INT * BITS_IN_BYTE;

/// <summary>
/// Display the bits in an integer
/// </summary>
/// <param name="intToDisplay">The integer to display</param>
/// <returns>A string representation of the bits</returns>
public string IntToBitString(int intToDisplay) {
    StringBuilder sb = new StringBuilder();
    AppendBitString(intToDisplay, sb);
    return sb.ToString();
}

/// <summary>
/// Displays the bits in an integer array
/// </summary>
/// <param name="intsToDisplay">Arrau to display</param>
/// <returns>String representation of the bits</returns>
public string IntArrayToBitString(int[] intsToDisplay) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < intsToDisplay.Length -1; i++) {
        AppendBitString(intsToDisplay[i], sb);
        sb.Append(' ');
    }
    if (intsToDisplay.Length - 1 > 0)
        AppendBitString(intsToDisplay[intsToDisplay.Length - 1], sb);
    return sb.ToString();
}

private void AppendBitString(int intToAppend, StringBuilder sb) {
    for (int j = BITS_IN_INT - 1; j >= 0; j--) {
        sb.Append((intToAppend >> j) & 1);
        if (j % 4 == 0 && j > 1)
            sb.Append(' ');
    }
}

/// <summary>
/// Creates an integer from a bit string. This method can be used
/// to explicitly set bits in an integer during testing.
/// </summary>
/// <example>
/// int i = bitUtil.IntFromBitString("0000 0000 0000 0100");
/// </example>
/// <param name="bitString">String representing the individual bits</param>
/// <returns></returns>
public int IntFromBitString(String bitString) {
    int returnInt = 0;
    int currentBitPos = bitString.Length;
    for (int i = bitString.Length - 1; i >= 0; i--) {
        char c = bitString[i];
        if (Char.IsWhiteSpace(c)) continue;

        if (c == '1') {
            returnInt |= 1 << (bitString.Length - currentBitPos);
        }
        currentBitPos--;
    }
    return returnInt;
}

/// <summary>
/// Tests the status of an individual bit in and integer. It is 0 based starting from the most
/// significant bit. 
/// </summary>
/// <param name="bits">The integer to test</param>
/// <param name="pos">The position we're interested in</param>
/// <returns>True if the bit is set, false otherwise</returns>
public bool IsBitOn(int bits, int pos) {
    int shiftAmnt = (BITS_IN_INT - 1) - pos;
    return ((bits >> shiftAmnt) & 1) == 1;
}

/// <summary>
/// Calculates the number of integers (as in an array of ints) required to
/// store a given number of bits
/// </summary>
/// <param name="bitsNeeded">The total count of required bits</param>
/// <returns>The number of integers required to represent a given bit count</returns>
public int RequiredSizeOfIntArray(int bitsNeeded) {
    return (bitsNeeded / BITS_IN_INT) + (((bitsNeeded % BITS_IN_INT) == 0) ? 0 : 1);
}

/// <summary>
/// Calculates which array element would hold the individual bit for a given bit position
/// </summary>
/// <param name="bitPos">The position of the interesting bit</param>
/// <returns>An index into an array of integers</returns>
public int ArrayPositionForBit(int bitPos) {
    return bitPos / BITS_IN_INT;
}

/// <summary>
/// Sets an individual bit to a given value
/// </summary>
/// <param name="bits">The integer containing the bits</param>
/// <param name="pos">The position in the integer to set</param>
/// <param name="isSet">True for on, False for off</param>
public void SetBit(ref int bits, int pos, bool isSet) {
    int posToSet = (BITS_IN_INT - 1) - pos;
    if (isSet)
        bits |= 1 << posToSet;
    else
        bits &= ~(1 << posToSet);
}

/// <summary>
/// Converts an array of integers into a comma seperated list
/// of hexidecimal values.
/// </summary>
/// <param name="bits">The array of integers</param>
/// <returns>String format</returns>
public String IntArrayToHexString(int[] bits) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < bits.Length - 1; i++) {
        sb.Append(bits[i].ToString("X"));
        sb.Append(',');
    }
    if (bits.Length > 0) {
        sb.Append(bits[bits.Length - 1].ToString("X"));
    }
    return sb.ToString();
}

/// <summary>
/// Parses a comma seperated list of hexidecimal values and
/// returns an array of integers for those values
/// </summary>
/// <param name="hexString">Comma seperated hex values</param>
/// <returns>integer array</returns>
public int[] HexStringToIntArray(String hexString) {
    string[] hexVals = hexString.Split(new char[] {','});
    int[] retInts = new int[hexVals.Length];
    for (int i = 0; i < hexVals.Length; i++) {
        retInts[i] = Int32.Parse(hexVals[i], System.Globalization.NumberStyles.HexNumber);
    }
    return retInts;
}

Are you sure you need to use bit fields?

In my experience, a class with a set of boolean data members is almost always the best choice.

The only argument I've ever heard for using bit fields instead of larger booleans (which are often a byte) is that it's supposedly faster. As with all optimizations, doing it without measuring performance is a bad idea.

Once it's encapsulated in a class, if you decide to change representation for optimization, you can do it without hitting a lot of other code.

Licensed under: CC-BY-SA with attribution

Not affiliated with StackOverflow