О битовых операциях
Число в двоичной записи можно использовать как множество или битовые флаги. В таком виде проще познакомится с побитовыми операциями.
Возьмем для примера число 168, в двоичной записи это (1010 1000).
Получается множество {7, 5, 3} или можно сказать что включен флаг 7, 5, 3
Для битовых флагов позволяет узнать включены ли нужные флаги
flags = 1010 1000
mask = 0000 1000 - хотим узнать включен ли 3й бит
(flags&mask)==mask
Возьмем для примера число 168, в двоичной записи это (1010 1000).
7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
Логические побитовые операции
Побитовое НЕ
Инвертирует состояние каждого бита.
Унарный префиксный оператор ^
Унарный префиксный оператор ^
^(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}
Для множества это операция пересечение
(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
- (flags&mask) = (1010 1000)&(0000 1000)=(0000 1000)
- сравниваем маску с результатов (0000 1000)= (0000 1000). если равны то биты включены
Так же можно использовать для усечение до нужно длины
flags &= 0xFF - выставит все что больше 8 бит в 0
Побитовое И НЕ
Позволяет сбрасывать биты
flags = 1010 1000
mask = 0000 1000 - хотим выключить 3й бит
flags& ^mask
flags& ^mask
- ^mask = (1111 0111)
- (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}
(1010 1000)&^(0110 1001)=(1010 1000)&(1001 0110)=(1000 0000)={7}
Побитовое ИЛИ
Любой бит, установленный в 1, вызывает установку соответствующего бита результата также в 1
Позволяет включить нужные биты
flags = 1010 1000
Для множеств это симметричная разность
(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
Позволяет включить нужные биты
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 1111 - хотим переключить 3,2,1,0 биты, 7-4 не изменятся
flags^mask
(1010 1000)|(0000 1111)=(1010 0111)
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
flags| ^mask
- ^mask = (1111 0111)
- (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 << 5 =(0010 0000)
- (1010 1000) & (0010 0000) = (0010 0000)
- (0010 0000) != 0 значит 5 входит в множество (1010 1000)
В следующей части задачи посложней.
Комментарии
Отправить комментарий