Пусть число a = a3*23 + a2*22 + a1*21 + a0*20 , где значения ai – содержание соответствующих бит числа (то есть либо нули , либо единицы).
| a | a3 | a2 | a1 | a0 |
| m | 0 | 1 | 0 | 1 |
| a|m | a3 | 1 | a1 | 1 |
Видно, что независимо от начального значения в числе a в результате нулевой и второй бит установились в единицу. Таким образом, операцию OR с маской можно использовать для установки нужных бит переменной в единицу, если нужные биты маски установлены в единицу, а остальные – нули.
б) установка в числе a нужных бит в 0 с помощью маски m операцией a&m (арифметический, или, что то же, побитовый оператор AND):
| a | a3 | a2 | a1 | a0 |
| m | 0 | 1 | 0 | 1 |
| a&m | 0 | a2 | 0 | a0 |
Видно, что независимо от начального значения в числе a в результате первый и третий бит установились в нуль. Таким образом, операцию AND с маской можно использовать для установки нужных бит переменной в ноль, если нужные биты маски установлены в ноль, а остальные – единицы.
в) инверсия (замена единиц на нули, а нулей на единицы) в битах числа a , стоящих на задаваемых маской m местах, операцией a^m (арифметический, или, что то же, побитовый оператор XOR):
| a | 1 | 1 | 0 | 0 |
| m | 0 | 1 | 0 | 1 |
| a^m | 1 | 0 | 0 | 1 |
Видно, что если в бите, где маска m имеет единицу, у числа a происходит инверсия: если стоит 1, в результате будет 0, а если 0 – в результате будет 1. В остальных битах значение не меняется.
Восстановление первоначального значения после операции XOR – повторное XOR с той же битовой маской:
| a^m | 1 | 0 | 0 | 1 |
| m | 0 | 1 | 0 | 1 |
| (a^m)^m | 1 | 1 | 0 | 0 |
Видно, что содержание ячейки приняло то же значение, что было первоначально в ячейке a. Очевидно, что всегда (a ^ m) ^ m = a, так как повторная инверсия возвращает первоначальные значения в битах числа. Операция XOR часто используется в программировании для инверсии цветов частей экрана с сохранением в памяти только информации о маске. Повторное XOR с той же маской восстанавливает первоначальное изображение. - Имеется команда перевода вывода графики в режим XOR при рисовании, для этого используется команда graphics.setXORMode(цвет).
Ещё одна область, где часто используется эта операция – криптография.
Инверсия всех битов числа осуществляется с помощью побитового отрицания ~a.
Побитовые сдвиги “<<”, “>>” и “>>>” приводят к перемещению всех бит ячейки, к которой применяется оператор, на указанное число бит влево или вправо. Сначала рассмотрим действие операторов на положительные целые числа.
Побитовый сдвиг на n бит влево m<<n эквивалентен быстрому целочисленному умножению числа m на 2n. Младшие биты (находящиеся справа), освобождающиеся после сдвигов, заполняются нулями. Следует учитывать, что старшие биты (находящиеся слева), выходящие за пределы ячейки, теряются, как и при обычном целочисленном переполнении.
Побитовые сдвиги на n бит вправо m>>n или m>>>n эквивалентны быстрому целочисленному делению числа m на 2n. При этом для положительных m разницы между операторами “>>” и “>>>” нет.
Рассмотрим теперь операции побитовых сдвигов для отрицательных чисел m. Поскольку они хранятся в дополнительном коде, их действие нетривиально. Как и раньше, для простоты будем считать, что ячейки четырёхбитовые, хотя на деле побитовые операции проводятся только для ячеек типа int или long, то есть для 32-битных или 64-битных чисел.
Пусть m равно -1. В этом случае m=11112. Оператор m<<1 даст m=111102, но из-за четырёхбитности ячейки старший бит теряется, и мы получаем m=11102=-2. То есть также получается полная эквивалентность умножению m на 2n.
Иная ситуация возникает при побитовых сдвигах вправо. Оператор правого сдвига “>>” для положительных чисел заполняет освободившиеся биты нулями, а для отрицательных – единицами. Легко заметить, что этот оператор эквивалентен быстрому целочисленному делению числа m на 2n как для положительных, так и для отрицательных чисел. Оператор m>>>n, заполняющий нулями освободившиеся после сдвигов биты, переводит отрицательные числа в положительные. Поэтому он не может быть эквивалентен быстрому делению числа на 2n. Но иногда такой оператор бывает нужен для манипуляции с наборами бит, хранящихся в числовой ячейке. Само значение числа в этом случае значения не имеет, а ячейка используется как буфер соответствующего размера.
Например, можно преобразовать последовательность бит, образующее некое целое значение, в число типа float методом Float.intBitsToFloat(целое значение) или типа double методом Double.intBitsToDouble (целое значение). Так, Float.intBitsToFloat(0x7F7FFFFF) даст максимальное значение типа float.
4.3. Двоичное представление вещественных чисел
Целое число 01012 можно представить в виде 01012 =0*23 + 1*22 + 0*21 + 1*20
Аналогично можно записать двоичную дробь:
11.01012 =1*21+ 1*20 + 0*2-1 + 1*2-2 + 0*2-3 + 1*2-4
Заметим, что сдвиг двоичной точки на n разрядов вправо (чаще говорят о сдвиге самого числа влево) эквивалентен умножению числа на (102)n = 2n. Сдвиг точки влево (то есть сдвиг самого числа вправо) – делению на 2n.
Рассмотрим сначала упрощенную схему хранения чисел в формате с плавающей точкой (floating point), несколько отличающуюся от реальной.
Число x с плавающей точкой может быть представлено в виде x=s*m*2p. Множитель s – знак числа. Второй множитель m называется мантиссой, а число p – порядком числа.
Для простоты рассмотрим 10-битовую ячейку, состоящую из трёх независимых частей:
знак порядок мантисса
1 бит 4 бита 5 бит
Первым идёт знаковый бит. Если он равен 0, число положительно, если равен 1 – отрицательно. Набор бит, хранящийся в мантиссе, задает положительное число m, лежащее в пределах 1≤m<2. Оно получается из нашего двоичного числа путем переноса двоичной точки на место после первой значащей цифры числа. Например, числа 1.01012, 10.1012 и 0.101012 и имеют одну и ту же мантиссу, равную 1.01012. При этом следующая за ведущей единицей точка в ячейке, выделяемой под мантиссу, не хранится - она подразумевается. То есть мантиссы приведённых чисел будут храниться в виде 101012.
Число сдвигов двоичной точки (с учетом знака) хранится в части ячейки, выделяемой под порядок числа. В нашем примере числа 1.01012, 10.1012 и 0.101012 будут иметь порядки 0, 1 и -1, соответственно. При перемножении чисел их мантиссы перемножаются, а порядки складываются. При делении – мантиссы делятся, а порядки вычитаются. И умножение, и деление мантисс происходит по тем же алгоритмам, что и для целых чисел. Но при выходе за размеры ячейки отбрасываются не старшие, а младшие байты. В результате каждая операция умножения или деления даёт результат, отличающийся от точного на несколько значений младшего бита мантиссы. Аналогичная ситуация с потерей младших бит возникает при умножениях и делениях. Ведь если в ячейках для чисел данного типа хранится k значащих цифр числа, то при умножении двух чисел точный результат будет иметь 2k значащих цифр, последние k из которых при записи результата в ячейку будут отброшены даже в том случае, если они сохранялись при вычислениях. А при делении в общем случае при точных вычислениях должна получаться бесконечная периодическая двоичная дробь, так что даже теоретически невозможно провести эти вычисления без округлений. С этим связана конечная точность вычислений на компьютерах при использовании формата с “плавающей точкой”. При этом чем больше двоичных разрядов выделяется под мантиссу числа, тем меньше погрешность в такого рода операциях.
Замечание: системы символьных вычислений (или, что то же, – аналитических вычислений, или, что то же, системы компьютерной алгебры) позволяют проводить точные численные расчеты с получением результатов в виде формул. Однако они выполняют вычисления на много порядков медленнее, требуют намного больше ресурсов и не могут работать без громоздкой среды разработки. Поэтому для решения большинства практически важных задач они либо неприменимы, либо их использование нецелесообразно.
При сложении или вычитании сначала происходит приведение чисел к одному порядку: мантисса числа с меньшим порядком делится на 2n, а порядок увеличивается на n, где n – разница в порядке чисел. При этом деление на 2n осуществляется путем сдвига мантиссы на n бит вправо, с заполнением освобождающихся слева бит нулями. Младшие биты мантиссы, выходящие за пределы отведенной под нее части ячейки, теряются.
Пример:
сложим числа 11.0112 и 0.110112 . Для первого числа мантисса 1.10112, порядок 1, так как 11.0112=1.10112*(102)1. Для второго – мантисса 1.10112 , порядок -1, так как 0.110112 =1.10112*(102)-1. Приводим порядок второго числа к значению 1, сдвигая мантиссу на 2 места вправо, так как разница порядков равна 2: