Освой программирование играючи

Сайт Александра Климова

Шкодим

/* Моя кошка замечательно разбирается в программировании. Стоит мне объяснить проблему ей - и все становится ясно. */
John Robbins, Debugging Applications, Microsoft Press, 2000

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

Существует несколько побитовых операторов, применимых к целочисленными типам long, int, short, char, byte.

~Побитовый унарный оператор NOT
&Побитовый AND
&=Побитовый AND с присваиванием
|Побитовый OR
|=Побитовый OR с присваиванием
^Побитовый исключающее OR
^=Побитовый исключающее OR с присваиванием
>>Сдвиг вправо
>>=Сдвиг вправо с присваиванием
>>>Сдвиг вправо с заполнением нулями
<<Сдвиг влево
<<=Сдвиг влево с присваиванием
>>>=Сдвиг вправо с заполнением нулями с присваиванием

Все целочисленные типы представляются двоичными числами различной длины. Например, значение типа byte, равное 42, в двоичном представлении имеет вид 00101010, в котором каждая позиция представляет степень числа два.

Все целочисленные типа, за исключением char - типы со знаком, т.е. могут быть положительными или отрицательными. В Java применяется двоичное дополнение, при котором отрицательные числа представляются в результате инвертирования всех битов значения (изменения 1 на 0 и наоборот) и последующего добавления 1 к результату. Например, -42 представляется в результате инвертирования всех битов в двоичном представлении числа 42, что даёт значение 11010101, и добавления 1, что приводит к значению 110110110, или -42. Чтобы декодировать отрицательное число, необходимо вначале инвертировать все биты, а затем добавить 1 к результату. Например, инвертирование значения -42, или 11010110, приводит к значению 00101001, или 41, после добавления 1 к которому мы получим 42.

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

Побитовые логические операторы

Побитовые логические операторы - это &, |, ^, ~. Побитовые операторы применяются к каждому отдельному биту каждого операнда.

Результаты выполнения побитовых логических операторов

ABA | BA & BA ^ B~A
000001
101010
011011
111100

Побитовое OR (|)

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

  00101010  42
| 00001111  15
--------------
  00101111  47 

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

Значение бита, полученное в результате выполнения побитового оператора AND, &, равно 1, если соответствующие биты в операндах также равны 1. Во всех остальных случаях значение результирующего бита равно 0.

  00101010  42
& 00001111  15
--------------
  00001010  10

Побитовое XOR (^)

Результирующий бит, полученный в результате выполнения оператора XOR, ^, равен 1, если соответствующий бит только в одном из операндов равен 1. Во всех других случаях результирующий бит равен 0.

  00101010  42
^ 00001111  15
--------------
  00100101  37  

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


int x = 5, y = 7;

x = x ^ y; // стало 2
System.out.println(x);
y = x ^ y; // стало 5
System.out.println(y);
x = x ^ y; //стало 7
System.out.println(x);

Но увлекаться такой записью не стоит, это работает медленнее и код менее читаем.

Гораздо шире используется XOR для шифрования. В простейшем виде это выглядит так. Есть текст, к которому применяется ключ с оператором XOR. Зашифрованное сообщение передаётся человеку, который знает ключ. Всё, что ему нужно сделать - это применить к зашифрованному тексту тот же ключ, используемый для шифровки и текст снова станет читаемым.

Ниже приводится приблизительный пример работы шифровки/дешифровки текста. С русским текстом пример не будет работать, так как используются разные кодировки и требуется писать дополнительный код. Итак, у нас есть некий текст, который мы зашифровали с помощью ключа (meow) и передали полученный набор байтов другому человеку. Если кто-то перехватит ваше сообщение, то увидит просто набор символов. А ваш сообщник сможет прочитать сообщение, так как вы заранее условились, каким будем ключ для расшифровки.


public void onClick(View view) {

	String message = "OK, i love you"; // секретное сообщение
	String catkey = "meow"; // ключ

	// зашифруем послание
	byte[] important = encode(message, catkey);
	// посмотрим на результат
	mInfoTextView.setText(new String(important));

	// теперь расшифруем текст
	mResultEditText.setText(decode(mInfoTextView.getText().toString().getBytes(),
			catkey));
	
}

// метод для шифровки текста с помощью XOR
public static byte[] encode(String secret, String key) {
	byte[] btxt = null;
	byte[] bkey = null;

	btxt = secret.getBytes();
	bkey = key.getBytes();

	byte[] result = new byte[secret.length()];

	for (int i = 0; i < btxt.length; i++) {
		result[i] = (byte) (btxt[i] ^ bkey[i % bkey.length]);
	}
	return result;
}

// метод для расшифровки текста
public static String decode(byte[] secret, String key) {
	byte[] result = new byte[secret.length];
	byte[] bkey = key.getBytes();

	for (int i = 0; i < secret.length; i++) {
		result[i] = (byte) (secret[i] ^ bkey[i % bkey.length]);
	}
	return new String(result);
}

Побитовое NOT (~)

Унарный оператор NOT (Не), ~, называемый также побитовым дополнением, инвертирует все биты операнда. Например, число 42 в битовом представлении имеет вид:

00101010

В результате применения оператора NOT преобразуется в значение:

11010101

Сдвиг влево

Оператор сдвига влево, <<, смещает все биты влево на указанное количество позиций:

значение << количество

Параметр количество указывает, на сколько нужно сдвинуть влево биты в параметре значение. При каждом сдвиге влево самый старший бит смещается за пределы допустимого значения и теряется, а справа дописывается нуль. Это означает, что при применении оператора сдвига влево к операнду типа int биты теряются, как только они сдвигаются за пределы 31 позиции. Если операнд имеет тип long, биты теряются после сдвига за пределы 63 позиции.

Автоматическое повышение типа, используемое в Java, может привести к странным результатам при выполнении сдвига в значениях типа byte, short. При вычислении выражений тип значений byte и short повышается до типа int. Это означает, что результатом выполнения сдвига влево значения типа byte или short будет значение int, и сдвинутые влево позиции не будут отброшены до тех пор, пока они не будут сдвинуты за пределы 31 позиции. Более того, при повышении до типа int отрицательное значение типа byte или short получит дополнительный знаковый разряд. Следовательно, старшие биты будут заполнены единицами. Поэтому выполнение оператора сдвига влево предполагает необходимость отбрасывания старших байтов результата типа int. Иными словами, при выполнении сдвига влево в значении типа byte сначала будет повышение до типа int и лишь затем сдвиг. Это означает, что для получения требуемого сдвинутого значения типа byte необходимо отбросить три старших байта результата. Простейший способ достижения этого - обратное приведение результата к типу byte.


byte x = 64;
byte y;
int i;

i = x << 2; // сдвиг влево
y = (byte) (x << 2); // сдвиг влево с приведением


mInfoTextView.append("i равно: " + i + "\n");
mInfoTextView.append("y равно: " + y);

Результат будет следующим:

i равно: 256
y равно: 0

Поскольку для выполнения вычислений тип переменной повышается до int, сдвиг влево на две позиции значение 64 (0100 0000) приводит к значению 256 (1 0000 0000). Однако, переменная y содержит значение не 256, а 0, поскольку после сдвига крайний единичный бит оказывается сдвинутым за пределы допустимого диапазона.

Приёмом сдвига влево часто пользуются в программах, где происходит много сложных вычислений. По сути, это замена операции умножения на 2, которая в силу особенностей процессора гораздо эффективнее. При этом следует соблюдать осторожность, так как при сдвиге единичного бита в старшую позицию (бит 31 или 63) значение становится отрицательным.

Сдвиг вправо

Оператор сдвига вправо, >>, смещает все биты значения вправо на указанное количество позиций:

значение >> количество

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


int a = 32;
a = a >> 2 // стало равным 8

Крайние биты при сдвиге просто теряются. Например, значение 35 при сдвиге вправо на две позиции также приводит к значению 8, так как теряются два младщих бита.

  00100011  35
>>2
----------
  00001000  8

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

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

Обратите внимание, что результат сдвига вправо значения -1 всегда равен -1, поскольку дополнительные знаковые разряды добавляют новые единицы к старшим битам.

Иногда при выполнении сдвига вправо появление дополнительных знаковых разрядов нежелательно. В этом случае используется маскировка за счёт объединения значения со значением 0x0f оператором AND, что приводит к отбрасыванию любых битов дополнительных знаковых разрядов.

Сдвиг вправо без учёта знака

Как было показано выше, при каждом выполнении оператор >> автоматически заполняет старший бит его предыдущим содержимым. В результате знак значения сохраняется. Однако иногда это нежелательно. Например, при работе со значениями пикселей и графическими изображениями. Как правило, в этих случаях требуется сдвиг нуля в позицию старшего бита независимо от его первоначального значения. Такое действие называют сдвигом вправо без учета знака, когда всегда вставляется нуль в позицию старшего бита.

Допустим, мы хотим сдвинуть вправо на 24 бит значение -1 (в двоичном представлении 11111111 11111111 11111111 11111111):

    11111111 11111111 11111111 11111111
>>> 24
---------------------------------------
    00000000 00000000 00000000 11111111 255 в двоичном виде типа int

Оператор >>> не столь полезен, поскольку имеет смысл только для 32- и 64-разрядных значений.

Побитовые составные операторы с присваиванием

Двоичные побитовые операторы имеют составную форму, которая объединяет побитовый оператор с оператором присваивания.


a = a >> 4;
a >>= 4;

a = a | b;
a |= b;
Реклама