Блог

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

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

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

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

С моей точки зрения, я бы написал 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 amp; 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] amp; (1 << (offset amp; 0x7));
}
 

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

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

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

Мои 2 цента.

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

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

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

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

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

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

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

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

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

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

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

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

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

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