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

StackOverflow https://stackoverflow.com/questions/177054

  •  05-07-2019
  •  | 
  •  

Вопрос

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

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

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

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

Это было полезно?

Решение

Вдобавок ко всему, я бы написал функцию 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));
}

Другие советы

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

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

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

Мои 2 цента.

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

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

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

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

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

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

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

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

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

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

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

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

Изменить . В вашем комментарии сказано, что вы используете MySQL. В документации для числовых типов MySQL 5.0 говорится, что максимальный размер ЧИСЛА - 64 или 65 цифр. Это 212 бит для 64 цифр.

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top