Поговорим о битах
Люди начинают спрашивать меня, читая мои записи в блоге - а что это такое "<<" или "&", как оно работает и вообще зачем оно нужно. Сегодня я вам об этом и расскажу.
Статья рассчитана на подрастающих девелоперов, ничего революционного в ней нет =)
Итак, что же творится 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 убрали возможность записывать число в двоичном виде, поэтому используя калкулятор записываем их в десятичном:
Код:
const b1 = 1 const b2 = 2 const b3 = 4
Теперь, чтобы задать что горит, например, первая лампочка и третья нужно передать число 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 путём сдвига, битовыми операциями можно делить с остатком и ещё много чего. Просто ищите, экспериментируйте и делитесь своим опытом с коллегами.
Всего комментариев 72
Комментарии
04.09.2010 02:42 | |
Билл ( не гейтс) - где ты?
Цитата:
Поиск, БК, ДВК, Вектор-06ц, Корвет, Орион
а вот о Цитата:
MSX-2
у меня были ИМПУЛЬС-М, Дубна и всякий самосбор.. первый мой айти-бизнес был: торговал пираткой (кассетами), когда еще и слов таких не было (айти и пиратка). Каталоги с играми, заказы, запись с кассеты на кассету через doubleClone.. веселуха.. денег получал больше чем родители-инженеры ( учился в 8 классе) А потом пришёл денди и весь мой бизнес обломал))) |
|
Обновил(-а) Котяра 04.09.2010 в 04:42
|
04.09.2010 19:59 | |
Существует 10 типов людей: одни понимают двоичную систему, другие - нет...
|
04.09.2010 20:26 | |
тонко
|
05.09.2010 03:56 | |
Такое решение не зачет?
Код:
//значения переменных в пределах 0-255, т.е. "размерность" 8 бит //перемещение битов var foo = 4;//0000 0100 (4) var bar = 3;//0000 0001 (1) foo = bar << 6 & 0xс0 | foo >> 2; bar >>= 2; trace([foo, bar]);// 0100 0001, 0000 0000 (65,0) //вращение сюда var lreg = 133;//1000 0101 (133) lreg = lreg >> 7 | lreg << 1 & 0xfe; trace(lreg);// 0000 1011 (11) //вращение туда var rreg = 133;//1000 0101 (133) rreg = rreg << 7 & 0x80 | rreg >> 1; trace(rreg);// 1100 0010 (194) |
|
Обновил(-а) alexcon314 05.09.2010 в 04:21
|
06.09.2010 17:29 | |
переходим на ZX Spectrum)
|
09.09.2010 23:23 | |
CF - это не для меня. Во всяком случае сейчас.
Завтра (ну уже сегодня) думаю купить веб-камеру и поизучать Augmented Reality, может напишу пару статей о нём. Очень нравится =) |
09.09.2010 23:27 | |
Согласен. Не в CF дело. О чем и отписал выше. Мне нас на него, как говорится. Я рад, что есть о чем поговорить )
|
|
Обновил(-а) dimarik 09.09.2010 в 23:30
|
09.09.2010 23:40 | |
Хахах) Ну тебе я всегда рад, заходи почаще )
|
10.09.2010 00:10 | |
А целыя индустрии тихо продолжают писать свои компиляторы. Што им какаято тигра )
|
10.09.2010 00:35 | |
Юмор за молодежью )
|
10.09.2010 12:17 | |
dimarik, тоже мне старикашка
|
11.09.2010 13:46 | |
dimarik, ну не знаю - когда меня ставят в женский род в любом контексте мне это не очень приятно)
|
10.10.2010 04:15 | |
Люди добрые-умные, а вот почему вы путаете бинарное с побитовым? =)
Вроде как, все вышеперечисленные операторы как раз побитовые (и тем не менее вполне себе логические). И кроме этого, не все они бинарные. "~" -- унарный оператор. Раз уже один раз решил отредактировать, то почему бы сразу правильно не написать? *выпендреж закончен, попытка повышения ЧСВ завершена* =D Первое, что приходит в голову про применение битов -- шифрование и сжатие данных. И быстрое умножение на степени двойки (правда как говорит один мой друг-с-программист -- "хороший компилятор это сделает за тебя". Хотя ас так высоко, что там разницы наверное и нет, надо будет проверить) Как уже говорили -- можно использовать как флаги, например при возврате нескольких кодов ошибок в одном числе. |
|
Обновил(-а) ChuwY 10.10.2010 в 04:35
|
05.12.2010 14:44 | |
Ну вот, и мне такое пригодилось. Удобная вешч.
|
06.12.2010 02:30 | |
Прочел статью. Заинтересовался. С битовыми операциями был знаком и раньше, но вот не совсем доганял как их практически использовать, за исключением всяких там N-мерных булевых массивов. В поисках дополнительной инфы нарыл ссылку, может кому интересно будет
http://sotomajor.org.ua/article/20/u...eb-programming |
16.12.2010 02:28 | |
А ещё 0 это нет электричества, а 1 это есть! Воооот
|
Последние записи от Psycho Tiger
- Тонкости и трюки ActionScript`а, которые... бесполезны (10.05.2011)
- Vkontakte: как пользоваться wall.post, нужен ли теперь wall.savePost? (05.03.2011)
- А пятый контер-страйк хорош. (19.01.2011)
- Пацаны, гоу Вконтакте? (21.12.2010)
- Давайте начистоту (18.12.2010)