Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Побитовые операции и операции битового сдвига в Java и не только

Anna | 5.06.2014 | нет комментариев
Целью статьи является показать вероятности утилитарного использования побитовых операций.

Побитовые операции пременяются для стремительного выполнения вычислений и меньшего потребления источников, связанных с этими вычислениями.В Java существуют следующие виды побитовых операций:

| ЛИБО (OR)
& И (AND)
^ ИСКЛЮЧАЮЩЕЕ ЛИБО (XOR)
~ ОТРИЦАНИЕ (NOT)

Так же стоит выделить операции битового сдвига:

<< сдвиг налево
>> сдвиг вправо
>>> беззнаковый сдвиг вправо

Побитовые операции

Используются к всякой паре битов, которые стоят в идентичных позициях в 2-х битовых последовательностях.

Побитовое ЛИБО (OR)

Оператор обозначается символом |

Выставляет значение в 1, если установлен соответствующий бит в первой либо во 2-й последовательности, либо совместно

00000000 00000000 00000000 01111011 (123)
|
00000000 00000000 00000001 11001000 (456)
=
00000000 00000000 00000001 11111011 (507)

Побитовое И (AND)

Обозначается символом &

Выставляет значение в 1, если установлены соответствующие биты в первой и 2-й последовательности единовременно

00000000 00000000 00000000 01111011 (123)
&
00000000 00000000 00000001 11001000 (456)
=
00000000 00000000 00000000 01001000 (57)

ИСКЛЮЧАЮЩЕЕ ЛИБО (XOR)

Обозначается символом ^

Выставляет значение в 1, если установлен соответствующий бит либо в первой либо во 2-й во 2-й последовательности, но не единовременно.

Если применяется больше 2-х последовательностей, то в итоге будет единица тогда, когда всеобщее число единиц соответствующей позиции нечетное.

00000000 00000000 00000000 01111011 (123)
^
00000000 00000000 00000001 11001000 (456)
=
00000000 00000000 00000001 10110011 (435)

ПОБИТОВОЕ ОТРИЦАНИЕ (NOT)

Обозначается символом ~

Унарный оператор, т.е. используется к одной последовательности. Трансформирует всякий бит в противоположный.

~
00000000 00000000 00000000 01111011 (123)
=
11111111 11111111 11111111 10000100 (-124)

Знаковый оператор сдвига налево <<

Все биты смещаются налево. Число справа дополняется нулем. Операция применяется для стремительного умножения на 2. Если оператор используется к числу, умножение на 2 которого будет огромнее максимального значения int (2147483647), то в итоге будет негативное число. Это происходит потому, что краний левый бит, тот, что отвечает за знак числа, выставляется в единицу, что соответствует негативным числам.

11111111 11111111 11111111 10000101 (-123)
<<
11111111 11111111 11111111 00001010 (-246)

Знаковый оператор сдвига вправо >>

Все биты смещаются вправо. Число слева дополняется нулем, если число правильное и единицей, если негативное. Операция применяется для стремительного деления на 2. Если делится нечетное число, то остаток отбрасывается для позитивных чисел и сохраняется для негативных.

11111111 11111111 11111111 10000101 (-123)
>>
11111111 11111111 11111111 11000010 (-62)

Беззнаковый оператор сдвига >>> 

Все биты смещаются вправо, число слева дополняется нулем, даже если операция выполняется с негативными числами. Отсель и наименование оператора — беззнаковый. В итоге использования оператора неизменно получается позитивное число, т.к. в Java левый бит отвечает за знак числа. Операция так же, как и знаковый оператор сдвига вправо, соответствует делению числа на два за исключением первого сдвига в отрицительном числе.

11111111 11111111 11111111 10000101 (-123)
>>>
01111111 11111111 11111111 11000010 (2147483586)

Использование на практике

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

Когда число сдвигов превышает число разрядов

При применении битовых сдвигов значимо помнить, что когда число сдвигов достигает числа разрядов, дальнейший сдвиг вернет значение в начальное расположение. Скажем, сдвиг налево:

0 -  00000000000000000000000001111011 (123)
1 -  00000000000000000000000011110110 (246)
...
30 - 11000000000000000000000000000000 (-1073741824)
31 - 10000000000000000000000000000000 (-2147483648)
32 - 00000000000000000000000001111011 (123)

Так же имеет толк подметить, что позже 31-го сдвига нет позиции, где все нули.

Приведение чисел к соответствующему типу данных

При применении побитовых операций с типами данных byte/short, числа вначале приводятся к типу int, а если одно из чисел — long, то к long.

int i = Integer.MAX_VALUE; //1111111111111111111111111111111
long l = Long.MAX_VALUE; //111111111111111111111111111111111111111111111111111111111111111
long r1 = i&l;
long r2 = l&l;

//r1 - 000000000000000000000000000000001111111111111111111111111111111 (2147483647)
//r2 - 111111111111111111111111111111111111111111111111111111111111111 (9223372036854775807)

При сужении типа данных, левая часть битов легко отбрасывается, скажем:

long l1 = -9223372032559808513L;
int i1 = (int) l1; //2147483647

l1 - 1000000000000000000000000000000011111111111111111111111111111111
r1 - 11111111111111111111111111111111

Применение маски

Одним из приемов работы с битовыми данными является применение маски. Маска разрешает получать значения только определенных битов в последовательности. Скажем, у нас есть маска 00100100, она разрешает нам получать из последовательности только те биты, которые в ней установлены. В данном случае это 3-й и 7-й разряд. Для этого довольно исполнить побитовое И с нашей маской и некоторым числом:

01010101
&
00100100
=
00000100

Битовая маска применяется, скажем, при определении маски подсети в сетевой адресации.

Хранение в одной целочисленной переменной нескольких значений

При помощи битовых сдвигов дозволено беречь в одной целочисленной переменной несколько значений меньшей длины. Скажем, в первых нескольких битах дозволено беречь одно число, в следующих битах — другое. Требуется только знать, на сколько бит выполняется сдвиг и сколько бит занимает хранимое число. Для записи применяется логическое ЛИБО, для приобретения — И.

В дальнейшем примере в одном числе сохраняются три значения — возраст, рост, вес, а после этого считываются из него. Недостатком такой системы является надобность помнить, что хранимые значения не обязаны превышать число бит, которые определены для них. Скажем, если в примере одно из значений будет превышать число 255, то мы получим ложный итог.

int age, height, weight, combined, mask;
age = 28; //00011100
height = 185; //10111001
weight = 80; //01010000
combined = (age) | (height << 8) | (weight << 16); //00000000 01010000 10111001 00011100

mask = 0b11111111;

System.out.printf("Age: %d, height: %d, weight: %d", 
        mask & combined, 
        mask & combined >>> 8, 
        mask & combined >>> 16);
//Age: 28, height: 185, weight: 80

Работа с правами доступа

Еще один рапространенный пример использования побитовых операций — работа с правами доступа к папкам и файлам. Правило дальнейший. Имеется последовательность из 3 битов, где:
001 — 1-й бит отвечает за права на выполнение
010 — 2-й — запись
100 — 3-й — чтение

Имеем следующие константы.

final int EXECUTE = 1; //001
final int WRITE = 2; //010
final int READ = 4; //100

Возможен, нам требуется дать пользователю полный доступ к источнику. Для этого должен быть выставлен всякий бит:

int usersAccess = EXECUTE | WRITE | READ; //Получили значение 7 (111)

А сейчас, возможен, что нам нужно забрать у пользователя права на выполнение:

usersAccess = usersAccess ^ EXECUTE //Получили значение 6 (110)

Обмен переменных местами без применения временной переменной

Исключающее ЛИБО может быть использовано для обмена 2-х переменных без создания временной переменной:

void xorSwap(int x, int y) {
 x = x^y;
 y = y^x;
 x = x^y;
}

Правда, в реальной жизни метод с временной переменной работает стремительней. Данный пример приведен только в познавательных целях.

Шифр Вернама

На основе иключающего ЛИБО работает шифр Вернама, для которого была подтверждена безусловная криптографическая стойкость. Шифр был «взломан» в фильме «Пароль «Рыба-меч»»

Стремительное умножение и деление

Операции сдвига рекомендуют применять для стремительного умножения и деления целых чисел на числа, равные степени двойки. Скажем, выражение 3 << 4 соответствует умножению тройки на 2 в 4-й степени.

Хранение списка булевых значений и манипуляция ими

Побитовое ЛИБО может быть использовано для установки в 1 нужных позиций битов в последовательности. Это разрешает, скажем, беречь список булевых значений в максимально сжатом виде

С поддержкой исключающего ЛИБО дозволено переключать заданные биты на противоположные, что разрешает манипулировать комплектом булевых значений.

Как проверить, является ли число степенью двойки?

С поддержкой побитовых операций дозволено за константное время проверить, является ли число степенью двойки:

(x & (x-1)) == 0

Данное выражение работает для всех чисел, помимо 0, а 0 не является степенью двойки. Следственно финальный вариант должен выглядеть так:

(x != 0) && ((x & (x-1)) == 0)

Как это работает:
В числе 2 в степени n в единицу выставлен только (n 1)-й бит. Все остальные — нули. Скажем, числа 16 и 32 имеют двоичный вид, соответственно, 10000 и 100000. Т.е. нам нужно проверить, что в числе выставлен только один бит.
Возможен, число k — два в степени n. В числе k в единицу выставлен (n 1)-й бит. Тогда в числе k-1 в единицу будут выставлены все биты от 1 до n. Если с такими числами исполнить побитовое ЛИБО, то в итоге должен получиться 0. Скажем:

32 & 31 == 0 //true

100000
&
011111
=
000000

Итог

Итог примитивный. Программист должен знать побитовые операции и уметь ими пользоваться. Это в некоторых случаях может упростить ему жизнь.

Вот еще много примеров использования побитовых операций:
Bit Twiddling Hacks
The Aggregate Magic Algorithms
All The Twiddled Bits
Code for the Algorithms in Hacker’s Delight book

Ну и домашнее задание напоследок. Отчего в HashMap в Java для определения индекса применяется логическое И?

static int indexFor(int h, int length) {
    return h & (length-1);
}

Использованная письменность:

Bitwise and Bit Shift Operators
Битовые операции в PHP на примерах
Алгорифм обмена при помощи исключающего ЛИБО
Битовые сдвиги и приведения в Java: подводные камни
Битовая маска
Bitwise operation
How to check if a number is a power of 2

 

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB