В Java есть операторы сдвига. Операторы << и >> позаимствованы из С/C++. Кроме того, Java обладает своим новым оператором сдвига >>>.
Операторы сдвига присущи системам, которые могут выравнивать биты, прочтённые из IO портов или зартсываемые в IO порты. Это также быстрое умножение или деление на степень двойки. Преимущество операторов сдвига в Java - это независимость от платформы. Поэтому вы можете использовать их не беспокоясь ни о чём.
Основы сдвига
Сдвиг - это, по сути, простейшая операция: мы берём последовательность битов и двигаем её влево или вправо. Больше всего конфуза вызывает оператор >>>. Но о нём мы поговорим чуть позже.
Операторы сдвига могут применяться лишь к целым числам, то есть к типам int или long. Следующая таблица иллюстрирует базовый механизм сдвига.
Исходные данные | 192 | |||||
Бинарное представление | 00000000 | 00000000 | 00000000 | 11000000 | ||
Сдвиг влево на 1 бит | 0 | 00000000 | 00000000 | 00000001 | 1000000? | |
Сдвиг вправо на бит | ?0000000 | 00000000 | 00000000 | 01100000 | 0 | |
Сдвиг влево на 4 бита | 0000 | 00000000 | 00000000 | 00001100 | 0000???? | |
Исходные данные | -192 | |||||
Бинарное представление | 11111111 | 11111111 | 11111111 | 01000000 | ||
Сдвиг влево на 1 бит | 1 | 11111111 | 11111111 | 11111110 | 1000000? | |
Сдвиг вправо на бит | ?1111111 | 11111111 | 11111111 | 10100000 | 0 |
Таблица показывает фундаментальную идею сдвига: перемещение битов относительно их позиций. Это как очередь в магазине: как только один человек совершил покупку и отшёл, вся очередь сдвинулась и позиции всех участников очереди изменились.
Однако, глядя на таблицу, возникают три вопроса вопроса:
- Что происходит, если мы сдвигаем влево и при этом часть бинарной записи выходит за границу слева, а часть - остаётся пустой справа?
- Что происходит, когда справа - выход за границы, а слева - пустое место?
- Какое истинное значение принимает знак "?"?.
Ответим на часть этих вопросов. Биты, вышедшие за границы, просто теряются. Мы о них забываем.
В некоторых языках, типа ассемблер, есть операция ротации, когда при сдвиге вышедшие за границы биты не теряются, но ставятся на освободившееся место (вместо вопросиков). Однако языки высокого уровня, типа Java, не имеют в своём арсенале такой операции.
Сдвиг отрицательных чисел
Ответ на вопрос о значении символов "?" в приведенной выше таблице требует отдельного рассмотрения.
В случае сдвига влево << и беззнакового сдвига вправо >>> новые биты просто устанавливаются в ноль. В случае сдвига вправо со знаком >> новые биты принимают значение старшего (самого левого) бита перед сдвигом. Следующая таблица демонстрирует это:
Исходные данные | 192 | |||
Бинарное представление | 00000000 | 00000000 | 00000000 | 11000000 |
Сдвиг вправо на 1 бит | 00000000 | 00000000 | 00000000 | 01100000 |
Сдвиг вправо на 7 бит | 00000000 | 00000000 | 00000000 | 00000001 |
Исходные данные | -192 | |||
Бинарное представление | 11111111 | 11111111 | 11111111 | 01000000 |
Сдвиг вправо на 1 бит | 11111111 | 11111111 | 11111111 | 10100000 |
Сдвиг вправо на 7 бит | 11111111 | 11111111 | 11111111 | 11111110 |
Заметьте: в том, случае, где старший бит был 0 перед сдвигом, новые биты стали тоже 0. Там где старший бит перед сдвигом был 1, новые биты тоже заполнились 1.
Это правило может показаться странным на первый взгляд. Но оно имеет под собой очень серьёзное обоснование. Если мы сдвигаем бинарное число влево на одну позицию, то в десятичной записи мы умножаем его на два. Если мы сдвигаем влево на n позиций, то умножение происходит на 2n, то есть на 2, 4, 8, 16 и т.д.
Сдвиг вправо даёт деление на степени двойки. При этом, добавление слева нулей на появившиеся биты на самом деле даёт деление на степени двойки лишь в случае положительных чисел. Но для отрицательных чисел всё совсем по другому!
Как известно, старший бит отрицательных чисел равен единице, 1. Для того, чтобы сохранить старшинство единицы при сдвиге, то есть сохранить отрицательный знак результата деления отрицательного числа на положительное (степень двойки), нам нужно подставлять единицы на освободившиеся места.
Если мы посмотрим на Таблицу 2, то заметим, что 192, сдвинутое на 1 бит вправо - это 192/2=96, а сдвинутое на 7 битов вправо - это 192/27=192/128=1 по законам целочисленной арифметики. С другой стороны, -192 сдвинутое на 1 бит вправо - это 192/2=-96 и т.д.
Таким образом, сдвиг вправо имеет две ипостаси: одна (>>>) просто сдвигает битовый паттерн "в лоб", а другая (>>) сохраняет эквивалентность с операцией деления на 2.
Сокращение (reduction) правого операнда
На самом деле у операторов сдвига есть правый операнд - число позиций, на которое нужно произвести сдвиг. Для корректного сдвига это число должно быть меньше, чем количество битов в результате сдвига. Если число типа int (long), то сдвиг не может быть сделан более, чем на 32 (64) бита.
Оператор же сдвига не делает никаких проверок данного условия и допускает операнды, его нарушающие. При этом правый операнд сокращается по модулю от нужного количества битов. Например, если вы захотите сдвинуть целое число на 33 бита, то сдвиг произойдёт на 33%32=1 бит. В результатае такого сдвига мы легко можем получить аномальные результаты, то есть результаты, которых мы не ожидали. Например, при сдвиге на 33 бита мы ожидаем получить 0 или -1 (в знаковой арифметике). Но это не так.
Почему Java сокращает правый операнд оператора сдвига или грустная история о заснувшем процессоре
Одной из главной причин введения сокращения было то, что процессоры сами сокращают подобным образом правый операнд оператора сдвига. Почему?
Несколько лет назад был создан мощнейший процессор с длинными регистрами и операциями ротации и сдвигам на любое количество битов. Именно потому, что регистры были длинными, корректное выполнение этих операций требовало несколько минут.
Основным применением данных процессоров был контроль систем реального времени. В данных системах самый быстрый ответ на внешнее событие должно занимать не более задержки на прерывание (interrupt latency). Отдельные инскрукции таких процессоров были неделимы. Поэтому выполнение длинных операций (сдвига на несколько бит и ротации) нарушало эффективную работу процессора.
Следующая версия процессора имплементировала эти операции уже по-другому: размер правого операнда сократился. Задержка на прерывание восстанавилась. И многие процессоры переняли данную практику.
Арифметическое распространение (promotion) операндов
Апифметическое распространение операндов происходит перед применением оперции сдвига и гарантирует, что операнды по крайней мере типа int. Это явление имеет особый эффект на беззнаковый сдвиг вправо, когда сдвигаемое число меньше, чем int: мы получаем не тот результат, который ожидали.
Следующая таблица показывает пример аномалии:
Исходные данные (-64 в десятичной записи) | 11000000 | |||
Распространение до int | 11111111 | 11111111 | 11111111 | 11000000 |
Сдвиг вправо на 4 битa | 00001111 | 11111111 | 11111111 | 11111100 |
Сокращение до байта | 11111100 | |||
Ожидаемый результат был | 00001100 |
3 комментария:
Исходя из "интонации", с которой написанно про невозможность сдвигать на количество бит больших чем разрядная сетка, можно сделать вывод, что автор считает это некоторым "связыванием рук" программисту.
Но вот объясните мне, где может потребоваться сдвиг более чем на разрядную сетку используемого типа данных? В этом же нет смысла. А вот деление правого оператора по модулю очень даже пользительная штуковина - создается цикличность. Даже если и возникнет задача в некоторых случаях сдвинуть так чтоб получился ноль, так можно сделать элементарную проверку правого операнда.
Мне понравилась ваша статья, спасибо, хорошо написано, интересно читать
Спасибо, интересная статья!
Отправить комментарий