О битовых операциях

Число в двоичной записи можно использовать как множество или битовые флаги. В таком виде проще познакомится с побитовыми операциями.

Возьмем для примера число 168, в двоичной записи это (1010 1000).

7	6	5	4	3	2	1	0
1	0	1	0	1	0	0	0

Получается множество {7, 5, 3} или можно сказать что включен флаг 7, 5, 3

Логические побитовые операции

Побитовое НЕ

Инвертирует состояние каждого бита.
Унарный префиксный оператор ^

^(1010 1000)=(0101 0111)

Побитовое И

Логическое & к каждой паре битов. Если оба бита равны 1 то результат будет 1, в остальных случаях 0.

Бинарный оператор &

Для множества это операция пересечение
(1010 1000) = {7, 5, 3}
(0110 1001) = {6, 5, 3, 0}
(1010 1000)&(0110 1001)=(0010 1000) = {5, 3}

Для битовых флагов позволяет узнать включены ли нужные флаги
flags = 1010 1000
mask = 0000 1000 - хотим узнать включен ли 3й бит
(flags&mask)==mask

1. (flags&mask) = (1010 1000)&(0000 1000)=(0000 1000)
2. сравниваем маску с результатов (0000 1000)= (0000 1000). если равны то биты включены

Так же можно использовать для усечение до нужно длины

flags &= 0xFF - выставит все что больше 8 бит в 0

Побитовое И НЕ

Позволяет сбрасывать биты

flags = 1010 1000

mask = 0000 1000 - хотим выключить 3й бит
flags& ^mask

1. ^mask = (1111 0111)
2. (1010 1000) & (1111 0111) = (1010 0000)

Для множеств это операция разности

(1010 1000) = {7, 5, 3}

(0110 1001) = {6, 5, 3, 0}
(1010 1000)&^(0110 1001)=(1010 1000)&(1001 0110)=(1000 0000)={7}

Побитовое ИЛИ

Любой бит, установленный в 1, вызывает установку соответствующего бита результата также в 1

Позволяет включить нужные биты
flags = 1010 1000

mask = 0000 1111 - хотим выключить 3,2,1,0 биты
flags|mask
(1010 1000)|(0000 1111)=(1010 1111)

Для множеств это операция объединение
(1010 1000) = {7, 5, 3}
(0000 1111) = {3, 2, 1, 0}
(1010 1000)|(0000 1111)=(1010 1111) = {7, 5, 3, 2, 1, 0}

Побитовое ИЛИ НЕ

flags = 1010 1000

mask = 0000 1000
flags| ^mask

1. ^mask = (1111 0111)
2. (1010 1000)|(1111 0111) = (1111 1111)

Побитовое исключающее ИЛИ

Исключающее ИЛИ устанавливает значение бита результата в 1, если значения в соответствующих битах исходных переменных различны

Позволяет переключить нужные биты
flags = 1010 1000
mask = 0000 1111 - хотим переключить 3,2,1,0 биты, 7-4 не изменятся
flags^mask
(1010 1000)|(0000 1111)=(1010 0111)

Для множеств это симметричная разность
(1010 1000) = {7, 5, 3}
(0000 1111) = {3, 2, 1, 0}
(1010 1000)^(0000 1111)=(1010 0111)={7, 5, 2, 1, 0}

Побитовые сдвиги

Операторы сдвига << и >> сдвигают биты в переменной влево или вправо на указанное число.
Арифметически сдвиг влево эквивалентен умножению на 2^n, а сдвиг вправо деление на 2^n.
Сдвиг влево заполняет освобождающиеся биты нулями, так же, как сдвиг вправо беззнакового значения. Но сдвиг вправо знаковых чисел заполняет освобождаемые биты копиями знакового бита.

Беззнаковый сдвиг
15 = (0000 1111)
15 << 2 = 60 = (0011 1100)
15 >> 2 = 3 = (0000 0011)

Знаковый сдвиг
-15 = (-000 1111)
-15 << 2 = -60 = (-011 1100)
-15 >> 2 = -4 = (-000 0100)

Проверка принадлежности множеству
N = (1010 1000) = {7, 5, 3}
n = 5 -проверить принадлежит 5 множеству N
N&(1 << n) -принадлежит при неравенстве 0

1.  1 << 5 =(0010 0000)
2. (1010 1000) & (0010 0000) = (0010 0000)
3. (0010 0000) != 0 значит 5 входит в множество (1010 1000)

В следующей части задачи посложней.