Bitwise and Bit Shift Operators
The Java programming language also provides operators that perform bitwise and bit shift operations on integral types. The operators discussed in this section are less commonly used. Therefore, their coverage is brief; the intent is to simply make you aware that these operators exist.
The unary bitwise complement operator "
" inverts a bit pattern; it can be applied to any of the integral types, making every "0" a "1" and every "1" a "0". For example, a byte contains 8 bits; applying this operator to a value whose bit pattern is "00000000" would change its pattern to "11111111".
The signed left shift operator " << " shifts a bit pattern to the left, and the signed right shift operator " >> " shifts a bit pattern to the right. The bit pattern is given by the left-hand operand, and the number of positions to shift by the right-hand operand. The unsigned right shift operator " >>> " shifts a zero into the leftmost position, while the leftmost position after ">>" depends on sign extension.
The bitwise & operator performs a bitwise AND operation.
The bitwise ^ operator performs a bitwise exclusive OR operation.
The bitwise | operator performs a bitwise inclusive OR operation.
The following program, BitDemo , uses the bitwise AND operator to print the number "2" to standard output.
Побитовые операции в Java
342 Но так как переменная типа int занимает 4 байта, т.е. 32 бита, на самом деле число в переменной хранится как: 00000000 00000000 00000001 01010110 — число 342 в переменной типа int в java 11111111 11111111 11111110 10101001 — результат выражения
& — побитовый оператор “И”
- | — побитовое “ИЛИ”. Принцип работы тот же — сравниваем два числа по битам. Только теперь если хотя бы один из битов равен 1, результат будет равен 1. Посмотрим на тех же числах — 277 и 432:
- ^ — побитовое исключающее “ИЛИ” (также известно как XOR)
Сдвиг влево
Сдвиг битов влево обозначается знаком << Пример: В этом примере число x=64 называется значением. Именно его биты мы будем сдвигать. Сдвигать биты мы будем влево (это можно определить по направлению знака << ) В двоичной системе число 64 = 1000000 Число y=3 называется количеством. Количество отвечает на вопрос “на сколько бит вправо/влево нужно сдвинуть биты числа x ” В нашем примере мы будем сдвигать их на 3 бита влево. Чтобы процесс сдвига был более понятен, посмотрим на картинке. У нас в примере используются числа типа int. Int ’ы занимают в памяти компьютера 32 бита. Вот так выглядит наше изначальное число 64: 
А теперь мы, в прямом смысле слова, берем каждый из наших битов и сдвигаем влево на 3 ячейки: 
Вот что у нас получилось. Как видишь, все наши биты сдвинулись, а из-за пределов диапазона добавились еще 3 нуля. 3 — потому что мы делали сдвиг на 3. Если бы мы сдвигали на 10, добавилось бы 10 нулей. Таким образом, выражение x << y означает “сдвинуть биты числа х на y ячеек влево”. Результатом нашего выражения стало число 1000000000, которое в десятичной системе равно 512. Проверим: Вывод в консоль: Все верно! Теоретически, биты можно сдвигать до бесконечности. Но поскольку у нас число int , в распоряжении есть всего 32 ячейки. Из них 7 уже заняты числом 64 (1000000). Поэтому если мы сделаем, например, 27 сдвигов влево, наша единственная единица выйдет за пределы диапазона и “затрётся”. Останутся только нули! Вывод в консоль: Как мы и предполагали, единичка вышла за пределы 32 ячеек-битов и исчезла. У нас получилось 32-битное число, состоящее из одних нулей. 
Естественно, в десятичной системе ему соответствует 0. Простое правило для запоминания сдвигов влево: При каждом сдвиге влево выполняется умножение числа на 2. Например, попробуем без картинок с битами посчитать результат выражения 111111111 << 3 Нам нужно трижды умножить число 111111111 на 2. В результате у нас получается 888888888. Давай напишем код и проверим: Вывод в консоль:
Сдвиги вправо
Они обозначаются знаком >> . Делают то же самое, только в другую сторону! 🙂 Не будем изобретать велосипед и попробуем сделать это с тем же числом int 64. 
В результате сдвига на 2 вправо два крайних нуля нашего числа вышли за пределы диапазона и затерлись. У нас получилось число 10000, которому в десятичной системе соответствует число 16 Вывод в консоль: Простое правило для запоминания сдвигов вправо: При каждом сдвиге вправо выполняется деление на два с отбрасыванием любого остатка. Например, 35 >> 2 означает, что нам нужно 2 раза разделить 35 на 2, отбрасывая остатки 35/2 = 17 (отбросили остаток 1) 17:2 = 8 (отбросили остаток 1) Итого, 35 >> 2 должно быть равно 8. Проверяем: Вывод в консоль: 
Побитовая арифметика в Java
Редко, но все же задачки из собеседований и обучалок имеют практическую ценность. Так, мне понадобилось реализовать на Java альтернативу арифметическим операциям над целочисленными значениями. Благо, первые страницы поисковиков пестрят готовыми решениями побитовых аналогов, и над большинством из них голову ломать не пришлось.
Признаться, я был несколько удивлен отсутствию такого материала на Хабре (плохо искал?), потому и решил восполнить этот недостаток, со своими комментариями и дополнениями.
Прошу учесть, что в примерах с побитовыми операциями значения урезаны до полубайта: фундаментальной разницы не будет, а воспринимается легче.
Сложение
Для начала надо вспомнить о переносе в старший разряд. В десятичной системе под его определение (для текущего разряда) подпадают значения в диапазоне от 10 до 18:
В двоичной же системе переносится все, что больше единицы:
В последнем примере первыми складываются самые младшие биты:
Ноль остается в текущем разряде, а единица переходит в старший, где участвует в сложении:
младшая единица остается в текущем, старшая сдвигается дальше. Отсюда же можно вывести правило, что в двоичной системе для одного текущего разряда под перенос подпадают значения от двух до трех включительно.
В части, касающейся алгоритма, стоит обратить внимание на инструкцию определения наличия/отсутствия переноса на примере предыдущих значений:
Это еще не перенос, но выставление «флагов» над разрядами, сложение которых оставляет перенос, т.е. перенос при сложении — это когда биты одинаковые.
Коль скоро уже что-то да прояснилось, то теперь первое слагаемое должно быть освобождено от битов, по которым перенос учтен:
Как известно, побитовый оператор «Исключающее ИЛИ» выставит биты только если значения разрядов противоположны.
Третий шаг цикла — это преобразование «флагов» наличия переноса непосредственно в перенос. Для этого они сдвигаются на один шаг влево и присваиваются второму слагаемому:
На последующей итерации перенос зафиксирован не будет, т.к:
Второй шаг даст нам:
Что является искомой суммой, а третий шаг завершит цикл while():
Вычитание
Эквивалентен предыдущему с той лишь разницей, что заем битов у старших разрядов реализован инверсия обратной импликации. Ну и переименовываем локальные переменные.
Умножение
Вернемся к истокам: умножение в столбик в десятичной системе:
т.е. мы перемножаем каждый разряд второго множителя с первым множителем. Отсюда же следует, что произведение от старшего разряда сдвигается на один шаг влево. И наконец складываем промежуточные значения. То же самое происходит на побитовом уровне:
Делаем вывод, что алгоритм только и должен, что складывать первый множитель с самим собою всякий раз как во втором множителе встречается установленный бит, естественно, с учетом правила перевода в старший разряд:
Дальше осуществляется сдвиг первого множителя на один разряд влево (формируем «лесенку»):
Теперь определяем, есть ли бит во втором по значимости разряде второго множителя:
Цикл работает до тех пор, пока второй множитель не равен нулю. Хотел бы обратить внимание на следующее: от ресурса к ресурсу гуляет экземпляр этого алгоритма, где логический сдвиг второго множителя (mul2 >>>= 1) заменен на арифметический (mul2 >>= 1). Вероятно, он берет свое начало из реализации на C/C++, где есть ключевое слово unsigned и такая подмена не является проблемой. Однако в Java все типы чисел знаковые и если второй множитель будет представлен отрицательным значением, то такая оплошность приведет к вываливанию алгоритма в бесконечный цикл, т.к. второй множитель всегда будет отвечать его условию:
Деление
С делением вышло не так гладко, как с предыдущими примерами: пришлось писать велосипед (сильно не бить).
Деление — это вычитание делителя от делимого до тех пор, пока частное больше или равно нулю. При таком подходе достаточно определить счетчик, значение которого инкрементируется после каждой операции вычитания. Его итоговое значение и есть частное:
Недостаток такого подхода становится особенно ощутимым при подаче устройству с ограниченными ресурсами последовательности из инструкций, как то: 2147483647 / 1; 2147483647 / 2; 2147483647 / 3, сложится впечатление, что приложение зависло.
Куда эффективней была бы работа на уровне битов. Но единственное найденное решение имеет тот недостаток, что для корректного вывода требуется тип переменных, на ступень выше охватываемого диапазона, т.е. если на вход подаете short, то тип локальных переменных должен быть int, иначе результат деления больших значений будет удивлять. В моем случае ситуация усугублялась отсутствием типа long.
Но вернемся к нашим баранам.
Для понимания принципа работы алгоритма необходимо вспомнить порядок деления столбиком:
Вот тут по-подробней. На выхлопе у нас получилось следующее: мы «вытолкнули» делитель влево до того разряда, где он минимизировал разность с делимым:
Этот механизм реализован в алгоритме. В цикле while() делитель должен сдвигаться влево до тех пор, пока не будет удовлетворять вышеописанному правилу. Параллельно с ним сдвигается маска частного. Оператор ветвления if() гласит: «сдвинуть можно если только результат этой операции не нарушит основное правило». Дополнительная проверка на отрицательное число связана с тем, что в Java выставленный самый старший бит – это отрицательное число. Без него цикл упадет в бесконечность:
Как только алгоритм перестал отвечать условиям if(), код входит в else, где на частном устанавливается бит маски:
Это аналогично выставлению битов при делении столбиком. Затем от делимого вычитается делитель:
После этого делитель и маска возвращаются в исходное состояние и цикл начинается вновь:
Напоследок хотел бы добавить несколько слов о дополнительном коде.
Приведенный алгоритм предполагает деление только положительных чисел, которые получены дополнительным кодом:
Тут происходит следующее: если число отрицательное, то его биты инвертируются, а результат складывается с единицей и получаем положительное (абсолютное) значение. Это же правило действительно для положительных чисел, например:
Но есть одно исключение — это максимально большое отрицательное число заданного типа, например:
Побитовые операции в Java
Бит — это то, на чем строится работа каждого компьютера. Перед тем как объяснить в чем же заключается работа с битами в Java, немного истории!
Жил был такой ученый Готфрид Вильгельм Лейбниц.
Может кто-то знает его за многочисленные заслуги в математике и не только:
- создание математического анализа — дифференциальное и интегральное исчисления;
- создал комбинаторику как науку;
- заложил основы математической логики;
- в физике сформулировал закон сохранения энергии;
- в психологии развил учение о бессознательной психической жизни;
- и именно он описал двоичную систему счисления с цифрами 0 и 1.
Одним словом — был серьезным ученым. И вот в 1703 году он описал двоичную систему исчисления с цифрами 0 и 1. В своей работе он упоминал, что двоичная система исчисления существовала в Китае много-много лет до того как он взялся за ее изучение. Она была описана великим Китайским императором и философом по имени Fu Xi (Фу Си), который жил еще более, чем за 4000 лет до Лейбница.
Китайский император описывал Инь и Ян как инь-ян («0«-«1«), китайский двоичный разряд, китайский бит. Другими словами можно сделать вывод, что двоичная система исчисления за долго до компьютеров уже имела огромную силу и большую историю!
Сегодня представление и обработка любой информации в компьютере представлена в виде двоичной системы исчислений. Сам бит — это единица измерения информации, 1 или 0 , да или нет .
Всем известна Дездемона из пьесы Уильяма Шекспира «Отелло«. И на вопрос «Молилась ли ты на ночь Дездемона?«, она могла бы ответить вот таким способом:
Тоесть, 1 это ДА, а 0 это НЕТ!
Любое число можно перевести в последовательность Битов!
Например:
- число 0 — (представление в битах) 0 0
- число 1 — (представление в битах) 0 1
- число 2 — (представление в битах) 1 0
- число 3 — (представление в битах) 1 1
- число 4 — (представление в битах) 1 0 0
- число 5 — (представление в битах) 1 0 1
- число 6 — (представление в битах) 1 1 0
- число 7 — (представление в битах) 1 1 1
- число 8 — (представление в битах) 1 0 0 0
- число 9 — (представление в битах) 1 0 0 1
- число 10 — (представление в битах) 1 0 1 0
- число 15 — (представление в битах) 1 1 1 1
- число 20 — (представление в битах) 1 0 1 0 0
- число 25 — (представление в битах) 1 1 0 0 1
- число 31 — (представление в битах) 1 1 1 1 1
Компьютер хранит в своей памяти таким образом любые символы (цифры, буквы, знаки препинания и т.д.) и для этого использует определенное количество бит. Компьютер распознает 256 (от 0 до 255) различных символов по их коду, чтобы вместить все цифры, буквы и много других символов.
Для представления символа с максимальным кодом, то есть 255 — нужно 8 бит. Эти 8 бит называются байтом. Один любой символ — это всегда 1 байт.
Но вернемся к Java!
— Что можно делать с битами с помощью языка программирования Java?
— Побитовые операции!
Побитовые операции в Java можно проводить только над целочисленными типами данных. То есть long, int, short, char, byte.
Разница в работе с целочисленными значениями только в том сколько они хранят в себе диапазон допустимых значений.