Битовая векторная реализация набора в Programming Pearls, 2nd Edition

Ответ 1

Ключом к пониманию того, что происходит, является распознавание того, что BITSPERWORD= 2 ^SHIFT. Таким образом, x[i>>SHIFT] находит, что 32-разрядный элемент массива x имеет бит, соответствующий i. (Перемещая i 5 бит вправо, вы просто делите на 32.) После того, как вы нашли правильный элемент x, нижние 5 бит i могут затем использоваться, чтобы найти какой конкретный бит x[i>>SHIFT] соответствует i. То, что делает i & MASK; сдвигая 1 на это число бит, вы переместите бит, соответствующий 1, в точную позицию в x[i>>SHIFT], которая соответствует бит i ^th в x.

Вот несколько пояснений:

Представьте, что мы хотим, чтобы бит для N битов в нашем битовом векторе. Поскольку каждый int содержит 32 бита, нам понадобятся значения (N + 31) / 32 int для нашего хранилища (то есть N/32 округлены). В пределах каждого значения int мы примем соглашение о том, что биты упорядочены от наименее значимых до наиболее значимых. Мы также примем соглашение о том, что первые 32 бита нашего вектора находятся в x[0], следующие 32 бита находятся в x[1] и т.д. Здесь используется макет памяти (показывающий индекс бит в нашем битовом векторе, соответствующем каждому бит памяти):

      +----+----+-------+----+----+----+
x[0]: | 31 | 30 | . . . | 02 | 01 | 00 |
      +----+----+-------+----+----+----+
x[1]: | 63 | 62 | . . . | 34 | 33 | 32 |
      +----+----+-------+----+----+----+
        etc.

Наш первый шаг - выделить необходимый объем памяти:

x = new int[(N + BITSPERWORD - 1) >> SHIFT]

(Мы могли бы предусмотреть динамическое расширение этого хранилища, но это просто добавило бы сложности в объяснение.)

Теперь предположим, что мы хотим получить доступ к биту i (либо установить его, очистить, либо просто узнать его текущее значение). Нам нужно сначала выяснить, какой элемент x использовать. Так как 32 бит на int, это легко:

subscript for x = i / 32

Используя константы перечисления, элемент x, который мы хотим:

x[i >> SHIFT]

(Подумайте об этом как о 32-битном окне в нашем N-битовом векторе.) Теперь нам нужно найти конкретный бит, соответствующий i. Глядя на макет памяти, нетрудно понять, что первый (самый правый) бит в окне соответствует битовому индексу 32 * (i >> SHIFT). (Окно начинается после i >> SHIFT слотов в x, и каждый слот имеет 32 бита.) Так как первый бит в окне (позиция 0), то бит, который нам интересен, находится в позиции

i - (32 * (i >> SHIFT))

в окнах. Немного экспериментируя, вы можете убедить себя, что это выражение всегда равно i % 32 (фактически, это одно определение оператора mod), которое, в свою очередь, всегда равно i & MASK. Поскольку это последнее выражение - самый быстрый способ рассчитать то, что мы хотим, то, что мы будем использовать.

Отсюда остальное довольно просто. Мы начинаем с одного бита в наименее значимой позиции окна (т.е. Константы 1) и перемещаем его влево на i & MASK биты, чтобы получить его в положение в окне, соответствующее бит i в битовом векторе. Здесь выражение

1 << (i & MASK)

. Когда бит теперь перемещен туда, где мы хотим, мы можем использовать его как маску для установки, очистки или запроса значения бит в этой позиции в x[i>>SHIFT], и мы знаем, что мы на самом деле устанавливаем, очищаем или запрашивая значение бит i в нашем битовом векторе.

Ответ 2

Поля бит и вы

Я опишу простой пример, чтобы объяснить основы. Скажем, у вас есть целое число без знака с четырьмя битами:

[0][0][0][0] = 0

Вы можете представить любое число здесь от 0 до 15, преобразуя его в базу 2. Скажем, у нас есть правый конец, наименьший:

[0][1][0][1] = 5

Итак, первый бит добавляет 1 к сумме, второй добавляет 2, третий добавляет 4, а четвертый добавляет 8. Например, здесь 8:

[1][0][0][0] = 8

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

[0][0][0][1] = 1 = ON
[0][0][0][0] = 0 = OFF //what a huge waste of space!

(Конечно, проблема более выражена в реальной жизни, поскольку 32-битные целые числа выглядят следующим образом:

[0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0] = 0

Ответ на этот вопрос - использование битового поля. У нас есть набор свойств (обычно связанных), которые мы будем включать и выключать с помощью бит-операций. Итак, скажем, у вас может быть 4 разных индикатора на аппаратном обеспечении, в котором вы хотите включить или выключить.

 3  2  1  0
[0][0][0][0] = 0

(Почему мы начинаем с света 0? Я объясню это через секунду.) Обратите внимание, что это целое число и хранится как целое число, но используется для представления нескольких состояний для нескольких объектов. Псих! Скажем, мы включаем свет 2 и 1 на:

 3  2  1  0
[0][1][1][0] = 6

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

 3  2  1  0
[1][1][1][0] = 0xE \\what?

Зачем нам это нужно? У нас есть ровно одно состояние для каждого номера от 0 до 15? Как мы будем управлять этим без каких-либо безумных серий операторов switch? Тьфу...

Свет в конце

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

1 * (2 ³) + 1 * (2 ²) + 1 * (2 ¹) +0 * (2 ⁰) = 0xE

Таким образом, каждый свет присутствует в показателе каждого члена уравнения. Если свет горит, рядом с его словом есть 1, если свет выключен, появляется нуль. Потратьте время, чтобы убедить себя, что существует только одно целое число от 0 до 15, которое соответствует каждому состоянию в этой схеме нумерации.

Операторы бит

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

[0][0][0][1] = 1

Когда вы смещаете биты влево или вправо в целое число, оно буквально перемещает биты влево и вправо. (Примечание: я 100% отрицаю это объяснение для отрицательных чисел! Там будут драконы!)

1<<2 = 4
[0][1][0][0] = 4
4>>1 = 2
[0][0][1][0] = 2

При смене числа, представленного более чем одним битом, вы столкнетесь с аналогичным поведением. Кроме того, нетрудно убедить себя, что x → 0 или x < 0 только x. Ничего не сдвигается.

Это, вероятно, объясняет схему именования операторов Shift всем, кто не знаком с ними.

Побитовые операции

Это представление чисел в двоичном формате также может использоваться для пролить свет на операции побитовых операторов на целые числа. Каждый бит в первом номере является xor-ed, и-ed, или or-ed с его другим номером. Возьмите секунду, чтобы отправиться в википедию и познакомиться с функцией этих булевых операторов - я объясню, как они работают на числах, но я не хочу подробно перерисовывать общую идею.

...

Добро пожаловать! Начнем с изучения влияния OR (|) на два целых числа, сохраненных в четырех бит.

 OR OPERATOR ON:
 [1][0][0][1] = 0x9
 [1][1][0][0] = 0xC
________________
 [1][1][0][1] = 0xD

Tough! Это близкий аналог таблицы истинности для логического оператора OR. Обратите внимание, что каждый столбец игнорирует соседние столбцы и просто заполняет столбец результатов с результатом первого бита, а второй бит OR'd вместе. Заметьте также, что значение чего-либо или'd с 1 равно 1 в этом конкретном столбце. Все, что или ноль, остается неизменным.

Таблица для AND (&) интересна, хотя и несколько инвертирована:

 AND OPERATOR ON:
 [1][0][0][1] = 0x9
 [1][1][0][0] = 0xC
________________
 [1][0][0][0] = 0x8

В этом случае мы делаем то же самое - мы выполняем операцию И с каждым битом в столбце и помещаем результат в этот бит. Никакая колонка не заботится о какой-либо другой колонке.

Важный урок об этом, который я предлагаю вам проверить, используя приведенную выше диаграмму: все AND-ed с нулем равно нулю. Кроме того, не менее важно - ничего не происходит с числами, которые AND-ed с одним. Они остаются неизменными.

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

 XOR OPERATOR ON:
 [1][0][0][1] = 0x9
 [1][1][0][0] = 0xC
________________
 [0][1][0][1] = 0x5

Каждый бит имеет XOR'd со своим столбцом, yadda yadda и т.д. Но внимательно посмотрите на первую строку и вторую строку. Какие биты изменились? (Половина из них.) Какие биты остались прежними? (Нет точек для ответа на этот вопрос.)

Бит в первой строке изменяется в результате, если (и только если) бит во второй строке равен 1!

Пример одной лампочки!

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

 0
[?] \\We don't know if it one or zero while coding

Мы знаем, что у нас есть операция, которая всегда может сделать этот бит равным одному - оператору OR 1.

0|1 = 1
1|1 = 1

Итак, игнорируя остальные луковицы, мы могли бы сделать это

4_bit_lightbulb_integer | = 1;

и точно знать, что мы ничего не сделали, но установили первую лампочку в положение ON.

 3  2  1  0
[0][0][0][?] = 0 or 1? \\4_bit_lightbulb_integer
[0][0][0][1] = 1
________________
[0][0][0][1] = 0x1

Аналогично, мы можем И число с нулем. Ну, не совсем нул - мы не хотим влиять на состояние других бит, поэтому мы будем заполнять их теми, что есть.

Я использую унарный (один аргумент) оператор для отрицания бит. Побитовый оператор ~ (NOT) сбрасывает все биты в свой аргумент. ~ (0x1):

[0][0][0][1] = 0x1
________________
[1][1][1][0] = 0xE

Мы будем использовать это в сочетании с битом И ниже.

Давайте сделаем 4_bit_lightbulb_integer и 0xE

 3  2  1  0
[0][1][0][?] = 4 or 5? \\4_bit_lightbulb_integer
[1][1][1][0] = 0xE
________________
[0][1][0][0] = 0x4

Мы видим много целых чисел с правой стороны, которые не имеют непосредственной актуальности. Вы должны привыкнуть к этому, если имеете дело с бит-полями. Посмотрите на левую сторону. Бит справа всегда равен нулю, а остальные биты остаются неизменными. Мы можем отключить свет 0 и игнорировать все остальное!

Наконец, вы можете использовать бит XOR для выборочного переключения первого бита!

 3  2  1  0
[0][1][0][?] = 4 or 5? \\4_bit_lightbulb_integer
[0][0][0][1] = 0x1
________________
[0][1][0][*] = 4 or 5?

На самом деле мы не знаем, что такое значение *, только что перевернувшееся от чего? был.

Объединение операций сдвига бит и побитовых операций

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

[0][0][0][1] = 1 = 1<<0
[0][0][1][0] = 2 = 1<<1
[0][1][0][0] = 4 = 1<<2
[1][0][0][0] = 8 = 1<<3

Хм. Интересно. Я упомянул оператор отрицания здесь (~), так как он аналогичным образом использовал необходимые значения бит для файла ANDing в полях бит.

[1][1][1][0] = 0xE = ~(1<<0)
[1][1][0][1] = 0xD = ~(1<<1)
[1][0][1][1] = 0xB = ~(1<<2)
[0][1][1][1] = 0X7 = ~(1<<3)

Вы видите интересную взаимосвязь между значением сдвига и соответствующей позицией световой лампы сдвинутого бита?

Канонические операторы бит-сдвига

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

Чтобы включить лампу, мы создаем 1 в правильном положении с использованием сдвига битов, а затем OR с текущими положениями лампочки. Скажем, мы хотим включить свет 3 и игнорировать все остальное. Нам нужно выполнить операцию смещения, которая ORs

 3  2  1  0
[?][?][?][?]  \\all we know about these values at compile time is where they are!

и 0x8

[1][0][0][0] = 0x8

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

1<<3 = 0x8

а затем:

4_bit_lightbulb_integer |= 0x8;

 3  2  1  0
[1][?][?][?]  \\the ? marks have not changed!

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

Сброс бит работает аналогично - мы будем использовать таблицу с отмененными битами выше, например, чтобы очистить свет 2.

~(1<<2) = 0xB = [1][0][1][1]

4_bit_lightbulb_integer и 0xB:

 3  2  1  0
[?][?][?][?] 
[1][0][1][1]
____________
[?][0][?][?]

Метод прерывания бит XOR - это та же идея, что и OR.

Таким образом, канонические методы переключения бит:

Включите свет i:

4_bit_lightbulb_integer|=(1<<i)

Отключить свет i:

4_bit_lightbulb_integer&=~(1<<i)

Отразить свет i:

4_bit_lightbulb_integer^=(1<<i)

Подождите, как я могу их прочитать?

Чтобы проверить бит, мы можем просто обнулить все биты, кроме той, о которой мы заботимся. Затем мы проверим, будет ли результирующее значение больше нуля, так как это единственное значение, которое может быть отличным от нуля, оно сделает целое число отличным от нуля тогда и только тогда, когда оно отличное от нуля. Например, чтобы проверить бит 2:

1 < < 2:

[0][1][0][0]

4_bit_lightbulb_integer:

[?][?][?][?]

1 < 2 и 4_bit_lightbulb_integer:

[0][?][0][0]

Помните из предыдущих примеров, что значение? не изменился. Помните также, что все ИО 0 равно 0. Таким образом, мы можем с уверенностью сказать, что если это значение больше нуля, переключатель в положении 2 является истинным, а лампочка равна нулю. Аналогично, если значение выключено, значение всей вещи будет равно нулю.

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

Итак, каноническая функция проверки:

Проверьте, включен ли бит i:

if (4_bit_lightbulb_integer & 1<<i) {
\\do whatever

}

Особенности

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

void set(int i)  {        x[i>>SHIFT] |=  (1<<(i & MASK)); }

Из канонической реализации я собираюсь предположить, что это пытается установить некоторые бит в 1! Пусть возьмем целое число и посмотрим, что происходит здесь, если я подставляю значение 0x32 (50 в десятичном значении) в i:

x[0x32>>5] |= (1<<(0x32 & 0x1f))

Ну, это беспорядок.. пусть разрешит эту операцию справа. Для удобства сделайте вид, что существует еще 24 ненужных нулей, так как они являются 32-битными целыми числами.

...[0][0][0][1][1][1][1][1] = 0x1F
...[0][0][1][1][0][0][1][0] = 0x32
________________________
...[0][0][0][1][0][0][1][0] = 0x12

Похоже, что все обрезается на границе сверху, где 1s превращаются в нули. Этот метод называется Bit Masking. Интересно, что граница здесь ограничивает результирующие значения от 0 до 31... Именно это число битных позиций у нас для 32-битного целого!

x [0x32 → 5] | = (1 < (0x12)) Давайте посмотрим на другую половину.

...[0][0][1][1][0][0][1][0] = 0x32

Сдвиньте пять бит вправо:

...[0][0][0][0][0][0][0][1] = 0x01

Обратите внимание, что это преобразование точно уничтожило всю информацию из первой части функции - мы имеем 32-5 = 27 оставшихся битов, которые могут быть отличными от нуля. Это указывает, какие из 2 ²⁷ целых чисел в массиве целых чисел выбраны. Итак, теперь упрощенное уравнение:

x[1] |= (1<<0x12)

Это похоже на каноническую операцию настройки бит! Мы только что выбрали

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

Ответ 3

Если вы храните свои биты в массиве слов n, вы можете представить, что их можно выложить как матрицу с n строками и 32 столбцами (BITSPERWORD):

         3                                         0
         1                                         0
      0  xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx
      1  xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx
      2  xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx     
      ....
      n  xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx

Чтобы получить k-й бит, вы разделите k на 32. Результат (целочисленный) даст вам строку (слово), в которой находится бит, напоминание даст вам, какой бит находится внутри слова.

Разделение на 2^p можно сделать, просто сдвинув p положения справа. Напоминание можно получить, получив р самых правых бит (то есть побитовое И с (2 ^ р - 1)).

В терминах C:

#define div32(k) ((k) >> 5)
#define mod32(k) ((k) & 31)

#define word_the_bit_is_in(k) div32(k)
#define bit_within_word(k)    mod32(k)

Надеюсь, что это поможет.