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

Question

Эй, в книге «Программирование жемчужин» есть исходный код для установки, очистки и проверки части заданного индекса в массиве целых чисел, который фактически является представлением набора.

Код следующий:

#include<stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000

int a[1+ N/BITSPERWORD];

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

void clr(int i)
{
    a[i>>SHIFT] &= ~(1<<(i & MASK));
}

int test(int i)
{
    a[i>>SHIFT] & (1<<(i & MASK));
}

Может ли кто-нибудь объяснить мне причину СДВИГА, и МАСКА определяет? И каковы их цели в коде?

Я уже прочитал предыдущий связанный вопрос .

Answer 1

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

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

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

Answer 2

С Здесь (Общий ответ, чтобы начать эту тему)

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

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

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

Например, используя 16-битный короткий тип данных, предположим, что вы хотите иметь возможность маскировать биты 3, 4 и 5 (младший бит равен 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;

Answer 3

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

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

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

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

Вы получаете:

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

Полагаю, вы понимаете все остальное.

Answer 4

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

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

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

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

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

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

Answer 5

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

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