Поговорим о битах

---

Люди начинают спрашивать меня, читая мои записи в блоге - а что это такое "<<" или "&", как оно работает и вообще зачем оно нужно. Сегодня я вам об этом и расскажу.
Статья рассчитана на подрастающих девелоперов, ничего революционного в ней нет =)

Итак, что же творится behind the magic =)

Начнём с простого, вообще поймём, что же такое биты.

Есть байты. Байт - это 8 битов. А бит - это элемент, который может принимать значения 0 или 1. То есть байт - это восемь положений 0 или 1. (прошу прощения за мой очень вольный рассказ). Компьютер вообще работает с двоичной системой счисления, то есть у него есть только цифры 0 и 1. У нас их целых десять - 0,1,2,3,4..9. Поэтому привычная система исчисления для нас десятичная. И вот же проблема: компьютер использует двоичную, а мы привыкли использовать десятичную, как же нам... Да всё нормально, успокойтесь. Сущность числа не меняется от записи его в любой из систем исчисления.
Например, записав во флеше в шестандцатиричной системе 0xFF мы записали число 255. Поэтому делая trace(0xFFFFFF) мы видим какое то странно число, начинающиеся с 16.... Дело в том, что флеш специально выводит нам числа в десятичной системе, как нам удобно. А теперь давайте запишем какое-нибудь число, например "2" в двоичной системе, "родной" для компьютера:

10

Но каждый разряд принимает значения или 0, или 1. Это значит что каждый разряд - это бит. Но чаще люди записывают все 8 разрядов сразу, чтобы видеть тот самый байт.

00000010

Вот он байт. Таким байтом записано число 2 в компьютерном представлении. Конечно, оперировать с битами должно быть куда быстрее - мы будем отдавать компьютеру приказы в его "родной среде", поэтому важно понимать, как они работают и что делают.
Сейчас рассмотрим 3 оператора: |, & и >>, а потом посмотрим что же это дело делает на практике.

Оператор |: это оператор бинарного или. Он сравнивает каждый бит первого байта с соответствующим каждым битом второго байта, и если хотя бы один из них равен единице - на выходе будет единица.
Пример:
2 | 3 = 3
00000010 | 00000011 = 00000011

Важно! Первый бит идёт справа.

Сравниваем первый бит с первым битом: 0 | 1 = 1, т.к. хотя бы один из них равен единице.
Сравниваем второй бит с вторым битом: 1 | 1 = 1, т.к. хотя бы один из них равен единице.
Остальные биты: 0 | 0 = 0, т.к. ни один бит не равен единице.


Оператор &: это оператор бинарного и. Делает то же самое, что и "или", только чтобы на выходе была единица нужно чтобы оба бита были равны единице.
Пример:
2 & 3 = 2
00000010 & 00000011 = 00000010
Сравниваем первый бит с первым битом: 0 & 1 = 0, т.к. оба бита НЕ равны 1.
Сравниваем второй бит со вторым: 1 & 1 = 1, т.к. оба бита равны 1
Остальные: 0 & 0, т.к. оба бита не равны 1.

Оператор >>: это оператор сдвига вправо. Он сдвигает биты. Второй операнд - это на сколько битов нужно сдвинуть это число.
Например:
00001100 >> 1 = 00000110
Мы просто подвинули число целиком на бит вправо, а слева вдвинули ноль. Ещё пример:
11100000 >> 2 = 00111000
Мы сдвинули это число 2 раза вправо, а слева добавили 2 нуля.

Важно понять, что при сдвиге вправо разряды, которые "выбились" уходят в небытие и их уже никак не вернуть.
Например:
00000111 >> 2 = 00000001


Оператор << работает аналогично, но "вдвигает" нули справа, при этом количество байт, отводящиеся под это число может увеличиться.
UPD: я вот прочитал это и не знаю под каким веществом писал эту статью. Во флеше для целых чисел есть только int и uint, причем они оба всегда по 4 байта (32 бита). Что я имел ввиду под количеством "новых" байт останется для меня загадкой.
Например:
11000000 << 2 = 00000011 00000000

Мы подвинули число 2 раза влево, вдвинув нули справа, но из за этого число не смогло поместиться в 8 бит и ему был отведен ещё один байт. Максимальное число, которое можно "всунуть" байт - это 255 (11111111).

А вот теперь самое вкусное. Как это можно применить на практике?
Но сперва поправка: всё нижеописанное будет иметь место при работе с целыми положительными числами.

Наверное, вы уже задумались над тем, что если бит - это 0 или 1, то есть false или true - то можно передать 8 логических значений за один байт! Остался вопрос, как это сделать приятным для использования. А очень просто: у нас есть оператор |. И если мы заведем константы с числами "00000001", "00000010", "00000100" и т.д., то объединяя их мы можем получать комбинации для передачи этих самых 8 значений одним числом.
В итоге каждое число, от 0 до 255 будет занято какой-то одной уникальной комбинацией этих 8 флагов.
Ради примера сделаем что нужно передать 3 логических значения: горит ли первая лампочка, вторая и третья. Каждая из них может гореть вне зависимости, горит ли какая-то другая.
Сейчас для краткости записи я буду писать только первые 3 разряда, т.е. число 00000111 я буду записывать как 111.
Что делаем:
Заводим константы со значениями 001, 010, 100. В AS3 убрали возможность записывать число в двоичном виде, поэтому используя калкулятор записываем их в десятичном:
Кстати говоря, когда только один бит в числе равен единице - это какая то степень двойки, равная номеру биту по счету, начиная с 0.

Теперь, чтобы задать что горит, например, первая лампочка и третья нужно передать число 101. Его можно записать вот так: "100 | 001", то есть, проще говоря b1 | b3.
Вот и всё. Мы передали уникальное число, которое соответствует комбинации первой и третьей лампочки включенной, и выключенной второй. Осталось это дело только распознать там, куда мы это передали.

А распознаётся это дело с помощью оператора &. Это битовая маска, так сказать.
Наложить её очень просто: нужно просто понять, где нам нужно видеть биты, а где не нужно. Например, чтобы понять, включена ли первая лампочка нужно наложить на это переданное число маску "001" и посмотреть на результат. Второй и третий бит будут равны 0, т.к. оператор "и" их не пропустит, а результат от первой лампочки будет целиком зависеть от переданного числа: если первый бит у него 1 - результатом будет 1, если второй бит 0, то результатом будет 0.
Со второй лампочкой аналогично, накладывая маску 010 - если лампочка не горит, значит результат будет 0, если горит - результат будет 010. Почему 010, а не 001? Потому что маска "не убивает" разряды, она просто маскирует. Если этот момент вам неясен, тогда взгляните сюда:
111 & 010 = 010
1 & 0 = 0
1 & 1 = 1
1 & 0 = 0
Разряды не пропали.

Но вспомним: 010 у нас лежит в константе b2, а 001 в константе b1. В итоге, достаточно проверить (number & b1) > 0 чтобы понять, горит ли первая лампочка, (number & b2) > 0 чтобы понять, горит ли вторая. Заметьте, используя константы совсем нету необходимости помнить что какое число означает и делать какие-то сложные операции.
К слову, такой механизм реализован в Array.sort.

Теперь практическое применение сдвигов: предположим, у вас есть какой нибудь цвет, например 0x45FF15 и вам нужно узнать каждую его составляющую - красный, зеленый и синий. Зная битовые операции, нет ничего проще!

Начнем с синего. Синий цвет - это последние две цифры, нужно замаскировать остальные и оставить просто их. Да-да, замаскировать - значит наложить маску, осталось понять какую. А очень простую - 0x0000FF. Число 0x45FF15 - это 3 байта: третий байт 0x45, второй 0xFF, первый байт 0x15. 0x - это префикс, означающий что дальше пойдёт число в шестнадцатеричном исчислении.
Значит, нам нужно сделать маску, чтобы второй и третий байты были нулями, а всё в первом байте было единицами. Это позволит нам "убить" второй и третий байты, а первый байт мы оставим в первозданном виде. Значит, второй и третий байт должны быть по 0x00, а третий байт должен быть заполнен полностью единицами, то есть нести число 255 или 0xFF - это десятичная и шестнадцатеричная запись одного и того же числа, о чем рассказывалось ранее. Отсюда и получаем: 0x0000FF.
(0x45FF15 & 0x0000FF) = 0x000015
Нули справа незначимы - поэтому результат и есть 0x15 - то что нам нужно!

Теперь нужно взять второй байт - зеленый. Мыслим логически: сперва нужно спрятать все байты кроме второго. Аналогично

(0x45FF15 & 0x00FF00) = 0x00FF00

Хм, получилось, но не совсем... Вот бы сдвинуть FF вправо. Слово сдвинуть не о чем не напоминает? Именно, о сдвигах. Но на сколько сдвинуть? Сдвигаем мы на столько, чтобы правый байт ушел в небытие. А в байте 8 битов. Значит, нужно сдвинуть на 8!
0x00FF00 >> 8 = 0x0000FF = 0xFF
Получили заветное число. Как получить красный? "Наверное, нужно наложить маску на красный, а потом сдвинуть!" - скажете вы. Но всё ещё проще: правые байты уйдут вправо в небытие, оставив только третий байт, а слева вдвинуться нули - поэтому достаточно просто сдвинуть это дело на 16, т.е. на 2 байта:
(0x45FF15 >> 16) = 0x000045 = 0x45

В конце хочу сказать, что флеш предоставляет отличный метод у всех числовых типов: toString, который имеет аргумент radix. Он позволяет выводить число в любой системе исчисления. Например, чтобы увидеть результат (16 << 3) в двоичной системе достаточно ввести

А чтобы увидеть число 255 в шестандцатеричной:
(Скобки написаны ради того, чтобы компилятор воспринимал точку как оператор, а не как разделитель между дробной и целой частью).

Следует заметить, что в статье рассмотрены не все бинарные операторы.
Если тема вам интересна - предлагаю продолжить самообучение, например, отсюда.

Таким образом биты - это совсем не страшно, а вполне хороший инструмент для работы. Но и как любой инструмент его нужно применять там, где нужно. Например, пример с 8 флагами очень хорош для передачи по интернет-соединению, такому как сокет - вы будете экономить трафик сервера и пользователя, но не нужно ради какого-нибудь класса всего с 2 флагами вводить подобный трюк. Трюков с битами достаточно много - например ранее я рассказывал об умножении и делении на 2 путём сдвига, битовыми операциями можно делить с остатком и ещё много чего. Просто ищите, экспериментируйте и делитесь своим опытом с коллегами.