Объяснение алгоритма для установки, очистки и тестирования одного бита

VonC опубликовал хороший ответ о битмашках в целом. Вот некоторая информация, более конкретная для кода, который вы опубликовали.

Учитывая целое число, представляющее бит, мы определяем, какой член массива имеет этот бит. То есть: Биты с 0 по 31 живут в a[0] , бит 32-63 живут в a[1] и т. Д. Все, что делает i>>SHIFT , это i / 32 . Это работает, какой член бит живет. С оптимизирующим компилятором они, вероятно, эквивалентны.

Очевидно, теперь мы выяснили, в каком члене этого битфлажа живет, нам нужно убедиться, что мы установили правильный бит в это целое число. Это то, что 1 << i . Однако нам нужно убедиться, что мы не пытаемся получить доступ к 33-му биту в 32-битном целочисленном, поэтому операция сдвига ограничена с помощью 1 << (i & 0x1F) . Магия здесь заключается в том, что 0x1F равно 31, поэтому мы никогда не будем смещать бит, представленный i более чем на 31 место (в противном случае он должен был пройти в следующем члене a ).

From Here (Общий ответ для запуска этой темы)

Битовая маска – это значение (которое может быть сохранено в переменной), которое позволяет изолировать определенный набор битов в целочисленном типе.

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

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

Например, используя 16-разрядный короткий тип данных, предположите, что вы хотели бы иметь возможность маскировать биты 3, 4 и 5 (LSB – номер 0). Маска и смена выглядят примерно так:

 #define MASK 0x0038 #define SHIFT 3 

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

Если у меня есть переменная var, которая содержит данные, к которым относится маска, то я могу выделить биты, подобные этому

 var & MASK 

Я могу выделить все остальные биты как это

 var & ~MASK 

Я могу очистить бит, как это

 var &= ~MASK; 

Я могу очистить все остальные биты, как это

 var &= MASK; 

Я могу установить все биты как это

 var |= MASK; 

Я могу установить все остальные биты как это

 var |= ~MASK; 

Я могу извлечь десятичное значение битов, как это

 (var & MASK) >> SHIFT 

Я могу назначить новое значение таким битам

 var &= ~MASK; var |= (newValue << SHIFT) & MASK; 

Когда вы хотите установить бит внутри массива, вы должны

1. искать правильный индекс массива и
2. установите соответствующий бит внутри этого элемента массива.

В одном элементе массива есть бит BITSPERWORD (= 32), что означает, что индекс i должен быть разделен на две части:

• самые правые 5 бит служат индексом в элементе массива и
• остальные биты (крайние левые 28) служат индексом в массиве.

Ты получаешь:

• самые левые 28 бит, отбрасывая самую правую пятерку , что i>>SHIFT делает i>>SHIFT , и
• самые правые пять бит, маскируя все, кроме самых правых пяти бит , что i & MASK делает i & MASK .

Думаю, ты понимаешь остальное.

Поразрядная работа и ведущие параграфы Маски – краткое объяснение и содержат некоторые указатели для дальнейшего изучения.

Подумайте о 8-битном байте как наборе элементов из 8-элементного юниверса. Элемент IN находится в наборе, когда установлен соответствующий бит. Установка бит более одного раза не изменяет установленное членство (бит может иметь только 2 состояния). Побитовые операторы в C обеспечивают доступ к битам путем маскировки и сдвига .

Код пытается хранить N бит массивом, где каждый элемент массива содержит BITSPERWORD (32).

Таким образом, если вы пытаетесь получить доступ к биту i , вам нужно вычислить индекс элемента массива, который хранит его ( i/32 ), что i>>SHIFT делает i>>SHIFT .

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

(i & MASK) дает позицию бита в элементе массива (слово). (1<<(i & MASK)) устанавливает бит в этом положении.

Теперь вы можете установить / очистить / протестировать этот бит в a[i>>SHIFT] помощью (1< .

Вы также можете думать, что i - 32-битное число, что биты 6-31 - это индекс элемента массива, который хранит его, бит 0 ~ 5 представляет бит позицию в слове.