Использование битовой маски в программе ниже от Programming Pearls

Question

Я начал читать «Программирование жемчуга» сегодня и, выполняя его упражнение, я столкнулся с вопросом «Как бы вы реализовали свой собственный битовый вектор?» Когда я посмотрел на решение, это было так:

#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)

Может кто-нибудь объяснить мне, что здесь происходит?

Answer 1

Обратите внимание, что MASK установлено таким образом, что для него установлены самые младшие SHIFT биты, где SHIFT - это точно логарифм по основанию 2 BITSPERWORD.

Поэтому (i & MASK) выберет5 самых младших битов i, что равносильно получению остатка после деления на 32 (просто посмотрите, как, например, взятие двух младших цифр десятичного числа дает остаток после деления на 100).Это дает номер бита в интересующем нас слове.

1 << (i & MASK)) (который, кстати, является выражением , а не оператор ) теперь создает значение, в котором установлен именно тот бит, который нас интересует.Слияние этого значения в слово памяти с помощью |= установит желаемый бит вектора битов.

Answer 2

0x20 равно 32, поэтому i & 0x1F занимает i по модулю 32, так что вы никогда не сдвигаетесь на 32 бита.Это является гарантией, потому что смещение на что-либо, не превышающее размер шрифта, является неопределенным поведением.