Как выбрать значения битового флага?

Question

У меня есть набор опций, некоторые ортогональные (можно комбинировать в любой комбинации), некоторые эксклюзивные (допускается только одно из набора), и мне нужно выбрать набор enum значений, чтобы их можно было комбинировать по битам or и извлеченным по битам and. Я бы предпочел, чтобы or -ing-недопустимая комбинация была бы обнаружена.

Есть ли инструменты для генерации enums, как это?

Изменить для ясности

Я ищу что-то, что может использовать тот факт, что некоторые флаги недопустимы в комбинации, чтобы уменьшить количество используемых битов. Требование, чтобы я был в состоянии обнаружить ошибки, мягко. Я не должен быть в состоянии сказать, что было использовано, если что-то испортилось.

Я использую C #, но любое решение должно быть полезным.

Примером шаблона будет:

0011 00
0101 00
1001 00
0110 00
1010 00
1100 00

0000 01
0000 10

, который получает 6 эксклюзивных флагов и ортогональную пару 2 в 6 бит

быстрый тест показывает, что 5 битов дают 9 значений, 6 битов дают 20, ...

Answer 1

Лучший общий метод, который я знаю для этого, не столько инструмент, сколько соглашение: определение списков битовых флагов, например:

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

С ним легко работать, потому что цифры продолжаются на этом шаблоне 1, 2, 4, 8, двигаясь влево.

РЕДАКТИРОВАТЬ: Ответ на комментарий. Что ж, если вы действительно хотите комбинацию битовых флагов с исключительными перечислениями, то вам в основном нужно сегментировать части списка битов, которые будут обрабатываться как числовое пространство. Таким образом, вы можете взять два бита 0x1 и 0x2, и теперь вы можете представить 0-3, используя эти два бита. Что-то вроде:

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

Логика маскировки, которую вы используете, должна быть более сложной. Для просмотра флагов вы можете сделать if (settings & FLAG_1), но для опционных пространств вы должны сделать if ((settings & OPT_1_VAL_3) == OPT_1_VAL_3).

Answer 2

Чтобы представить " эксклюзивный " набор параметров n (т. Е. Должен быть выбран только один), нам требуется не менее ceil(log2(n)) битов. Например, опция k может быть представлена ​​числом k в базе- 2.

Для представления " ортогонального " набора параметров n (т. Е. Может быть выбрана любая комбинация размера 0, 1, ..., n), нам требуется не менее n битов. Например, параметры k0, k1, k2 могут быть представлены двоичным числом, биты которого равны нулю, за исключением битов 0, 1, 2.

Таким образом, чтобы представить несколько наборов опций одновременно, мы складываем количество битов, необходимое для каждого набора опций (в зависимости от того, является ли он "эксклюзивным" или "ортогональным"), чтобы получить общее количество требуемых битов.

Короче говоря, для выбора значений перечисления,

• «Эксклюзивный» параметр k использует k << r
• опция "ортогональный" k0, k1, ..., k{n-1} использует 0x1 << r, 0x1 << (r+1), ..., 0x1 << (r+n-1)

где смещение r - это количество битов, использованных предыдущими наборами опций.

---

Пример того, как автоматизировать эту конструкцию , на 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;
}

Answer 3

Я не знаю, какой инструмент, но вот трюк, чтобы немного облегчить создание уникальных битовых перечислений:

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
};

Answer 4

Используйте степени двойки, чтобы каждый флаг соответствовал одной позиции бита.

Answer 5

... нужно выбрать набор значений enum чтобы их можно было комбинировать ...

Вам действительно нужно выбрать их вручную? Java, например, имеет EnumSet, который делает грязную работу за вас и предоставляет вам интерфейс Set для управления этими флагами.

Answer 6

Вы уверены, что вам нужно использовать битовые поля?

По моему опыту, класс с набором логических членов-данных почти всегда является лучшим выбором.

Единственный аргумент, который я когда-либо слышал об использовании битовых полей вместо более крупных логических значений (которые часто являются байтами), заключается в том, что он предположительно быстрее. Как и во всех оптимизациях, делать это без измерения производительности - плохая идея.

Как только он будет инкапсулирован в классе, если вы решите изменить представление для оптимизации, вы можете сделать это, не затрагивая много другого кода.

Answer 7

Вы можете использовать стандартные перечисления (в C #) для этой цели. Для этого вам нужно установить FlagsAttribute , а затем конкретно пронумеровать значения. Код будет выглядеть примерно так:

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

И тогда стандартные побитовые операторы будут работать как положено.

[Изменить] Хм, хорошо, вы хотите создать возможные комбинации, верно? Ваши требования очень специфичны, поэтому я был бы очень удивлен, если бы был какой-либо инструмент, близкий к тому, что вы хотите. Я думаю, что вам придется кататься самостоятельно. Я предполагаю, что вы хотите это как строки, правильно? Вот некоторый код утилиты, по крайней мере, для начала:

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;
}