Как называется хранение / упаковка множества логических состояний в одно число?

55

Это своего рода простое сжатие, где вы используете одну числовую переменную для хранения множества логических / двоичных состояний, используя удвоение и тот факт, что каждое удваивающее число равно 1 + сумма всех предыдущих.

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

Например, вот очень простая реализация, предназначенная для иллюстрации концепции:

packStatesIntoNumber () {
  let num = 0
  if (this.stateA) num += 1
  if (this.stateB) num += 2
  if (this.stateC) num += 4
  if (this.stateD) num += 8
  if (this.stateE) num += 16
  if (this.stateF) num += 32
  return num
}

unpackStatesFromNumber (num) {
  assert(num < 64)
  this.stateF = num >= 32; if (this.stateF) num -= 32
  this.stateE = num >= 16; if (this.stateE) num -= 16
  this.stateD = num >= 8; if (this.stateD) num -= 8
  this.stateC = num >= 4; if (this.stateC) num -= 4
  this.stateB = num >= 2; if (this.stateB) num -= 2
  this.stateA = num >= 1; if (this.stateA) num -= 1
}

Вы также можете использовать побитовые операторы, разбор чисел с основанием 2, перечисления ... Есть много более эффективных способов реализовать это, меня интересует название подхода в более общем смысле.

user56reinstatemonica8
источник
8
В C # они есть enums, и они могут иметь Flagsатрибут. Они могут сделать ваш код намного проще.
Бернхард Хиллер
12
Я бы назвал это «имитацией битовых полей». Это почти всегда плохая идея, если космическая эффективность не является чрезвычайно важной.
Килиан Фот
7
@KilianFoth A boolобычно хранится как 32-битное целое число внутри. Таким образом, упаковка может иметь значение в 32 раза. Это действительно много. Я имею в виду, что мы, программисты, всегда готовы выбросить половину наших ресурсов, но я, как правило, не хочу выбрасывать 97% из них. Такие бесполезные факторы могут легко определить разницу между возможностью запуска важных сценариев использования и нехваткой памяти.
начальник
3
Исторически сложилось так, что типичные битовые маски используются для объявления, установки и получения значений. Использование сдвигов странно и не является лучшей иллюстрацией подхода.
JimmyJames
3
@cmaster Причина, по которой булы хранятся таким образом, заключается в том, что совместное использование одной области памяти (32 или 64 бита на современных компьютерах) может быть очень плохим для производительности кэша, если вы не уделяете много внимания коду машинного языка. Если у вас действительно огромное количество битов, это, вероятно, того стоит, но если нет, то, вероятно, лучше не предварительно оптимизировать и просто собрать биты, когда вы будете готовы к передаче в сеть или на диск.
Билл К

Ответы:

107

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

Многие языки программирования имеют вспомогательные структуры, чтобы помочь с этим. Как отмечает @BernhardHiller в комментариях, C # имеет перечисления с флагами ; У Java есть класс EnumSet .

Глорфиндел
источник
4
Я бы интерпретировал «битовое поле» как использование языковой функции, которая позволяет отдельным битам присваиваться полям структуры, а не делать это вручную с помощью побитовых операторов.
Питер Грин
22
@PeterGreen Это будет отличаться от стандартной интерпретации.
Эрик
1
«Битовое отображение» или «Битовое отображение», хотя и является общим для наборов записей и обработки массивов, также может применяться в этом случае. При извлечении общих элементов из нескольких наборов значение может быть разложено для идентификации компонентов федеративной модели. Мы даже говорим это о восьмеричных цифрах файлового режима. Битовые маски (любая маска), как правило, являются фильтрами (как для портов ввода-вывода и регистров направления данных).
Маккензм
1
C # также имеет BitArray, что позволяет хранить произвольное количество битов и индексировать их (в то время как флаги ограничены целочисленным типом и предназначены для использования в качестве масок).
Луаан
Правда; Я только что упомянул две структуры, с которыми я наиболее знаком. Там, наверное, десятки, особенно на других языках.
Глорфиндель
20

Странно, здесь довольно много разных терминов, но я не вижу того, что сразу пришло в голову (и это в названии вашего вопроса!) - Bit Packing - это то, что я всегда слышал, как его называли.

Я думал, что это действительно очевидно, но, как ни странно, когда я захожу в Google, это термин, который широко используется, но не определен официально (Википедия, кажется, перенаправляет на битовое поле, которое является способом упаковки битов, а не именем для процесс). Поиски определения, кажется, ведут к этой странице:

http://www.kinematicsoup.com/news/2016/9/6/data-compression-bit-packing-101

Это не очень хорошо для SO целей, но это лучшее определение / описание, которое я могу найти, включая это краткое описание: «Битовая упаковка - это простая концепция: используйте как можно меньше бит для хранения части данных».

Билл К
источник
Можете ли вы предоставить некоторые ссылки? Интересный термин.
Грег Бургхардт
13
Упаковка битов технически правильна, но также относится к более общей вещи, чем просто логические состояния - хранение данных в целом в наименьшем количестве битов, насколько это возможно. Например, другое его использование может означать сжатие charмассива путем помещения двух chars в один int.
Изката
@GregBurghardt Вы знаете, это интересно. Я не думал об этом, когда писал, потому что этот термин был настолько распространен в 80-х / 90-х годах, когда я изучал программирование на С и ассемблере - теперь, хотя поиск в Google находит МНОГИЕ упоминания, для него нет определенной страницы Википедии. , Первый ответ в Google имеет следующее определение: «Упаковка битов - это простая концепция: используйте как можно меньше бит для хранения фрагмента данных». kinematicsoup.com/news/2016/9/6/…
Билл К
вот тогда я и узнал о битовой упаковке, хотя вы можете стать намного безумнее, чем просто переназначить неиспользуемые 0 в номинально целочисленные значения. Несколько лет назад я столкнулся с системой, которая хранила один из своих параметров в виде 8-битного числа с плавающей запятой. IIRC 5 битов для неподписанной мантиссы (все значения были положительными, нет необходимости хранить знак явно) и еще 3 для базовой 10 степени. В то время, когда я предполагал, что это был устаревший аппаратный клудж без какого-либо пути вперед, но с тех пор, как машинное обучение недавно начало делать вещи с int4 vs int8, я мог видеть, как некоторые рабочие нагрузки снижаются с FP16.
Дэн Нили
1
@DanNeely Подобные вещи также обычно поддерживаются графическими процессорами - торговля между точностью, памятью и вычислениями там очень важна. Это очень хорошо использовалось и для вычислений на GPU.
Луаан
14

Есть много разных терминов, используемых для описания этого.

Чаще всего биты называются «битовыми флагами» или «битовыми полями».
(Тем не менее, стоит отметить, что «битовые поля» иногда ссылаются на специфическую особенность языков C и C ++, которая связана, но не совсем одинакова.)

Само целое число по-разному называется «битовым массивом», «битовым набором» или «битовым вектором», в зависимости от использования и обстоятельств.

В любом случае извлечение битов из набора битов / вектора / массива осуществляется посредством сдвига и маскирования.
(т.е. используя битовую маску .)


Для некоторых примеров каждого термина в активном использовании:

  • Статья Википедии на эту тему называется « Битовый массив» , в котором отмечается, что он «также известен как битовая карта, битовый набор, битовая строка или битовый вектор».
  • C ++ использует std::bitset
  • Java использует BitSet
  • C # использует BitArray
  • StackOverflow имеет теги bitvector, bitarrayиbitset
  • На PyPi есть bitarrayпроект и BitVectorпроект

Это не совсем относится к вопросу, но я хотел бы сказать: пожалуйста, не используйте сложение и вычитание для установки и очистки битов, так как эти методы подвержены ошибкам.
(т.е. если вы сделаете num += 1дважды, результат эквивалентен num += 2.)

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

packStatesIntoNumber ()
{
  let num = 0
  if (this.stateA) num |= 1
  if (this.stateB) num |= 2
  if (this.stateC) num |= 4
  if (this.stateD) num |= 8
  if (this.stateE) num |= 16
  if (this.stateF) num |= 32
  return num
}

unpackStatesFromNumber (num)
{
  this.stateF = ((num & 32) != 0);
  this.stateE = ((num & 16) != 0);
  this.stateD = ((num & 8) != 0);
  this.stateC = ((num & 4) != 0);
  this.stateB = ((num & 2) != 0);
  this.stateA = ((num & 1) != 0);
}
Pharap
источник
1
this.stateF = (num & 32) ? true : falseи т. д. Не нужно изменять numпри извлечении значений.
Роджер Липскомб
3
@RogerLipscombe Хороший вопрос, я на самом деле не читал, что делает код, а просто реагировал на использование +и -. Теперь я стал лучше и использовал != 0вместо троичного, который, как мне кажется, более лаконичен, хотя еще и является expclit.
Pharap