Как проверить корретность битовой маски?

Question

[Антон Шаманов]

Пример:
Eсть "флаги": a = 1, b = 2, c = 6
Значение должно является битовой маской содержащей от 1 до 3 флагов:
a, b, c
a | b, a | c, b | c
a | b | c

Как проверить значение? например, 7 - верно (a | c), а 4 или 11 - не верно.

Answer 1

[Rsa97]

У вас не битовая маска, так как b и c содержат один и тот же бит 2 и отличить c от b|c невозможно. 2|6 === 6. В битовой маске все уникальные некомбинированные флаги должны быть степенями двойки.
Работать с вашим набором можно, но флаги придётся складывать через +, а проверять своей функцией, наподобие такой:

function flags($value) {
    if (!in_array($value, [0, 1, 2, 3, 6, 7, 8, 9])) {
        return false;
    }
    $result = [];
    if (in_array($value, [1, 3, 7, 9])) {
        $result[] = 'a';
    }
    if (in_array($value, [2, 3, 8, 9])) {
        $result[] = 'b';
    }
    if (in_array($value, [6, 7, 8, 9])) {
        $result[] = 'c';
    }
    return $result;
}

Comments

[Антон Шаманов]

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

отличить c от b|c невозможно

смысл в том что, каждая вариация флагов дает уникальную сумму по которой можно проверить как наличие флага, так и валидность суммы флагов.
что-то вроде:

/**
  * @param int[] $flags ['a' => 1, 'b' => 2, 'c' => 6]
  * @param int $flagSum верные суммы: 7(a+c), 3(a+b), 2(b), не верные: 0, 4, 5
  */
function validate(array $flags, int $flagSum): bool
{
       $flagSums = [1, 2, 6, ..., 9]; // все возможные суммы флагов которые надо как-то получить
       return in_array($flagSum, $flagSums);
}

[Rsa97]

Антон Шаманов, Собственно, вы можете называть свою систему как угодно. Я лишь говорю о том, что это не битовые флаги.
С битовыми всё просто.

const FLAG_A = 1;
const FLAG_B = 2;
const FLAG_C = 4;

if (($value & FLAG_A) === FLAG_A) {
    print "Flag A\n";
}

А в вашем случае надо вычислять все возможные суммы, хранить их, как-то вычислять, входит ли конкретное значение в конкретную сумму и т.д., и т.п., и пр.
Это несложно для двух-трёх флагов, но когда их будет 20, то вы получите 2²⁰ возможных комбинаций.

[Антон Шаманов]

Rsa97, ты проверяешь наличие отдельного флага в маске, а как проверить маску на основании имеющихся флагов?

[Антон Шаманов]

А в вашем случае надо вычислять все возможные суммы

вопрос как раз и состоит в том как их вычислить

[Rsa97]

Антон Шаманов, Для правильной системы битовых флагов любая маска корректна. Неиспользуемые биты просто игнорируются.

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

[Антон Шаманов]

Rsa97,

Для правильной системы битовых флагов любая маска корректна. Неиспользуемые биты просто игнорируются.

ок, допустим у нас есть флаги дающие корректную битовую маску: a =2, b=4, c=8 как проверить на основании этих флагов корретна ли маска? 6(да - a|b), 5(нет)

[Rsa97]

Антон Шаманов, А вычислить их легко. Это обычная комбинаторная задача. Она медленная, но несложная.
Можно рекурсивно, можно итеративно.

function allCombinations(array $values) : array
{
    $current = array_pop($values);
    if (count($values) === 0) {
        return [0, $current];
    }
    $subArray = allCombinations($value);
    return array_merge(
        $subArray, 
        array_map(
            function ($el) use ($current) { return $el + $current; },
            $subArray
        )
    );
}
print_r(allCombinations([1, 2, 6]));
/*
Array {
  [0] => 0
  [1] => 1
  [2] => 2
  [3] => 3
  [4] => 6
  [5] => 7
  [6] => 8
  [7] => 9
}

[Rsa97]

Антон Шаманов, А в битовой маске все значения верные. Если флаг (бит) не используется, то он вообще игнорируется. Так что маска 5 - вполне себе верная. Просто неиспользуемый бит 1 имеет значение 1, а в маске 6 этот же неиспользуемый бит имеет значение 0.
Иногда бывает требование, что неиспользуемые биты должны иметь определённое значение, но тогда это легко проверить, ($value & ~(FLAG_A | FLAG_B | FLAG_C)) === 0

[Антон Шаманов]

Так что маска 5 - вполне себе верная

ни одна комбинация флагов a =2, b=4, c=8 не даст 5

[Rsa97]

Антон Шаманов, И что? Игнорируйте этот бит. Маска 5 и маска 4 - это одна и та же маска, поскольку бит 1 не используется.

[Антон Шаманов]

Rsa97, я тебя понимаю, но в десятичной форме оно не так ясно представляется т.ч. туплю

Answer 2

[dollar]

Корректность битовой маски обычно не проверяется, потому что обычно нет нормальных критериев. По сути каждый флаг - это степень двойки (или отдельный "бит"). Таким образом, правильная маска - это просто число от 0 до максимально возможного, когда все флаги включены. В этом диапазоне обычно нет дырок. Для понятности попробуйте записывать маску в двоичном формате.

Предположим, у вас есть пять "флагов": a=1, b=2, c=4, d=8, e=16,
тогда значение маски будет от 0 до 31 (т.е. макс. 11111). По выходу за диапазон можно сказать, что она некорректна. Но если у вас 32 флага в маске типа uint, то выход за диапазон не возможен в принципе, и любая маска будет корректной.

Предположим, у вас теперь 4 флага: a=1, b=2, d=8, e=16,
то есть не хватает c=4. Тогда это как бы дырка в маске.
Проверяем этот бит: (mask & 4 == 4)
По идее, если этот бит установлен, то маска некорректна. Но с другой стороны, целевой алгоритм может просто игнорировать бит, который не используется. Так что лишние биты не делают маску некорректной.

Ну и, наконец, возможен уже реальный критерий, когда логика флагов такова, что не все комбинации возможны. Хотя такие кейсы лучше вообще не флагами решать, тем не менее бывает. Например, запрещено устанавливать одновременно b=2 и e=16, тогда условие некорректности будет следующее:
(mask & 2 > 0) && (mask & 16 > 0)
Либо короче:
(mask & (b | e) > 0)
(mask & 18 > 0)

Аналогично проверяется любое другое условие, накладываемое на маску. Например, если количество включённых флагов лимитировано, то просто считаем количество бит в маске.

P.S. И да, c=6 это некорректный флаг, потому что содержит b=2, и вы никак не определите, является ли mask=c или же mask=b|c.

Comments

[Антон Шаманов]

Извиняюсь, я не совсем корректно выразился, просто не знаю как назвать сумму флагов.
Смысл в том, что каждая вариация флагов дает уникальную сумму по которой можно проверить как наличие флага, так и валидность суммы флагов.
что-то вроде:

/**
  * @param int[] $flags ['a' => 1, 'b' => 2, 'c' => 6]
  * @param int $flagSum верные суммы: 7(a+c), 3(a+b), 2(b), не верные: 0, 4, 5
  */
function validate(array $flags, int $flagSum): bool
{
       $flagSums = [1, 2, 6, ..., 9]; // все возможные суммы флагов которые надо как-то получить
       return in_array($flagSum, $flagSums);
}

[Антон Шаманов]

Предположим, у вас есть пять "флагов": a=1, b=2, c=4, d=8, e=16,
тогда значение маски будет от 0 до 31 (т.е. макс. 11111).

по поводу того что значение в диапазоне это понятно, но проблема в том что не все входящие в него значения являются верной суммой флагов, например, 5, 7 и т.д.

[dollar]

Антон Шаманов,
5 - это 101 (в двоичной системе), то есть 1+4, то есть (a|c)
7 - это 111, то есть 1+2+4, то есть (a|b|c)
Любое число от 0 до 31 будет валидным набором флагов, если их всего пять и если нет каких-то специальных условий.

Таким специальным условием может быть, например, ограничение количества флагов. Например, максимум 2 флага. Тогда и правда 7 будет невалидной маской. Но тогда и функцию нужно делать соответственно критерию невалидности. Например, в примере выше нужно подсчитывать количество флагов (т.е. количество бит в маске).

Answer 3

[Василий Мельников]

Можно наложить по AND все инверсированные значения флагов и если будет не 0 то есть лишний "неверный" бит
На C

size_t value = // Откуда-то получили

bool isValid = (value & ~(MASK1 | MASK2 | MASK3)) == 0;

Comments

[Rsa97]

Накладываем.
1 + 2 + 6 = 9
9 & ~(1 | 2 | 6) = 8
По вашему алгоритму получили ошибку, но автор то использовал не битовые флаги, поэтому ваш алгоритм работает неверно.

[Василий Мельников]

Rsa97, Флаги так не накладывают. Поэтому и как раз получили ошибку. У нас установлен бит которого быть не может.
Поэтому алгоритм отработал верно