Есть ли практическое ограничение на размер битовых масок?

Question

Существует распространенный способ хранения нескольких значений в одной переменной с помощью битовой маски. Например, если у пользователя есть права на чтение, запись и выполнение для элемента, который можно преобразовать в одно число, сказав read = 4 (2^2), write = 2 (2^1), execute = 1 (2^0), а затем сложить их вместе, чтобы получить 7.

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

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

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

Answer 1

Вдобавок к моей голове, я бы написал функцию set_bit и get_bit, которая могла бы принимать массив байтов и битовое смещение в массиве, и использовать некоторую комбинацию битов для установки / получения соответствующего бит в массиве. Примерно так (в Си, но, надеюсь, вы поняли):

// sets the n-th bit in |bytes|. num_bytes is the number of bytes in the array
// result is 0 on success, non-zero on failure (offset out-of-bounds)
int set_bit(char* bytes, unsigned long num_bytes, unsigned long offset)
{
  // make sure offset is valid
  if(offset < 0 || offset > (num_bytes<<3)-1) { return -1; }

  //set the right bit
  bytes[offset >> 3] |= (1 << (offset & 0x7));

  return 0; //success 
}

//gets the n-th bit in |bytes|. num_bytes is the number of bytes in the array
// returns (-1) on error, 0 if bit is "off", positive number if "on"
int get_bit(char* bytes, unsigned long num_bytes, unsigned long offset)
{
  // make sure offset is valid
  if(offset < 0 || offset > (num_bytes<<3)-1) { return -1; }

  //get the right bit
  return (bytes[offset >> 3] & (1 << (offset & 0x7));
}

Answer 2

Я использовал битовые маски в коде файловой системы, где битовая маска во много раз больше машинного слова. думайте об этом как о «массиве логических значений»;

(журналирование масок во флеш-памяти, если хотите знать)

многие компиляторы знают, как это сделать для вас . Добавьте немного OO-кода, чтобы иметь типы, которые работают разумно, и тогда ваш код начинает выглядеть как его намерение, а не как какой-то битовый удар.

Мои 2 цента.

Answer 3

Старый поток, но стоит упомянуть, что есть случаи, когда требуются раздутые битовые маски, например, молекулярные отпечатки пальцев, которые часто создаются в виде 1024-битных массивов, которые мы упаковали в 32 поля bigint (SQL Server не поддерживает UInt32). Побитовые операции работают нормально - пока ваша таблица не начнет расти, и вы не поймете медлительность отдельных вызовов функций. Тип двоичных данных сработал бы, если бы не запрет T-SQL на побитовые операторы, имеющие два двоичных операнда.

Answer 4

Некоторые языки (я думаю, что Perl делает, не уверен) разрешают побитовую арифметику для строк. Давать вам гораздо больший эффективный диапазон. ((стр. * 8-битные символы) комбинации)

Однако я бы не использовал одно значение для наложения более одного / типа / данных. Основной триплет r / w / x из 3-битных целых, вероятно, будет верхним «практическим» пределом не по соображениям эффективности использования пространства, а по причинам практического развития.

(Php использует эту систему для управления своими сообщениями об ошибках, и я уже обнаружил, что это немного чрезмерно, когда вам нужно определить значения, где константы php не являются резидентными, и вы должны сгенерировать целое число вручную и, честно говоря, если бы chmod не поддерживал синтаксис стиля 'ugo + rwx', я бы никогда не захотел его использовать, потому что я никогда не смогу запомнить магические числа)

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

Answer 5

С 64-разрядным целым числом вы можете хранить значения до 2 ^ 64-1, 64 только 2 ^ 6. Так что да, есть предел, но если вам нужно более 64 флагов, мне было бы очень интересно узнать, что они все делают:)

Сколько штатов вам нужно подумать? Если у вас есть 64 потенциальных состояния, число комбинаций, в которых они могут существовать, равно полному размеру 64-разрядного целого числа.

Если вам нужно беспокоиться о 128 флагах, тогда пары битовых векторов будет достаточно (2 ^ 64 * 2).

Добавление : в Программировании Жемчуга существует расширенное обсуждение использования массива битов длиной 10 ^ 7, реализованного в целых числах (для хранения используемых 800 чисел) - это очень быстро и очень подходит для задача, описанная в этой главе.

Answer 6

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

Редактировать: Ваш комментарий говорит, что вы используете MySQL. В документации для MySQL 5.0 Numeric Types указано, что максимальный размер NUMERIC составляет 64 или 65 цифр. Это 212 бит для 64 цифр.

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

Answer 7

Например, .NET использует массив целых чисел в качестве внутреннего хранилища для своего класса BitArray. Практически другого пути нет.

Как говорится, в SQL вам потребуется более одного столбца (или использовать BLOBS) для хранения всех состояний.