Использование битовой маски в программе ниже от Programming Pearls
Сегодня я начал читать "Программирование жемчуга" и, выполняя его упражнение, натолкнулся на вопрос "Как бы вы реализовали свой собственный битовый вектор?". Когда я посмотрел на решение, это было так:
#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));
Где я запутался в этом утверждении
1 << (i & MASK)
Может кто-нибудь объяснить мне, что здесь происходит?
2 ответа
Обратите внимание, что MASK устанавливается так, чтобы он имел самый низкий SHIFT биты установлены, где SHIFT это точно логарифм по основанию 2 BITSPERWORD,
Следовательно (i & MASK) выберет самые низкие 5 бит i, что аналогично получению остатка после деления на 32 (просто подумайте, как, например, взятие двух младших цифр десятичного числа дает остаток после деления на 100). Это дает номер бита в слове, которое нас интересует.
1 << (i & MASK)) (которое, кстати, является выражением, а не утверждением) теперь создает значение, в котором установлен именно тот бит, который нас интересует. Слияние этого значения в слово памяти с |= установит желаемый бит вектора битов.
0x20 это 32, так i & 0x1F принимает i по модулю 32, так что вы никогда не сдвигаетесь на 32 бита. Это гарантия, потому что смещение на что-то, что не строго меньше размера шрифта, является неопределенным поведением.