Практическое применение (Битовые маски,...)

— Привет, Амиго!

Еще хотел бы рассказать про битовые маски и XOR.

Ты уже знаешь, что числа состоят из битов и над этими битами можно производить различные операции. Битовая маска – это когда мы храним много различных логических значений (true/false) в виде одного целого числа. При этом каждому boolean-значению соответствует определенный бит. Вот как это можно делать:

Числа-степени двойки (1,2,4,8,16,32,…) занимают в двоичном представлении числа всего по одному биту:

Поэтому любое целое число можно рассматривать, как массив бит или массив boolean.

Вот как можно хранить различные логические значения в одном числе:

boolean a = true;
boolean b = false;
boolean c = true;
boolean d = false;

int result = 0;
 if (a) result += 1; //1 == 20 — нулевой бит
 if (b) result += 2; //2 == 21 — первый бит
 if (c) result += 4; //4 == 22 — второй бит
 if (d) result += 8; //8 == 23 — третий бит

Теперь каждый бит равен 1, если соответствующая ему логическая переменная была true.

В нашем случае true были переменные a и c, значит число result равно 1+4 ==5

0000 0101
0000 dcba

— Вроде понятно, что происходит.

— Ну, раз понятно, то пошли дальше.

В числе int 32 бита, один из них используется для знака, а еще 31 можно использовать для хранения значений 31-й булевской переменной.

— А в числе long 64 бита. Мы там можем хранить 63 логических переменных.

— Ага.

— Полсотни переменных в одном числе. Немало.

А где такое применяется?

— В основном там, где надо компактно хранить много информации об объектах. Когда хранишь много информации об объекте, всегда наберется пара десятков логических переменных. Вот их всех удобно хранить в одном числе.

Именно хранить. Т.к. пользоваться им в работе не так уж удобно.

— Кстати, как раз хотел спросить. А как нам обратно получить логические значение их числа?

— Это совсем не сложно. Вот допустим тебе нужно узнать, установлен ли 5-й бит числа в единицу или нет (2 в пятой степени – это 32). Вот как это можно проверить:

int a = 32; //25 == 0010 0000
int b = 8; //23 == 0000 1000
int c = 2; //21 == 0000 0010

int result = a+b+c; //32+8+2 == 42 == 0010 1010

int a = result & 32; // 0010 1010 & 0010 0000 = 0010 0000
int b = result & 8; // 0010 1010 & 0000 1000 = 0000 1000
int c = result & 2; // 0010 1010 & 0000 0010 = 0000 0010

Т.е. фактически, для работы с битовыми масками нужны три операции:

1) Установить определенный бит в 0

2) Установить определенный бит в 1

3) Проверить, какое значение определенного бита.

Возьмем, например, бит номер 6.

Как установить в 1 бит 6?

result = result | 01000000;
result |= 01000000;

result = result & 10111111;
result &= 10111111;

с = result & 01000000;

— Очень необычно, но не сложно. Я ж теперь уже крутой программист.

— И теперь еще маленькая подсказка. Как легко получить числа со снятым или установленным определенным битом: 01000000 или 10111111.

Для этого у нас есть операции сдвига >> и <<.

Вот 1 – это 2 в нулевой степени. Т.е. число с установленным нулевым битом. Нам надо число с установленным 6-м битом.

int c = 1<<6; //0000 0001 <<6 == 0100 0000 == 64

— Круто! Действительно полезная вещь для таких дел.

А если мне нужно число, где все биты 1, а один определенный – 0?

— Это тоже не сложно:

int d = ~(1<<6); //~0100 0000 == 10111111

Т.е. все очень просто:

result = result | (1<<6);
result |= (1<<6);

result = result & ~(1<<6);
result &= ~(1<<6);

с = result & (1<<6);

— Выглядит не очень сложно. Но так сразу — не запомню.

— Зато, если встретишь где-то в чужом коде такое страшное выражение:

«result &= ~(1<<6)», будешь знать, что это кто-то просто работает с битовой маской. А если часто будешь встречать, то вскоре все само запомнится.

— Само запомнится… Хорошо звучит. Спасибо за лекцию.