О чем статья
В данной статье, я хочу на простом примере рассказать про битовые операции в программировании. Битовые операции активно используются на протяжении всей истории электроники и вычислительной техники, но современные программисты часто оставляют этот инструмент без внимания. Чтобы статья была максимально приближена к реальности, я подготовил пример c несуществующей игрой и абстрактными котятами.
Расскажу об одном из способов применения битовых операций, которым я сам регулярно пользуюсь при разработке игр. Речь пойдет об упаковке и распаковке данных с помощью битовых операций.
Вы узнаете как запаковать JSON:
{ "color": "ginger", "age": 3, "tailStripes": true, "backStripes": true, "faceStripes": true }
в число807
Задача
Давайте представим, что мы работаем над игрой — симулятором сильных независимых женщин, — и получаем от отдела дизайна задание по добавлению котят в игру. На момент постановки задачи котята бывают 5 цветов, но в дальнейшем их может стать больше (не больше 10).
Кроме разных цветов у котят могут появляться полоски на мордашках, хвостиках и спинках:
Помимо цвета и полосок котята могут взрослеть, но не могут быть старше 6 месяцев. Возраст отражается в длине их тушек:
Реализация
Начнем с того, что опишем простой класс Kitten
с полями под необходимые данные: цвет, полоски, возраст:
class Kitten
{
constructor(color, age, tailStripes, backStripes, faceStripes) {
this.color = color;
this.age = age;
this.tailStripes = tailStripes;
this.backStripes = backStripes;
this.faceStripes = faceStripes;
}
}
Так как мы работаем над уже «существующей» игрой, попросим движок вывести на экран несколько котят, чтобы убедиться в правильности выполнения задачи:
const colors = ["devil","black","white","gray","ginger"];
for(let i = 0; i < 5; i++) {
kitten_render(new Kitten(
colors[i], // цвета от Devil до Ginger
i + 2, // возраст от 2 до 6
i % 2 != 0, // каждый второй котенок без полосок на хвосте
i % 3 == 0, // каждый третий котенок с полосками на спинке
i % 2 == 0 // каждый второй котенок с полосками на мордочке
));
}
Запускаем код и видим, что задача выполнена, и можно идти отдыхать.
Оптимизация
Но на следующий же день из отдела QA\техлида\сторонника оптимизации, приходит задача в таск-менеджер: Оптимизировать загрузку комнаты. В подробном описании говорится, что появился заметный лаг при входе в комнату сильной независимой женщины.
При изучении проблемы становится понятно, что время загрузки увеличилось пропорционально времени загрузки JSON данных по сети, так как в среднем в комнате по 40-50 котят, и объекты Kitten
занимают много места:
{
"color": "ginger",
"age": 3,
"tailStripes": true,
"backStripes": true,
"faceStripes": true
}
Количество котят уменьшать нельзя, нужно оптимизировать формат сохранения. Можно сократить названия ключей, но есть вариант лучше: сохранять новорожденного дьявольского котенка без полосок как 0
, а новорожденного черного котенка с полосками на хвостике как 1
и т.д. со всеми вариантами котят. Чтобы получать из объекта Kitten
целочисленное значение и не составлять таблицу всех возможных котят, мы воспользуемся битовыми операциями.
Упаковка данных
Для эффективной запаковки данных мы будем использовать битовые операции над целочисленными значениями. Чтобы понять процесс, давайте разберемся, что такое целочисленное значение для компьютера. Все данные компьютер воспринимает как набор двоичных значений: 0
и 1
, а целочисленные значения как совокупность 32-х двоичных значений (актуально для js и Int32 в строго типизированных языках).
Приведу табличку значений от 0 до 8 и их двоичное представление:
0000 0000 0000 0000 0000 0000 0000 0000
0
0000 0000 0000 0000 0000 0000 0000 0001
1
0000 0000 0000 0000 0000 0000 0000 0010
2
0000 0000 0000 0000 0000 0000 0000 0011
3
0000 0000 0000 0000 0000 0000 0000 0100
4
0000 0000 0000 0000 0000 0000 0000 0101
5
0000 0000 0000 0000 0000 0000 0000 0110
6
0000 0000 0000 0000 0000 0000 0000 0111
7
0000 0000 0000 0000 0000 0000 0000 1000
8
И отдельно для значения 16:
0000 0000 0000 0000 0000 0000 0001 0000
16
Прошу вас обратить особое внимание на двоичное представление значений 1
, 2
, 4
, 8
и 16
. Их объединяет особенность: все двоичные значения, кроме одного, равны 0. Чем это удобно для нас? Мы можем сказать, что первый бит — это полоски на хвостике, второй — на спинке, а третий - мордашка. Тогда для котенка с полосками на спинке и хвостике первый и второй бит будут равны 1
, а третий - 0
. Получим: 0000 0011
или 3
в десятичном представлении. Давайте посмотрим в виде таблицы:
Место | |||
---|---|---|---|
Хвостик | 0 | 1 | 0 |
Cпинка | 0 | 1 | 1 |
Мордашка | 1 | 1 | 0 |
Итого (бинарно) | 100 |
111 |
010 |
Итого (десятично) | 4 | 7 | 2 |
Давайте начнем записывать формат запаковки в комментариях к объекту Kitten:
ХХХ
││└ Tail stripes flag
│└─ Back stripes flag
└── Face stripes flag
Используя полученные знания, уже можно сократить объем данных до: { "color": "ginger", "age":3, "stripes": 3 }
, это заметно сократит объем передаваемых данных, но наша цель — одно целочисленное значение.
Цвет в отличие от полосок может быть только один, то есть дьявольско-рыжего котенка в игре быть не может, а так же цветов не больше 10. Так как 9 (считаем вместе с 0) в двоичной системе это: 1001
, для хранения нам нужно 4 бита. Учтивая, что 1111
- это 15, у нас будет запас на 6 дополнительных цветов.
Так как котята в нашем случае не могут быть старше 6 месяцев, для записи возраста хватит трех битов (111
- это 7). Учитывая цвет и возраст, дополняем наш формат запаковки данных:
ZZZYYYYХХХ 10 bits
└┬┘└─┬┘││└ Tail stripes flag 1 bit
│ │ │└─ Face stripes flag 1 bit
│ │ └── Back stripes flag 1 bit
│ └──── Color data 4 bits
└──────── Age data 3 bit
Поэкспериментируем со значениями. В какулятор ниже попробуйте получить значение для котенка с полосками на хвостике и мордашке, серого цвета и 4-х месяцев от роду:101
– флаги для полосок0011
– цвет котенка (3)100
– возраст котенка (4)
Запишите последовательно все значения в калькулятор (1000011101
):
Получите 541 в десятичном представлении. То есть для сохранения указанного выше котенка нужно будет записать в JSON 541
, а не: {"color": "gray", "age":4, "tailStripes":true, "backStripes":true, "faceStripes":false }
.
Запись значений в бинарные данные
В ручную у нас вышло получить 541
из котенка, давайте теперь разберемся как это сделать в коде. Самое замечательное, что битовые операции (bitwise) во всех мне известных языках имеют одинаковый синтаксис, и пример на JS можно использовать в C#, Java, C++.
Единственный (pascal не в счет) известный мне синтаксис битовых операций выглядит следующим образом (что он делает и как - разберем дальше):
a & b // Побитовое И
a | b // Побитовое ИЛИ
a ^ b // Побитовое НЕ И (исключающее ИЛИ)
~a // Побитовое НЕ
a << b // Сдвиг влево
a >> b // Сдвиг вправо
Для записи значений со смещением воспользуемся сдвигом.
Побитовые сдвиги
Сдвиги бывают в два направления: влево и вправо. Работают очень просто: берут двоичное представление и двигают биты в указанное направление, отбрасывая биты, выходящие за границы:
| | borders
XXXX 0000 0000 0000 0000 0000 0000 0000 0001 XXXX original is ONE
XXXX 0000 0000 0000 0000 0000 0000 0000 0000 1XXX shift right (1 is outside)
XXXX 0000 0000 0000 0000 0000 0000 0000 0000 XXXX final is ZERO
XXXX 0000 0000 0000 0000 0000 0000 0000 0001 XXXX original is ONE
XXXX 0000 0000 0000 0000 0000 0000 0000 0010 XXXX shift left
XXXX 0000 0000 0000 0000 0000 0000 0000 0010 XXXX final is TWO
Попробуйте поставить несколько бит в целочисленное значение и подвигать:
Когда я сказал, что мы будем записывать значения со смещением, я лукавил, мы будем их писать в начало, а после сдвигать в отведенное для них место. Например, цвет, согласно нашей схеме, должен находиться в данных со сдвигом на три бита влево, сразу после флагов полосок. Давайте попробуем сдвинуть серый цвет (3 или 011)
const a = 3; // 00000011
const b = a << 3; // 00011000
Аналогично с цветом, получим значения со сдвигом для всех данных о котенке:
const KITTEN_COLOR_CODES = {
devil: 0,
black: 1,
white: 2,
gray: 3,
ginger: 4
};
const KITTEN_TAIL_OFFSET = 0;
const KITTEN_FACE_OFFSET = 1;
const KITTEN_BACK_OFFSET = 2;
const KITTEN_COLOR_OFFSET = 3;
const KITTEN_AGE_OFFSET = 7;
class Kitten
{
// CONSTRUCTOR
pack() {
const tailData = this.tailStripes << KITTEN_TAIL_OFFSET;
const faceData = this.faceStripes << KITTEN_FACE_OFFSET;
const backData = this.backStripes << KITTEN_BACK_OFFSET;
const ageData = this.age << KITTEN_AGE_OFFSET;
const colorData = KITTEN_COLOR_CODES[this.color] << KITTEN_COLOR_OFFSET;
// should return packed data of instance
return 0;
}
}
Теперь предстоит полученные бинарные данные склеить в одно, склеивать данные можно оператором ИЛИ.
Побитовое ИЛИ
Чтобы понять побитовые ИЛИ, И и НЕ И, проще всего представить двоичные значения как массивы значений Boolean
. А использование битовых операторов воспринимать как операции сравнения (&&
, ||
, !=
) логических типов (boolean) и запись результатов в третий массив.
Давайте разберемся на примере:
У нас есть значения 0110
(6) и 0011
(3), но мы представляем их как [false, true, true, false]
и [false, false, true, true]
. В цикле for(let i = 0; i < 4; i++)
сравним left[i]
и right[i]
оператором ||
, а результат запишем в result[i]
.
const left = [false, true, true, false];
const right = [false, false, true, true];
let result = [];
for(let i = 0; i < 4; i++) {
result[i] = left[i] || right[i];
}
Надеюсь, что табличка ниже поможет разобраться.
┌──────────────────┬───────────────────┬───────────────────┐
│ Значения A │ Значения Б │ Результат при ИЛИ │
│ bin bool │ bin bool │ bin bool │
├───────┼──────────┼───────┼───────────┼───────┼───────────┤
│ 0 │ false │ 0 │ false │ 0 │ false │
│ 1 │ true │ 0 │ false │ 1 │ true │
│ 1 │ true │ 1 │ true │ 1 │ true │
│ 0 │ false │ 1 │ true │ 1 │ true │
└───────┴──────────┴───────┴───────────┴───────┴───────────┘
Ну и результат вместе:
Как видите оператор ИЛИ «склеивает» два значения в одно, а это именно то, что нам нужно в задаче с котятами. Просто надо взять и побитово склеить все значения и вернуть как результат метода pack()
:
pack() {
const tailData = this.tailStripes << KITTEN_TAIL_OFFSET;
const faceData = this.faceStripes << KITTEN_FACE_OFFSET;
const backData = this.backStripes << KITTEN_BACK_OFFSET;
const ageData = this.age << KITTEN_AGE_OFFSET;
const colorData = KITTEN_COLOR_CODES[this.color] << KITTEN_COLOR_OFFSET;
return tailData | backData | faceData | colorData | ageData;
}
Выведем на экран вместе со спрайтом котенка его запакованное значение:
Как видим у каждого котенка запакованное значение уникально и теперь можно сохранять котят как массив целочисленных значений, что существенно сократит размер JSON данных, но нужно научиться их распаковывать.
Распаковка данных
Теперь от сервера мы получаем информацию о котенке как целочисленное значение. Например, 423
для трехмесячного рыжего котенка с полосками на хвостике, спинке и мордашке.
В двоичном представлении 423
это: 0000 0000 0000 0000 0000 0000 1110 0111
. Нас же интересуют только последние 10 бит, где 0-2 - полоски, 3-6 - цвет, а 7-9 - возраст. В случае 423
, полоски — это 111
, цвет — 0100
(4), возраст — 0011
(3).
Чтобы вычленить нужные нам биты, будем использовать оператор И и уже знакомые нам сдвиги.
Оператор И
Как мы уже видели выше, побитовые И, ИЛИ и НЕ И можно воспринимать как привычное сравнение булевых значений в цикле, но в отличие от ИЛИ, для И мы бы использовали оператор &&
. Другими словами, result[i] == left[i] && right[i];
и принимает true
только когда оба значения true
.
Для извлечения части битов из данных применим оператор И вместе с маской явно указывающей на интересующие данные. В случае с цветом, применение битового оператора &
для двоичного значения котенка 423 (011 0100 111
) и маски цвета 120 (000 1111 000
) вернет 000 0100 000
. Осталось только сдвинуть вправо полученное значение и мы видим, что это интересующий нас рыжий (ginger) цвет, или 4 в десятичном представлении.
Создавать битовые можно следующей операцией:
((1 << bitCount) - 1) << offset
Как это работает: маска 1111 0000
— это 1111
со сдвигом влево на 4 бита, а 1111
— это 15
или 16 - 1
. 16
— это степерь двойки или 1 << 4
. Таким образом искомая маска — это ((1 << 4) - 1) << 4
.
Подготовим необходимые для извлечения данных маски:
function bitMask(bitCount, offset) {
return ((1 << bitCount) - 1) << offset;
}
const KITTEN_TAIL_MASK = bitMask(1, KITTEN_TAIL_OFFSET);
const KITTEN_FACE_MASK = bitMask(1, KITTEN_FACE_OFFSET);
const KITTEN_BACK_MASK = bitMask(1, KITTEN_BACK_OFFSET);
const KITTEN_COLOR_MASK = bitMask(4, KITTEN_COLOR_OFFSET);
const KITTEN_AGE_MASK = bitMask(3, KITTEN_AGE_OFFSET);
Теперь когда у нас есть сдвиги и маски, мы можем получить из данных интересующую нас информацию, например, возраст: (data & KITTEN_AGE_MASK) >> KITTEN_AGE_OFFSET
, но чтобы не писать всю конструкцию для каждого поля данных, сделаем вспомогательную функцию bitData
:
function bitData(value, mask, offset) {
return (value & mask) >> offset;
}
В реальном проекте советую создать для методов bitMask
, bitData
отдельный модуль и использовать его методы везде где они требуются.
Для разработки на Unity вы можете найти все методы работы с бинарными данными в моей библиотеке Uniful, что доступна на github
Создадим в классе Kitten
метод для распаковки значений
const KITTEN_COLOR_NAMES = [
"devil",
"black",
"white",
"gray",
"ginger"
];
class Kitten
{
// constructor
// pack()
static unpack(data) {
let instance = new Kitten();
instance.tailStripes = !!bitData(data, KITTEN_TAIL_MASK, KITTEN_TAIL_OFFSET);
instance.faceStripes = !!bitData(data, KITTEN_FACE_MASK, KITTEN_FACE_OFFSET);
instance.backStripes = !!bitData(data, KITTEN_BACK_MASK, KITTEN_BACK_OFFSET);
instance.color = KITTEN_COLOR_NAMES[bitData(data, KITTEN_COLOR_MASK, KITTEN_COLOR_OFFSET)];
instance.age = bitData(data, KITTEN_AGE_MASK, KITTEN_AGE_OFFSET);
return instance;
}
}
Теперь наша система готова! Можем проверить вывод пяти котят: [791, 540, 135, 288, 0]
Концепция изменилась
Раз уж у нас статья максимально приближенна к реальности, то без заветной фразы «концепция поменялась» она будет неполной.
Гордые за проделанную работу мы отмечаем задачу в таск-менеджере как завершенную, но видим, что появилась новая: Изменения котят, а тело задачи говорит:
Исследования показали, что сильные независимые женщины предпочитают ограниченную палитру цветов, но любят сочетания цветов!
Нужно сделать так, чтобы котята могли быть двух-цветными: один цвет для тела, второй для мордочки.
Новых цветов добавлять не нужно!
Изменение данных
Сценарий внесения изменений у нас будет таким же как и реализация первой версии:
- Подготовим объект со всеми полями для данных
- Составим схему хранения данных
- Напишем реализацию для упаковки и распаковки данных
Добавим в класс Kitten поле faceColor
:
class Kitten
{
constructor(color, age, tailStripes, backStripes, faceStripes, faceColor) {
this.color = color;
this.faceColor = faceColor;
this.age = age;
this.tailStripes = tailStripes;
this.backStripes = backStripes;
this.faceStripes = faceStripes;
}
}
Так уж получилось, что в рамках статьи мы инженеры по упаковке данных и магическим образом движок игры уже умеет рисовать разноцветных котят. Поэтому сразу перейдем к обновлению схемы.
Что изменилось в данных? Во первах, цветов теперь меньше. То есть мы можем хранить цвет в 3-х битах, вместо 4-х изначально выделенных под увеличение палитры. Во вторых, нужно выделить еще 3 бита под дополнительный цвет. Обновим нашу схему запаковки данных:
FFFZZZYYYXХХ 12 bits
└┬┘└┬┘└┬┘││└ Tail stripes flag 1 bit
│ │ │ │└─ Face stripes flag 1 bit
│ │ │ └── Back stripes flag 1 bit
│ │ └──── Color data 3 bits
│ └─────── Age data 3 bits
└────────── Face color data 3 bits
Изменим константы KITTEN_COLOR_MASK
, KITTEN_AGE_OFFSET
и добавим две новые для хранения сдвига цвета мордашек: KITTEN_FCOLOR_OFFSET
и KITTEN_FCOLOR_MASK
:
const KITTEN_AGE_OFFSET = 6;
const KITTEN_FCOLOR_OFFSET = 9;
const KITTEN_COLOR_MASK = bitMask(3, KITTEN_COLOR_OFFSET);
const KITTEN_FCOLOR_MASK = bitMask(3, KITTEN_FCOLOR_OFFSET);
По аналогии с основным цветом, добавим упаковку и распаковку цвета мордашки:
pack() {
const tailData = this.tailStripes << KITTEN_TAIL_OFFSET;
const faceData = this.faceStripes << KITTEN_FACE_OFFSET;
const backData = this.backStripes << KITTEN_BACK_OFFSET;
const ageData = this.age << KITTEN_AGE_OFFSET;
const colorData = KITTEN_COLOR_CODES[this.color] << KITTEN_COLOR_OFFSET;
// FACE COLOR
const fcolorData = KITTEN_COLOR_CODES[this.faceColor] << KITTEN_FCOLOR_OFFSET;
return tailData | backData | faceData | colorData | ageData | fcolorData;
}
static unpack(data) {
let instance = new Kitten();
instance.tailStripes = !!bitData(data, KITTEN_TAIL_MASK, KITTEN_TAIL_OFFSET);
instance.faceStripes = !!bitData(data, KITTEN_FACE_MASK, KITTEN_FACE_OFFSET);
instance.backStripes = !!bitData(data, KITTEN_BACK_MASK, KITTEN_BACK_OFFSET);
instance.color = KITTEN_COLOR_NAMES[bitData(data, KITTEN_COLOR_MASK, KITTEN_COLOR_OFFSET)];
instance.age = bitData(data, KITTEN_AGE_MASK, KITTEN_AGE_OFFSET);
// FACE COLOR
instance.faceColor = KITTEN_COLOR_NAMES[bitData(data, KITTEN_FCOLOR_MASK, KITTEN_FCOLOR_OFFSET)];
return instance;
}
Все мы внесли необходимые изменения! Надеюсь, что больше правок не будет, а вам понравилась статья. Ну и финальное демо котят, чтобы вы могли себя почувствовать сильной независимой женщиной и создать своего идеального друга: